|
Rational extrapolation for the PageRank vector
Author(s):
C.
Brezinski;
M.
Redivo-Zaglia.
Journal:
Math. Comp.
77
(2008),
1585-1598.
MSC (2000):
Primary 65B05, 65F15, 68U35.
Posted:
February 7, 2008
Retrieve article in:
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  , with a rank one matrix. Its left principal eigenvector now depends on  , and it is the PageRank vector we are looking for. However, when  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  , 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  . Numerical experiments end the paper.
References:
-
- 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., 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:
10.1090/S0025-5718-08-02086-3
PII:
S 0025-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
Posted:
February 7, 2008
Additional Notes:
The work of the second author was supported by MIUR under the PRIN grant no. 2006017542-003
Copyright of article:
Copyright
2008,
American Mathematical Society
|
Comments: webmaster@ams.org