Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
On Computing the Gromov Hyperbolicity
View through CrossRef
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
(
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 depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is
O
(
n
4
), 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.
Association for Computing Machinery (ACM)
Title: On Computing the Gromov Hyperbolicity
Description:
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
(
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 depends on the distribution of distances and on the actual value of the hyperbolicity.
Although its worst case runtime is
O
(
n
4
), 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.
Related Results
Hyperbolicity cones are amenable
Hyperbolicity cones are amenable
AbstractAmenability is a notion of facial exposedness for convex cones that is stronger than being facially dual complete (or ‘nice’) which is, in turn, stronger than merely being ...
Discrete Superior Hyperbolicity in Chaotic Maps
Discrete Superior Hyperbolicity in Chaotic Maps
In the last few decades, the dynamics of one-dimensional chaotic maps have gained the tremendous attention of scientists and scholars due to their remarkable properties such as per...
A quantitative relative index theorem and Gromov’s conjectures on positive scalar curvature (with an appendix by Jinmin Wang and Zhizhang Xie)
A quantitative relative index theorem and Gromov’s conjectures on positive scalar curvature (with an appendix by Jinmin Wang and Zhizhang Xie)
In this paper, we prove a quantitative relative index theorem. It provides a conceptual framework for studying some conjectures and open questions of Gromov on positive scalar curv...
Two Notions of Hyperbolicity in Complex Codimension One for Compact Complex Manifolds
Two Notions of Hyperbolicity in Complex Codimension One for Compact Complex Manifolds
Deux notions d'hyperbolicité en codimension complexe un pour les variétés complexes compactes
Cette thèse est consacrée à l'introduction de deux notions nouvelles d...
Hyperbolicity of First Order Quasi-Linear Equations
Hyperbolicity of First Order Quasi-Linear Equations
The theorem about equivalence of the strong hyperbolicity concept and the Friedrichs hyperbolicity concept for partial quasi-linear differential equations of the first order is pro...
A Comparative Study between Kähler and Non-Kähler Hyperbolicity
A Comparative Study between Kähler and Non-Kähler Hyperbolicity
Abstract
In this note, we establish a connection between SKT and balanced hyperbolicity, highlighting their relationship with Kähler hyperbolicity in the sense of Gromov.
M...
CLOUD COMPUTING - NAVIGATING THE DIGITAL SKY
CLOUD COMPUTING - NAVIGATING THE DIGITAL SKY
“Cloud Computing – Navigating the Digital Sky” is an extensive guide designed to provide a thorough understanding of cloud computing, an essential technology in today’s digital age...
Adoption Strategy for Cloud Computing in Kenyan Research Institutions
Adoption Strategy for Cloud Computing in Kenyan Research Institutions
Cloud computing has transformed the aspect of distributed computing from many other prevailing methods by offering more unlimited benefits, like cutting down computing costs and al...