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 Free Access

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. Claude Brezinski, Projection methods for systems of equations, Studies in Computational Mathematics, vol. 7, North-Holland Publishing Co., Amsterdam, 1997. MR 1616573
  • 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, 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, 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, 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
  • 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
  • 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
  • 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, 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, 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.

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
Email: Claude.Brezinski@univ-lille1.fr

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

DOI: https://doi.org/10.1090/S0025-5718-08-02086-3
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