On Computing the Hyperbolicity of Real-World Graphs

Abstract : The (Gromov) hyperbolicity is a topological property of a graph, which has been recently applied in several different contexts, such as the design of routing schemes, network security, computational biology, the analysis of graph algorithms, and the classification of complex networks. Computing the hyperbolicity of a graph can be very time consuming: indeed, the best available algorithm has running-time O(n^{3.69}), which is clearly prohibitive for big graphs. In this paper, we provide a new and more efficient algorithm: although its worst-case complexity is O(n^4), in practice it is much faster, allowing, for the first time, the computation of the hyperbolicity of graphs with up to 200,000 nodes. We experimentally show that our new algorithm drastically outperforms the best previously available algorithms, by analyzing a big dataset of real-world networks. Finally, we apply the new algorithm to compute the hyperbolicity of random graphs generated with the Erdös-Renyi model, the Chung-Lu model, and the Configuration Model.
Type de document :
Communication dans un congrès
23rd Annual European Symposium on Algorithms (ESA), Sep 2015, Patras, Greece. Springer, 9294, pp.215-226, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-48350-3_19〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01199860
Contributeur : David Coudert <>
Soumis le : mercredi 16 septembre 2015 - 12:03:24
Dernière modification le : mercredi 14 décembre 2016 - 01:05:50
Document(s) archivé(s) le : mardi 29 décembre 2015 - 07:30:21

Fichier

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

Identifiants

Collections

Citation

Michele Borassi, David Coudert, Pierluigi Crescenzi, Andrea Marino. On Computing the Hyperbolicity of Real-World Graphs. 23rd Annual European Symposium on Algorithms (ESA), Sep 2015, Patras, Greece. Springer, 9294, pp.215-226, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-48350-3_19〉. 〈hal-01199860〉

Partager

Métriques

Consultations de
la notice

198

Téléchargements du document

308