Computing Personalized PageRank Using Strongly Connected Components in Web
Date Issued
2008
Date
2008
Author(s)
Tzeng, Rung-Guo
Abstract
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.
Subjects
Algorithm
Search Engine
Linkage Analysis
Linear System
PageRank
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95921088-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):9b611e9eef0a62ad59de8465d613727b