Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Rational extrapolation for the PageRank vector

Authors: C. Brezinski and M. Redivo-Zaglia
Journal: Math. Comp. 77 (2008), 1585-1598
MSC (2000): Primary 65B05, 65F15, 68U35.
Posted: February 7, 2008
MathSciNet review: 2398781
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An important problem in web search is to determine the importance of each page. From the mathematical point of view, this problem consists in finding the nonnegative left eigenvector of a matrix corresponding to its dominant eigenvalue 1. Since this matrix is neither stochastic nor irreducible, the power method has convergence problems. So, the matrix is replaced by a convex combination, depending on a parameter , with a rank one matrix. Its left principal eigenvector now depends on , and it is the PageRank vector we are looking for. However, when is close to 1, the problem is ill-conditioned, and the power method converges slowly. So, the idea developed in this paper consists in computing the PageRank vector for several values of , and then to extrapolate them, by a conveniently chosen rational function, at a point near 1. The choice of this extrapolating function is based on the mathematical expression of the PageRank vector as a function of . Numerical experiments end the paper.

References

1. M. Bianchini, M. Gori, F. Scarselli, Inside PageRank, ACM Trans. Internet Tech., 5 (2005) 92-128.
2. P. Boldi, M. Santini, S. Vigna, PageRank as a function of the damping factor, in Proceedings of the 14th International World Wide Web Conference, ACM Press, New York, 2005, pp. 557-566.
3. A. Borodin, G.O. Roberts, J.S. Rosenthal, P. Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, in Proceedings of the 11th International World Wide Web Conference, ACM Press, New York, 2001, pp. 415-429.
4. Claude Brezinski, Projection methods for systems of equations, Studies in Computational Mathematics, vol. 7, North-Holland Publishing Co., Amsterdam, 1997. MR 1616573 (99f:65004)
5. Claude Brezinski and Michela Redivo-Zaglia, The PageRank vector: properties, computation, approximation, and acceleration, SIAM J. Matrix Anal. Appl. 28 (2006), no. 2, 551–575 (electronic). MR 2255342 (2007h:68205), http://dx.doi.org/10.1137/050626612
6. C. Brezinski, M. Redivo-Zaglia, G. Rodriguez, and S. Seatzu, Extrapolation techniques for ill-conditioned linear systems, Numer. Math. 81 (1998), no. 1, 1–29. MR 1657714 (99j:65069), http://dx.doi.org/10.1007/s002110050382
7. Claude Brezinski, Michela Redivo-Zaglia, and Stefano Serra-Capizzano, Extrapolation methods for PageRank computations, C. R. Math. Acad. Sci. Paris 340 (2005), no. 5, 393–397 (English, with English and French summaries). MR 2127117, http://dx.doi.org/10.1016/j.crma.2005.01.015
8. Philip J. Davis, Interpolation and approximation, Dover Publications Inc., New York, 1975. Republication, with minor corrections, of the 1963 original, with a new preface and bibliography. MR 0380189 (52 #1089)
9. N. Eiron, K.S. McCurley, J.A. Tomlin, Ranking the web frontier, in Proceedings of the 13th International World Wide Web Conference, ACM Press, New York, 2004, pp. 309-318.
10. R.A. Horn, S. Serra-Capizzano, A general setting for the parametric Google matrix, Internet Math., to appear.
11. I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl., submitted.
12. 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, ACM Press, New York, 2003, pp. 261-270.
13. M. Kendall, A new measure of rank correlation, Biometrika, 30 (1938) 81-89.
14. Richard Kerner, Models of agglomeration and glass transition, Imperial College Press, London, 2007. MR 2289782 (2008g:82002)
15. Amy N. Langville and Carl D. Meyer, Google’s PageRank and beyond: the science of search engine rankings, Princeton University Press, Princeton, NJ, 2006. MR 2262054 (2007h:68002)
16. R. Lempel, S. Moran, Rank-stability and rank-similarity of link-based web ranking algorithms in authority-connected graphs, in Second Workshop on Algorithms and Models for the Web-Graph (WAW 2003), Budapest, Hungary, May 2003.
17. R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, U. Alon, Superfamilies of designed and evolved networks, Science, 303 (2004) 1538-1542.
18. M. E. J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2003), no. 2, 167–256 (electronic). MR 2010377 (2005a:05206), http://dx.doi.org/10.1137/S003614450342480
19. E. Ravasz, A.-L. Barabási, Hierarchical organization in complex networks, Phys. Rev., E 67, 026112 (2003).
20. Stefano Serra-Capizzano, Jordan canonical form of the Google matrix: a potential contribution to the PageRank computation, SIAM J. Matrix Anal. Appl. 27 (2005), no. 2, 305–312 (electronic). MR 2179674 (2006g:15019), http://dx.doi.org/10.1137/S0895479804441407
21. S. Serra-Capizzano, Google pageranking problem: The model and the analysis, Proc. of the Dagstuhl Seminar 7071 Web Information Retrieval and Linear Algebra Algorithms, March 2007, A. Frommer, M.W. Mahoney, D.B. Szyld eds., http://drops.dagstuhl.de/opus/ volltexte/2007/1069
22. D.J. Watts, Networks, dynamics and small-world phenomenon, Amer. J. Sociology, 105 (1999) 493-527.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|