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

https://hal.inria.fr/hal-02043367
Contributor : Emanuele Natale <>
Submitted on : Thursday, July 11, 2019 - 5:01:27 PM
Last modification on : Saturday, July 20, 2019 - 3:58:01 PM

File

kadabra_1604.08553.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

180

Files downloads

406