Extrapolation methods for PageRank computations

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+(1?c)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)$. To cite this article: C. Brezinski et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).