Rational extrapolation for the PageRank vector

Brezinski, C.; Redivo-Zaglia, M.

doi:10.1090/S0025-5718-08-02086-3

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.