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.
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