Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs

Nathann Cohen 1 David Coudert 2, 3 Aurélien Lancin 2, 3
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 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
Résumé : Soit G un graphe connexe et soit d(a, b) la distance entre les sommets a et b dans le graphe. Le graphe G est dit δ-hyperbolic si pour tout quadruplet a, b, c, d de sommets d G, les deux plus grandes des sommes S1 = d(a, b)+d(c, d), S2 = d(a, c)+d(b, d), et S3 = d(a, d)+d(b, c) diffèrent d'au plus 2δ. Cette valeur peut être déterminé en temps O(n^4), ce qui est souvent inaccessible pour les grands graphes. Nous proposons un nouvel algorithme exact pour calculer l'hyperbolicité sur des graphes de grande taille. La complexité en temps de cet algorithme est fonction de la taille de la plus grande composante bi-connexe du graphe, de la distribution des plus courts chemins dans cette composante et de la valeur de l'hyperbolicité. Dans le pire cas, cet algorithme prendra un temps en O(n^4). Cependant, l'algorithme est bien plus efficace en pratique. Il nous a en effet permis de calculé la valeur exacte de l'hyperbolicité pour l'ensemble des cartes Internet CAIDA et DIMES. Nous proposons également un algorithme approché avec un facteur multiplicatif ou avec une constante additive donné en entrée. Enfin, nous analysons la complexité temporelle de notre algorithme pour des classes particulières de graphes.
Type de document :
Rapport
[Research Report] RR-8074, INRIA. 2012


https://hal.inria.fr/hal-00735481
Contributeur : David Coudert <>
Soumis le : vendredi 15 mars 2013 - 14:41:05
Dernière modification le : samedi 17 septembre 2016 - 01:36:49

Fichier

RR-8074-v4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00735481, version 4

Collections

Citation

Nathann Cohen, David Coudert, Aurélien Lancin. Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs. [Research Report] RR-8074, INRIA. 2012. <hal-00735481v4>

Exporter

Partager

Métriques

Consultations de
la notice

616

Téléchargements du document

691