×

Adaptive methods for the computation of PageRank. (English) Zbl 1091.68044

Summary: We observe that the convergence patterns of pages in the PageRank algorithm have a nonuniform distribution. Specifically, many pages converge to their true PageRank quickly, while relatively few pages take a much longer time to converge. Furthermore, we observe that these slow-converging pages are generally those pages with high PageRank. We use this observation to devise a simple algorithm to speed up the computation of PageRank, in which the PageRank of pages that have converged are not recomputed at each iteration after convergence. This algorithm, which we call Adaptive PageRank, speeds up the computation of PageRank by nearly 30%.

MSC:

68P20 Information storage and retrieval of data
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Golub, G. H.; Loan, C. F.V, Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore
[2] Grimmett, G.; Stirzaker, D., Probability and Random Processes (1989), Oxford University Press · Zbl 0759.60002
[3] T.H. Haveliwala, Topic-sensitive PageRank, in: Proceedings of the 11th International World Wide Web Conference, 2002; T.H. Haveliwala, Topic-sensitive PageRank, in: Proceedings of the 11th International World Wide Web Conference, 2002
[4] T.H. Haveliwala, S.D. Kamvar, The second eigenvalue of the Google matrix, Stanford University Technical Report, 2003; T.H. Haveliwala, S.D. Kamvar, The second eigenvalue of the Google matrix, Stanford University Technical Report, 2003
[5] J. Hirai, S. Raghavan, H. Garcia-Molina, A. Paepcke, WebBase: a repository of web pages, in: Proceedings of the Ninth International World Wide Web Conference, 2000; J. Hirai, S. Raghavan, H. Garcia-Molina, A. Paepcke, WebBase: a repository of web pages, in: Proceedings of the Ninth International World Wide Web Conference, 2000
[6] G. Jeh, J. Widom, Scaling personalized web search, in: Proceedings of the 12th International World Wide Web Conference, 2003; G. Jeh, J. Widom, Scaling personalized web search, in: Proceedings of the 12th International World Wide Web Conference, 2003
[7] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolation methods for accelerating PageRank computations, in: Proceedings of the 12th International World Wide Web Conference, 2003; S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolation methods for accelerating PageRank computations, in: Proceedings of the 12th International World Wide Web Conference, 2003
[8] L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: bringing order to the web, Stanford Digital Libraries Working Paper, 1998; L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: bringing order to the web, Stanford Digital Libraries Working Paper, 1998
[9] Richardson, M.; Domingos, P., The intelligent surfer: probabilistic combination of link and content information in PageRank, (in: Advances in Neural Information Processing Systems, vol. 14 (2002), MIT Press: MIT Press Cambridge, MA)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.