2025/12/18 by Mikkel Thorup, Thorup, Mikkel, Hanzhi Wang +1
Physics and Astronomy · Computer Science · Mathematics · #Complex Network Analysis Techniques #Graph Theory and Algorithms #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2512.16087
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 the simple classic bidirectional 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 O(n) edges. In addition, we provide a counterexample showing that the bidirectional algorithm is not instance-optimal for graphs whose degrees are mostly equal to n. We also consider weighted graphs and multigraphs. We show that the bidirectional algorithm is instance-optimal on all multigraphs, but for weighted simple graphs, we have almost the same limitations as for unweighted simple graphs.