We study an adaptive variant of a simple, classic algorithm for estimating a vertex's PageRank centrality within a constant relative error, with constant probability. We show that this algorithm is instance-optimal up to a polylogarithmic factor for any directed graph of order n whose maximal in- and out-degrees are at most a constant fraction of n. The instance-optimality also extends to graphs in which up to a polylogarithmic number of vertices have unbounded degree, thereby covering all sparse graphs with O (n) edges. Finally, we provide a counterexample showing that the algorithm is not instance-optimal for graphs with degrees mostly equal to n.
Thorup et al. (Thu,) studied this question.