Sublinear Algorithms for Local Graph-Centrality Estimation

We study the complexity of local graph-centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of n nodes and m arcs, with probability (1 -delta) computes a multiplicative (1 +/-epsilon)-approximation of its score by examining only O(min(n(1/2)Delta(1/2),n(1/2)m(1/4))) nodes/arcs, where Delta is the maximum outdegree of the graph and poly(epsilon (-1)) and polylog(delta(-1)) factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of Omega (min(n(1/2)Delta(1/2), n(1/3)m(1/3))) for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph -access model, our technique yields a O(min(n(1/2)Delta(1/2), n(2/3)))-queries algorithm; we show that this algorithm is optimal up to a logarithmic factor-in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node.