Instance-Optimality in PageRank Computation
This work addresses the efficiency of PageRank computation for sparse graphs, offering near-optimal guarantees, but it is incremental as it builds on existing algorithms.
The paper tackles the problem of estimating a vertex's PageRank with constant relative error and probability, proving that an adaptive variant of a classic algorithm is instance-optimal up to a polylogarithmic factor for directed graphs with bounded or sparse degrees, and provides a counterexample for graphs with mostly high degrees.
We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of a simple, classic algorithm is instance-optimal up to a polylogarithmic factor for all directed graphs of order $n$ whose maximum in- and out-degrees are at most a constant fraction of $n$. In other words, there is no correct algorithm that can be faster than our algorithm on any such graph by more than a polylogarithmic factor. We further extend the instance-optimality to all graphs in which at most a polylogarithmic number of vertices have unbounded degrees. This covers all sparse graphs with $\tilde{O}(n)$ edges. Finally, we provide a counterexample showing that our algorithm is not instance-optimal for graphs whose degrees are mostly equal to $n$.