PageRank using Power Extrapolation
We present a novel technique for speeding up the computation of PageRank, a hyperlink-based estimate of the “importance” o f Web pages, based on the ideas presented in [7]. The original PageRank algorit hm uses the Power Method to compute successive iterates that converge to the p rincipal eigenvector of the Markov matrix representing the Web link graph. The algorithm presented here, called Power Extrapolation, accelerates the c onv rgence of the Power Method by subtracting off the error along several nonprinci pal eigenvectors from the current iterate of the Power Method, making use of known n onprincipal eigenvalues of the Web hyperlink matrix. Empirically, we show tha t using Power Extrapolation speeds up PageRank computation by 30% on a Web gr aph of 80 million nodes in realistic scenarios over the standard power me thod, in a way that is simple to understand and implement.