Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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.
Published electronically: 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 $ c$, with a rank one matrix. Its left principal eigenvector now depends on $ c$, and it is the PageRank vector we are looking for. However, when $ c$ 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 $ c$, 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 $ c$. Numerical experiments end the paper.

References [Enhancements On Off] (What's this?)

  • 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. C. Brezinski, Projection Methods for Systems of Equations, North-Holland, Amsterdam, 1997. MR 1616573 (99f:65004)
  • 5. C. Brezinski, M. Redivo-Zaglia, The PageRank vector: Properties, computation, approximation, and acceleration, SIAM J. Matrix Anal. Appl., 28 (2006) 551-575. MR 2255342 (2007h:68205)
  • 6. C. Brezinski, M. Redivo-Zaglia, G. Rodriguez, S. Seatzu, Extrapolation techniques for ill-conditioned linear systems, Numer. Math., 81 (1998) 1-29. MR 1657714 (99j:65069)
  • 7. C. Brezinski, M. Redivo-Zaglia, S. Serra-Capizzano, Extrapolation methods for PageRank computations, C.R. Math. Acad. Sci. Paris, 340 (2005) 393-397. MR 2127117
  • 8. P.J. Davis, Interpolation and Approximation, Reprint, Dover, New York, 1975. 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. R. Kerner, Models of Agglomeration and Glass Transition, Imperial College Press, London, 2006. MR 2289782
  • 15. A.N. Langville, C.D. Meyer, Google's PageRank and Beyond. The Science of Search Engine Rankings, Princeton University Press, Princeton and Oxford, 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) 167-256. MR 2010377 (2005a:05206)
  • 19. E. Ravasz, A.-L. Barabási, Hierarchical organization in complex networks, Phys. Rev., E 67, 026112 (2003).
  • 20. S. Serra-Capizzano, Jordan canonical form of the Google matrix: A potential contribution to the PageRank computation, SIAM J. Matrix Anal. Appl., 27 (2005) 305-312. MR 2179674 (2006g:15019)
  • 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., volltexte/2007/1069
  • 22. D.J. Watts, Networks, dynamics and small-world phenomenon, Amer. J. Sociology, 105 (1999) 493-527.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65B05, 65F15, 68U35.

Retrieve articles in all journals with MSC (2000): 65B05, 65F15, 68U35.

Additional Information

C. Brezinski
Affiliation: Laboratoire Paul Painlevé, UMR CNRS 8524, UFR de Mathématiques Pures et Appliquées, Université des Sciences et Technologies de Lille, 59655–Villeneuve d’Ascq cedex, France

M. Redivo-Zaglia
Affiliation: Università degli Studi di Padova, Dipartimento di Matematica Pura ed Applicata, Via Trieste 63, 35121–Padova, Italy

Keywords: Extrapolation, PageRank, web matrix, eigenvector computation.
Received by editor(s): January 23, 2007
Received by editor(s) in revised form: June 27, 2007
Published electronically: February 7, 2008
Additional Notes: The work of the second author was supported by MIUR under the PRIN grant no. 2006017542-003
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society