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.
Accepted:
Published online:
Claude Brezinski 1; Michela Redivo-Zaglia 2; Stefano Serra-Capizzano 3
@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 -
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] 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
Cited by Sources:
Comments - Policy