FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs

We propose a new algorithm, FAST-PPR, for the Significant-PageRank problem: given input nodes s, t in a directed graph and threshold δ, decide if the Personalized PageR-ank from s to t is at least δ. Existing algorithms for this problem have a running-time of Ω(1/δ); this makes them unsuitable for use in large social-networks for applications requiring values of δ = O(1/n). FAST-PPR is based on a bi-directional search and requires no preprocessing of the graph. It has a provable average running-time guarantee of Õ( d/δ) (where d is the average in-degree of the graph). We complement this result with an Ω(1/ δ) lower bound for Significant-PageRank, showing that the dependence on δ cannot be improved. We perform a detailed empirical study on numerous mas-sive graphs showing that FAST-PPR dramatically outper-forms existing algorithms. For example, with target nodes sampled according to popularity, on the 2010 Twitter graph with 1.5 billion edges, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced ver-sion of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs