Frank McSherry
ABSTRACT
In this note we consider a simple reformulation of the traditional power iteration algorithm for computing the stationary distribution of a Markov chain. Rather than communicate their current probability values to their neighbors at each step, nodes instead communicate only changes in probability value. This reformulation enables a large degree of flexibility in the manner in which nodes update their values, leading to an array of optimizations and features, including faster convergence, efficient incremental updating, and a robust distributed implementation.While the spirit of many of these optimizations appear in previous literature, we observe several cases where this unification simplifies previous work, removing technical complications and extending their range of applicability. We implement and measure the performance of several optimizations on a sizable (34M node) web subgraph, seeing significant composite performance gains, especially for the case of incremental recomputation after changes to the web graph.
- Arvind Arasu, Jasmine Novak, Andrew Tomkins, and John Tomlin, Pagerank computation and the structure of the web: Experiments and algorithms. WWW 2002 poster.Google Scholar
- Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks 30(1-7): 107--117 (1998). Google ScholarDigital Library
- Steve Chien, Cynthia Dwork, Ravi Kumar, Dan Simon, and D. Sivakumar, Link evolution: Analysis and algorithms. Internet Mathematics: Volume 1, No. 3, pp. 277--304.Google Scholar
- Nadav Eiron, Kevin McCurley, and John Tomlin, Ranking the web frontier. WWW 2004. Google ScholarDigital Library
- Sepandar Kamvar, Taher Haveliwala, and Gene Golub, Adaptive Methods for the Computation of PageRank. Stanford University Technical Report, 2003.Google Scholar
- Sepandar Kamvar, Taher Haveliwala, Christopher Manning, and Gene Golub, Exploiting the Block Structure of the Web for Computing PageRank. Stanford University Technical Report, 2003.Google Scholar
- Sepandar Kamvar, Taher Haveliwala, Christopher Manning, and Gene Golub, Extrapolation Methods for Accelerating PageRank Computations. WWW 2003. Google ScholarDigital Library
- Taher Haveliwala, Topic-Sensitive PageRank. WWW 2002. Google ScholarDigital Library
- Glen Jeh and Jennifer Widom, Scaling Personalized Web Search. WWW 2003. Google ScholarDigital Library
- Amy Langville and Carl Meyer, A Reordering for the PageRank problem. NCSU CRSC Technical Report #CRSC-TR04-16. March 2004.Google Scholar
Index Terms
- A uniform approach to accelerated PageRank computation
Recommendations
Extrapolation methods for accelerating PageRank computations
WWW '03: Proceedings of the 12th international conference on World Wide WebWe 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 ...
Web graph analyzer tool
valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and toolsWe present the software tool "Web Graph Analyzer". This tool is designed to perform a comprehensive analysis of the Web Graph structure. By Web Graph we mean a graph whose vertices are Web pages and whose edges are hyper-links. With the help of the Web ...
The distribution of pageRank follows a power-law only for particular values of the damping factor
WWW '06: Proceedings of the 15th international conference on World Wide WebWe show that the empirical distribution of the PageRank values in a large set of Web pages does not follow a power-law except for some particular choices of the damping factor. We argue that for a graph with an in-degree distribution following a power-...
Comments