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

Description

Let G be a connected graph, and let d(a, b) denotes the shortest path distance between vertices a and b of G. The graph G is δ-hyperbolic if for any vertices a, b, c, d of G, the two largest of the three sums S1 = d(a,b) + d(c,d), S2 = d(a,c) + d(b,d), and S3 = d(a,d) + d(b,c) differ by at most 2δ. This can be determined in time O(n^4) which could be prohibitive for large graphs. In this document, we propose an exact algorithm for determining the hyperbolicity of a graph that is scalable for large graphs. The time complexity of this algorithm is a function of the size of the largest bi-connected component of the graph, of the shortest path distance distribution in this component and of the value of the hyperbolicity. In the worst case, the time complexity remains in O(n^4), but it is much faster in practice. Indeed, it allowed us to compute the exact hyperbolicity of all maps of the autonomous systems of the Internet provided by CAIDA and DIMES. We also propose both a multiplicative factor and an additive constant approximation algorithms. Finally, we also analyze further the time complexity of our exact algorithm for several class of graphs.

Abstract (French)

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.

Additional details