Fast Approximation of Centrality and Distances in Hyperbolic Graphs

International audienceWe show that the eccentricities (and thus the centrality indices) of all vertices of a δhyperbolicgraph G = (V, E) can be computed in linear time with an additive one-sided error of atmost cδ, i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time anestimate ê(v) of its eccentricity eccG(v) such that eccG(v) ≤ ê(v) ≤ eccG(v) + cδ for a small constantc. 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 aninteresting monotonicity property of the eccentricity function of hyperbolic graphs: the closer a vertexis to the center of G, the smaller its eccentricity is. We also show that the distance matrix of G with anadditive one-sided error of at most c′δ can be computed in $O(|V |^2log^2|V |)$ time, where c′ < c is a smallconstant. Recent empirical studies show that many real-world graphs (including Internet applicationnetworks, web networks, collaboration networks, social networks, biological networks, and others) havesmall hyperbolicity. So, we analyze the performance of our algorithms for approximating centrality anddistance matrix on a number of real-world networks. Our experimental results show that the obtainedestimates are even better than the theoretical bounds