  We present ABRA, a suite of algorithms that compute and maintain
probabilistically-guaranteed, high-quality, approximations of the betweenness
centrality of all nodes (or edges) on both static and fully dynamic graphs. Our
algorithms rely on random sampling and their analysis leverages on Rademacher
averages and pseudodimension, fundamental concepts from statistical learning
theory. To our knowledge, this is the first application of these concepts to
the field of graph analysis. The results of our experimental evaluation show
that our approach is much faster than exact methods, and vastly outperforms, in
both speed and number of samples, current state-of-the-art algorithms with the
same quality guarantees.
