Fast Approximation of Centrality and Distances in Hyperbolic Graphs

We show that the eccentricities (and thus the centrality indices) of all vertices of a \(\delta \)-hyperbolic graph \(G=(V,E)\) can be computed in linear time with an additive one-sided error of at most \(c\delta \), i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimate \(\hat{e}(v)\) of its eccentricity \(ecc_G(v)\) such that \(ecc_G(v)\le \hat{e}(v)\le ecc_G(v)+ c\delta \) for a small constant c. We prove that every \(\delta \)-hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, \(ecc_G(v)\le ecc_T(v)\le ecc_G(v)+ c\delta \). We also show that the distance matrix of G with an additive one-sided error of at most \(c'\delta \) can be computed in \(O(|V|^2\log ^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.