Speaker: Frank McSherry 

Title : A Uniform Approach to PageRank Acceleration 

Time & Place: 1:30pm, EE1-025 

Abstract: 

In this talk we consider a simple algorithmic alternative to the 
standard power iteration algorithm for computing the stationary 
distribution of a Markov chain. The algorithm is based on shifting from 
the traditional propagation of probability mass (power iteration) to the 
propagation of changes in probability mass. Each round nodes communicate 
the difference between their present and previous levels, rather than 
retransmitting their actual values. 
This transformation enables several beneficial algorithmic 
optimizations, including faster convergence, efficient incremental 
updating, and a robust decentralized implementation. While many of these 
optimization have existed in the literature in spirit, we observe 
several cases where this unification simplifies previous work, removing 
technical complications and extending their range of applicability. We 
also discuss several optimizations that appear to be novel, and suggest 
directions for further investigation.