[Méthodes d'extrapolation pour les calculs de PageRank]
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 , where E is a rank one matrix and c a parameter. The dominant left eigenvector of is denoted by PageRank. This vector can be computed for several values of c and then extrapolated at the point . In this Note, we construct special extrapolation methods for this problem. They are based on the mathematical analysis of the vector PageRank.
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 , où E est une matrice de rang 1 et c un paramètre. Le vecteur propre gauche dominant de est dénoté PageRank. On le calcule pour plusieurs valeurs de c et ensuite on l'extrapole en . 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.
Accepté le :
Publié le :
Brezinski, Claude 1 ; Redivo-Zaglia, Michela 2 ; Serra-Capizzano, Stefano 3
@article{CRMATH_2005__340_5_393_0,
author = {Brezinski, Claude and Redivo-Zaglia, Michela and Serra-Capizzano, Stefano},
title = {Extrapolation methods for {PageRank} computations},
journal = {Comptes Rendus. Math\'ematique},
pages = {393--397},
year = {2005},
publisher = {Elsevier},
volume = {340},
number = {5},
doi = {10.1016/j.crma.2005.01.015},
language = {en},
url = {https://www.numdam.org/articles/10.1016/j.crma.2005.01.015/}
}
TY - JOUR AU - Brezinski, Claude AU - Redivo-Zaglia, Michela AU - Serra-Capizzano, Stefano TI - Extrapolation methods for PageRank computations JO - Comptes Rendus. Mathématique PY - 2005 SP - 393 EP - 397 VL - 340 IS - 5 PB - Elsevier UR - https://www.numdam.org/articles/10.1016/j.crma.2005.01.015/ DO - 10.1016/j.crma.2005.01.015 LA - en ID - CRMATH_2005__340_5_393_0 ER -
%0 Journal Article %A Brezinski, Claude %A Redivo-Zaglia, Michela %A Serra-Capizzano, Stefano %T Extrapolation methods for PageRank computations %J Comptes Rendus. Mathématique %D 2005 %P 393-397 %V 340 %N 5 %I Elsevier %U https://www.numdam.org/articles/10.1016/j.crma.2005.01.015/ %R 10.1016/j.crma.2005.01.015 %G en %F CRMATH_2005__340_5_393_0
Brezinski, Claude; Redivo-Zaglia, Michela; Serra-Capizzano, Stefano. Extrapolation methods for PageRank computations. Comptes Rendus. Mathématique, Tome 340 (2005) no. 5, pp. 393-397. doi: 10.1016/j.crma.2005.01.015
[1] 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] Extrapolation techniques for ill-conditioned linear systems, Numer. Math., Volume 81 (1998), pp. 1-29
[4] 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
Cité par Sources :
