Revisiting Local Push: Faster Algorithms and Optimal Query Complexity for PageRank and Effective ResistanceResearch Paper
Personalized PageRank from a seed node is the basic primitive of local graph algorithms: it drives local clustering by sweep cuts (Andersen, Chung, Lang 2007; Andersen, Chung 2007) and the bidirectional estimation of single PageRank values (Lofgren, Banerjee, Goel 2015). The standard local method is the push of Andersen, Chung and Lang. It computes an…