Comptes Rendus
Numerical Analysis
Extrapolation methods for PageRank computations
Comptes Rendus. Mathématique, Volume 340 (2005) no. 5, pp. 393-397.

The mathematical problem behind Web search is the computation of the nonnegative left eigenvector of a stochastic matrix P corresponding to the dominant eigenvalue 1. This vector is called the PageRank vector. Since the matrix P is ill-conditioned, the computation of PageRank is difficult and the matrix P is replaced by P(c)=cP+(1c)E, where E is a rank one matrix and c a parameter. The dominant left eigenvector of P(c) is denoted by PageRank(c). This vector can be computed for several values of c and then extrapolated at the point c=1. In this Note, we construct special extrapolation methods for this problem. They are based on the mathematical analysis of the vector PageRank(c).

Le problème mathématique qui est sous-jacent à la recherche sur le Web est le calcul du vecteur propre gauche non négatif d'une matrice stochastique P correspondant à la valeur propre dominante 1. Ce vecteur s'appelle PageRank. Puisque la matrice P est mal conditionnée, le calcul de PageRank est difficile et la matrice P est remplacée par P(c)=cP+(1c)E, où E est une matrice de rang 1 et c un paramètre. Le vecteur propre gauche dominant de P(c) est dénoté PageRank(c). On le calcule pour plusieurs valeurs de c et ensuite on l'extrapole en c=1. Dans cette Note, on construit des méthodes spéciales d'extrapolation pour ce problème. Elles sont basées sur l'analyse mathématique du vecteur PageRank(c).

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2005.01.015

Claude Brezinski 1; Michela Redivo-Zaglia 2; Stefano Serra-Capizzano 3

1 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
2 Università degli Studi di Padova, Dipartimento di Matematica Pura ed Applicata, Via G.B. Belzoni 7, 35131 Padova, Italy
3 Dipartimento di Fisica e Matematica, Università dell'Insubria – Sede di Como, Via Vallegio 11, 22100 Como, Italy
@article{CRMATH_2005__340_5_393_0,
     author = {Claude Brezinski and Michela Redivo-Zaglia and Stefano Serra-Capizzano},
     title = {Extrapolation methods for {PageRank} computations},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {393--397},
     publisher = {Elsevier},
     volume = {340},
     number = {5},
     year = {2005},
     doi = {10.1016/j.crma.2005.01.015},
     language = {en},
}
TY  - JOUR
AU  - Claude Brezinski
AU  - Michela Redivo-Zaglia
AU  - Stefano Serra-Capizzano
TI  - Extrapolation methods for PageRank computations
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 393
EP  - 397
VL  - 340
IS  - 5
PB  - Elsevier
DO  - 10.1016/j.crma.2005.01.015
LA  - en
ID  - CRMATH_2005__340_5_393_0
ER  - 
%0 Journal Article
%A Claude Brezinski
%A Michela Redivo-Zaglia
%A Stefano Serra-Capizzano
%T Extrapolation methods for PageRank computations
%J Comptes Rendus. Mathématique
%D 2005
%P 393-397
%V 340
%N 5
%I Elsevier
%R 10.1016/j.crma.2005.01.015
%G en
%F CRMATH_2005__340_5_393_0
Claude Brezinski; Michela Redivo-Zaglia; Stefano Serra-Capizzano. Extrapolation methods for PageRank computations. Comptes Rendus. Mathématique, Volume 340 (2005) no. 5, pp. 393-397. doi : 10.1016/j.crma.2005.01.015. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2005.01.015/

[1] C. Brezinski; M. Redivo Zaglia Extrapolation Methods. Theory and Practice, North-Holland, Amsterdam, 1991

[2] C. Brezinski, M. Redivo Zaglia, On the acceleration of PageRank computations, submitted for publication

[3] C. Brezinski; M. Redivo Zaglia; G. Rodriguez; S. Seatzu Extrapolation techniques for ill-conditioned linear systems, Numer. Math., Volume 81 (1998), pp. 1-29

[4] G.H. Golub; C.F. Van Loan Matrix Computations, Johns Hopkins University Press, Baltimore, 1983

[5] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolations methods for accelerating PageRank computations, WWW2003, May 20–24, 2003, Budapest, Hungary

[6] S. Serra-Capizzano, Jordan canonical form of the Google matrix: a potential contribution to the PageRank computation, SIAM J. Matrix Anal., in press. See a preliminary version as Technical Report SCCM-4-3, Stanford University, Stanford, 2004

Cited by Sources:

Comments - Policy