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.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-02043367
Contributeur : Emanuele Natale <>
Soumis le : jeudi 11 juillet 2019 - 17:01:27
Dernière modification le : samedi 20 juillet 2019 - 15:58:01

Fichier

kadabra_1604.08553.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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⟩

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

444