Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Rational extrapolation for the PageRank vector
HTML articles powered by AMS MathViewer

by C. Brezinski and M. Redivo-Zaglia PDF
Math. Comp. 77 (2008), 1585-1598 Request permission

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
  • M. Bianchini, M. Gori, F. Scarselli, Inside PageRank, ACM Trans. Internet Tech., 5 (2005) 92–128.
  • 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.
  • 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.
  • Claude Brezinski, Projection methods for systems of equations, Studies in Computational Mathematics, vol. 7, North-Holland Publishing Co., Amsterdam, 1997. MR 1616573
  • 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. MR 2255342, DOI 10.1137/050626612
  • 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, DOI 10.1007/s002110050382
  • 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, DOI 10.1016/j.crma.2005.01.015
  • 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
  • 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.
  • R.A. Horn, S. Serra-Capizzano, A general setting for the parametric Google matrix, Internet Math., to appear.
  • I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl., submitted.
  • 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.
  • M. Kendall, A new measure of rank correlation, Biometrika, 30 (1938) 81–89.
  • Richard Kerner, Models of agglomeration and glass transition, Imperial College Press, London, 2007. MR 2289782
  • 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, DOI 10.1515/9781400830329
  • 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.
  • 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.
  • M. E. J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2003), no. 2, 167–256. MR 2010377, DOI 10.1137/S003614450342480
  • E. Ravasz, A.-L. Barabási, Hierarchical organization in complex networks, Phys. Rev., E 67, 026112 (2003).
  • 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. MR 2179674, DOI 10.1137/S0895479804441407
  • 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
  • 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
  • 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
  • © Copyright 2008 American Mathematical Society
  • Journal: Math. Comp. 77 (2008), 1585-1598
  • MSC (2000): Primary 65B05, 65F15, 68U35
  • DOI: https://doi.org/10.1090/S0025-5718-08-02086-3
  • MathSciNet review: 2398781