PageRank Centrality in Directed Graphs with Bounded In-Degree

We study the computational complexity of locally estimating a node's PageRank centrality in a directed graph G. For any node t, its PageRank centrality π(t) is defined as the probability that a random walk in G, starting from a uniformly chosen node, terminates at t, where each step terminates with a constant probability α ∈ (0, 1).

To obtain a multiplicative 1 ± O(1) -approximation of π(t) with probability Ω(1), the pre-

from [Wang, Wei, Wen, Yang, STOC '24], where n and m denote the number of nodes and edges in G, and ∆ in and ∆ out upper bound the in-degrees and out-degrees of G, respectively. Using a refinement of the proof in the same paper, we establish a lower bound of

. As γ only depends on ∆ in and n γ = O(1) for ∆ in = Ω n Ω(1) , the known upper bound is tight if we only parameterize the complexity by n, m, and ∆ out . However, there remains a gap of Ω (n γ ) when considering the maximum in-degree ∆ in , and this gap is large when ∆ in is small. In the extreme case where ∆ in ≤ 1/(1α), we have γ = 1/2, leading to a gap of Ω n 1/2 between the bounds O n 1/2 and Ω(1).

In this paper, we present a new algorithm that achieves the above lower bound (up to logarithmic factors). The algorithm assumes that n and the bounds ∆ in and ∆ out are known in advance. Our key technique is a novel randomized backwards propagation process that only propagates selectively based on Monte Carlo estimated PageRank scores.