2014/04/07 by Bressan, Marco, Peserico, Enoch, Pretto, Luca
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.1404.1864
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, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1-δ) computes a multiplicative (1±ε)-approximation of its score by examining only O(min(m2/3 Δ1/3 d-2/3, m4/5 d-3/5)) nodes/arcs, where Δ and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(ε-1) and polylog(δ-1) factors). A similar bound holds for computational complexity. We also prove a lower bound of Ω(min(m1/2 Δ1/2 d-1/2, m2/3 d-1/3)) for both query complexity and computational complexity. Moreover, our technique yields a O(n2/3) query complexity algorithm for the graph access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.