On computing the Gromov hyperbolicity
N Cohen, D Coudert, A Lancin - Journal of Experimental Algorithmics …, 2015 - dl.acm.org
N Cohen, D Coudert, A Lancin
Journal of Experimental Algorithmics (JEA), 2015•dl.acm.orgThe Gromov hyperbolicity is an important parameter for analyzing complex networks which
expresses how the metric structure of a network looks like a tree. It is for instance used to
provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs.
However, the best-known theoretical algorithm computing this parameter runs in O (n 3.69)
time, which is prohibitive for large-scale graphs. In this article, we propose an algorithm for
determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time …
expresses how the metric structure of a network looks like a tree. It is for instance used to
provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs.
However, the best-known theoretical algorithm computing this parameter runs in O (n 3.69)
time, which is prohibitive for large-scale graphs. In this article, we propose an algorithm for
determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time …
The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best-known theoretical algorithm computing this parameter runs in O(n3.69) time, which is prohibitive for large-scale graphs.
In this article, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is O(n4), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果