Skip to Main content Skip to Navigation
Journal articles

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

Michele Borassi 1 Emanuele Natale 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks. The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time |E| 1 2 +o (1) with high probability, obtaining a significant speedup with respect to the Θ(|E|) worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the k most central nodes. Furthermore, our analysis is general, and it might be extended to other settings.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download
Contributor : Emanuele Natale <>
Submitted on : Thursday, July 11, 2019 - 5:01:27 PM
Last modification on : Tuesday, May 26, 2020 - 6:50:53 PM


Files produced by the author(s)




Michele Borassi, Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. ACM Journal of Experimental Algorithmics, Association for Computing Machinery, 2019, 24 (1), ⟨10.1145/3284359⟩. ⟨hal-02043367⟩



Record views


Files downloads