Revisiting Local Computation of PageRank: Simple and Optimal

We revisit the classic local graph exploration algorithm ApproxContributions proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW '07, Internet Math. '08) for computing an ϵ-approximation of the PageRank contribution vector for a target node t on a graph with n nodes and m edges. We give a worst-case complexity bound of ApproxContributions as O nπ(t)/ϵ • min ∆ in , ∆ out , √ m , where π(t) is the PageRank score of t, and ∆ in and ∆ out are the maximum in-degree and out-degree of the graph, resp. We also give a lower bound of Ω min ∆ in /δ, ∆ out /δ, √ m/δ, m for detecting the δ-contributing set of t, showing that the * This text is the full version of a paper accepted by the 56th Annual ACM Symposium on Theory of Computing (STOC 2024). This work was partially done at