Nearly optimal Personalized PageRank computation
In the authors' words
We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph . We focus on the -error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 & Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL -error guarantee in time, where is the teleportation parameter. In this paper, we eliminate the dependence on and present an algorithm that achieves the same error guarantee in time. Consequently, we obtain a nearly optimal algorithm for PPR computation under the ACL error guarantee, and a nearly linear algorithm for local graph clustering with complexity independent of .
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.