Abstract

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 (1pmepsilon)-approximation of its score by examining only O~(min(n1/2Delta1/2,n1/2m1/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(n1/2Delta1/2, n1/3m1/3)) for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph-access model, our technique yields a O~(min(n1/2Delta1/2,n2/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.