Approximating PageRank locally with sublinear query complexity.

Can we approximate the centrality score of a given node by exploring only a vanishing fraction of the graph? In this paper we develop a combination of techniques that we apply to the case of PageRank, where the centrality of a node depends on \emph{every} arc in the graph. We obtain an algorithm that, given any one node in any $n$-node graph, with probability $1-\delta$ returns a multiplicative $(1\pm\epsilon)$ approximation of its PageRank score using at most $O\big(n^{\frac{2}{3}}\sqrt[3]{\log(n/\delta)}\,\ln(1/\delta)^\frac{1}{3}\epsilon^{-\frac{2}{3}}\big) = \tilde{O}(n^{\frac{2}{3}})$ graph exploration queries -- where a query returns either a given node's list of neighbours, or a node chosen uniformly at random. Until now, every algorithm required in general $\Omega(n)$ queries. We also show that this upper bound is essentially optimal by proving an almost matching lower bound. Our techniques can be applied to other centrality measures, even though we leave the analysis of the resulting bounds for future work.