利用網路中的強連結單元計算個人化網頁排序

Abstract

網頁排序是搜尋引擎中一項重要的排序技術。藉由不同的個人化向量，搜尋引擎公司可以為不同群組的使用者計算出特殊及適合的網頁排序向量。然而，僅計算單一網頁排序向量便需花費許多時間。為了解決這個問題，我們提出了SCC (Strongly Connected Component)網頁排序演算法。SCC 網頁排序演算法的主要精神在於利用舊的網頁排序向量推導出新的網頁排序向量。我們將網頁排序模組中原先的線性系統拆解為線性子系統。利用這些線性子系統間的相依關係，我們將原本的計算轉變為階層式架構。在計算個人化網頁排序向量時，我們檢查重覆計算的必要性。因此，我們可以避免一些迭代的重覆計算並達到效能上的改進。根據我們的實驗成果顯示，在計算諸多個人化網頁排序向量時，SCC 網頁排序演算法的表現在許多情況下可優於已知的加速演算法。

PageRank is an important ranking technique used in search engines. By using different personalization vectors, search engine companies can compute specific and adaptive PageRank vectors for different classes of users. However, computing even one PageRank vector consumes a lot of time. To address this problem, we propose the SCC (Strongly Connected Component) PageRank algorithm. The main spirit of SCC PageRank is utilizing the old PageRank vector to deduce the new one. We decompose the original linear system of PageRank model into linear subsystems. By using the dependency relation between these linear subsystems, we translate the original computation into a hierarchical manner. While computing personalized PageRank vectors, we check the necessity of recomputation. Thus, we can prevent some iterative recomputations and achieve an improvement of efficiency. As shown by our experimental results, while computing several personalized PageRank vectors, SCC PageRank performs better than the known accelerating algorithms in most cases.