Fast Approximation of Centrality and Distances in Hyperbolic Graphs

Victor Chepoi (1) , Feodor F. Dragan (2) , Michel Habib (3, 4) , Yann Vaxès (5) , Hend Alrasheed (2)

1 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle
2 Kent State University
3 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
4 GANG - Networks, Graphs and Algorithms
5 LIS - Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon)

We show that the eccentricities (and thus the centrality indices) of all vertices of a δhyperbolic graph G = (V, E) can be computed in linear time with an additive one-sided error of at most cδ, i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimate ê(v) of its eccentricity eccG(v) such that eccG(v) ≤ ê(v) ≤ eccG(v) + cδ for a small constant c. We prove that every δ-hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, eccG(v) ≤ eccT (v) ≤ eccG(v) + cδ. These results are based on an interesting monotonicity property of the eccentricity function of hyperbolic graphs: the closer a vertex is to the center of G, the smaller its eccentricity is. We also show that the distance matrix of G with an additive one-sided error of at most c′δ can be computed in $O(|V |^2log^2|V |)$ time, where c′ < c is a small constant. Recent empirical studies show that many real-world graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity. So, we analyze the performance of our algorithms for approximating centrality and distance matrix on a number of real-world networks. Our experimental results show that the obtained estimates are even better than the theoretical bounds.

Domaines: Algorithme et structure de données [cs.DS]

Victor Chepoi, Feodor F. Dragan, Michel Habib, Yann Vaxès, Hend Alrasheed. Fast Approximation of Centrality and Distances in Hyperbolic Graphs. COCOA 2018 - 12th Annual International Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. pp.1-23, ⟨10.1007/978-3-540-27836-8_101⟩. ⟨hal-01955263⟩