On computing the Gromov hyperbolicity

Nathann Cohen 1 David Coudert 2 Aurélien Lancin 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best known theoretical algorithm computing this parameter runs in O(n^3.69) time, which is prohibitive for large-scale graphs. In this paper, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is O(n^4), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances.
Type de document :
Article dans une revue
ACM Journal on Experimental Algorithmics, Association for Computing Machinery, 2015, 20 (1), pp.18. <10.1145/2780652>
Liste complète des métadonnées


https://hal.inria.fr/hal-01182890
Contributeur : David Coudert <>
Soumis le : mercredi 5 août 2015 - 11:17:47
Dernière modification le : jeudi 20 juillet 2017 - 09:30:07
Document(s) archivé(s) le : mercredi 26 avril 2017 - 08:31:22

Fichier

CCL15-no-format.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nathann Cohen, David Coudert, Aurélien Lancin. On computing the Gromov hyperbolicity. ACM Journal on Experimental Algorithmics, Association for Computing Machinery, 2015, 20 (1), pp.18. <10.1145/2780652>. <hal-01182890>

Partager

Métriques

Consultations de
la notice

368

Téléchargements du document

172