title: Computing PageRank using Power Extrapolation
creator: Haveliwala, Taher
creator: Kamvar, Sepandar
creator: Klein, Dan
creator: Manning, Chris
creator: Golub, Gene
subject: Computer Science
subject: Databases and the Web
subject: Miscellaneous
description: We present a novel technique for speeding up the computation of PageRank, a hyperlink-based estimate of the ``importance'' of Web pages, based on the ideas presented in "Extrapolation Methods for Accelerating PageRank Computations".  The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph.  The algorithm presented here, called Power Extrapolation, accelerates the convergence of the Power Method by subtracting off the error along several nonprincipal eigenvectors from the current iterate of the Power Method, making use of known nonprincipal eigenvalues of the Web hyperlink matrix. Empirically, we show that using Power Extrapolation speeds up PageRank computation by 30% on a Web graph of 80 million nodes in realistic scenarios over the standard power method, in a way that is simple to understand and implement. 
publisher: Stanford
date: 2003
type: Techreport
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/605/1/2003-45.pdf
identifier: Haveliwala, Taher and Kamvar, Sepandar and Klein, Dan and Manning, Chris and Golub, Gene (2003) Computing PageRank using Power Extrapolation. Technical Report. Stanford.
relation: http://ilpubs.stanford.edu:8090/605/