Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1060745.1060829 | WWW |
Keywords | Field | DocType |
accelerated pagerank computation,uniform approach,current probability value,significant composite performance gain,web graph,probability value,simple reformulation,incremental recomputation,previous literature,previous work,markov chain,web subgraph,iterative algorithm,stationary distribution,random walk,link analysis,random walks | Convergence (routing),PageRank,Link analysis,Computer science,Unification,Markov chain,Theoretical computer science,Stationary distribution,Artificial intelligence,Power iteration,Machine learning,Computation | Conference |
ISBN | Citations | PageRank |
1-59593-046-9 | 47 | 2.98 |
References | Authors | |
8 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank McSherry | 1 | 4289 | 288.94 |