  The identification of the set of k most central nodes of a graph, or
centrality maximization, is a key task in network analysis, with various
applications ranging from finding communities in social and biological networks
to understanding which seed nodes are important to diffuse information in a
graph. As the exact computation of centrality measures does not scale to
modern-sized networks, the most practical solution is to resort to rigorous,
but efficiently computable, randomized approximations. In this work we present
CentRA, the first algorithm based on progressive sampling to compute
high-quality approximations of the set of k most central nodes. CentRA is based
on a novel approach to efficiently estimate Monte Carlo Rademacher Averages, a
powerful tool from statistical learning theory to compute sharp data-dependent
approximation bounds. Then, we study the sample complexity of centrality
maximization using the VC-dimension, a key concept from statistical learning
theory. We show that the number of random samples required to compute
high-quality approximations scales with finer characteristics of the graph,
such as its vertex diameter, or of the centrality of interest, significantly
improving looser bounds derived from standard techniques. We apply CentRA to
analyze large real-world networks, showing that it significantly outperforms
the state-of-the-art approximation algorithm in terms of number of samples,
running times, and accuracy.
