[Méthodes d'extrapolation pour les calculs de 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.
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.
Accepté le :
Publié le :
@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},
publisher = {Elsevier},
volume = {340},
number = {5},
year = {2005},
doi = {10.1016/j.crma.2005.01.015},
language = {en},
url = {http://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 - http://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 http://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. http://www.numdam.org/articles/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 :
