ABRA: Approximating Betweenness Centrality with Rademacher Averages

Introduced ABRA, a new suite of algorithms for approximating betweenness centrality in static and dynamic graphs. ABRA uses progressive random sampling and statistical learning theory (Rademacher averages, pseudodimension) to provide probabilistically guaranteed, high-quality approximations. It significantly outperforms exact methods and existing state-of-the-art algorithms in runtime and sample efficiency.