We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node  s  and target node  t  in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from  s  to  t , guaranteeing that the relative error is small as long π  s  ( t ) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of  O (√ d /δ) (where  d  is the average in-degree of the graph). This is a significant improvement, since δ is often  O (1/ n ) (where  n  is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved.   We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs.
['Peter Lofgren', 'Siddhartha Banerjee', 'Ashish Goel', 'C. Seshadhri']
FAST-PPR: scaling personalized pagerank estimation for large graphs