[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2002-54 | ||
| Previous version | 2002-54 | ||
| Next version(s) | 2003-16, 2002-54 | ||
| Submitted on | 28th of February 2003 | ||
| Author | Kamvar, Sepandar; Haveliwala, Taher; Manning, Chris; Golub, Gene | ||
| Title | Extrapolation Methods for Accelerating PageRank Computations | ||
| Date of publication | 2003 | ||
| Published in | Proceedings of the Twelfth International World Wide Web Conference | ||
| Citation | Kamvar, Sepandar; Haveliwala, Taher; Manning, Chris; Golub, Gene. Extrapolation Methods for Accelerating PageRank Computations, Proceedings of the Twelfth International World Wide Web Conference, 2003. | ||
| Number of pages | 10 | ||
| Language | English | ||
| Project | Stanford InfoLab; Database Group; Natural Language Processing Group | ||
| Type | Conference or Journal Paper | ||
| Subject group | Computer Science; Miscellaneous | ||
| Abstract | We present a novel algorithm for the fast computation of PageRank, a hyperlink-based estimate of the ``importance'' of Web pages. 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 Quadratic Extrapolation, accelerates the convergence of the Power Method by periodically subtracting off estimates of the nonprincipal eigenvectors from the current iterate of the Power Method. In Quadratic Extrapolation, we take advantage of the fact that the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method. Empirically, we show that using Quadratic Extrapolation speeds up PageRank computation by 25--300\% on a Web graph of 80 million nodes, with minimal overhead. Our contribution is useful to the PageRank community and the numerical linear algebra community in general, as it is a fast method for determining the dominant eigenvector of a matrix that is too large for standard fast methods to be practical. | ||
| Keywords | PageRank, link analysis, web search, eigenvector computation | ||
| Contact address |
kamvar@stanford.edu taherh@cs.stanford.edu | ||
| Sponsored by |
This paper is based upon work supported (in part) by the National Science Foundation under Grant No. IIS-0085896 and Grant No. CCR-9971010. This research was supported (in part) by the Research Collaboration between NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corporation and CSLI, Stanford University (research project on Concept Bases for Lexical Acquisition and Intelligently Reasoning with Meaning). | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]