Computing the Gromov Hyperbolicity of Graphs

Definition

The hyperbolicity of a graph G has been defined by Gromov [Gromov87] as the smallest δ such that dist(u,v)+dist(x,y) - max { dist(u,x)+dist(v,y), dist(u,y)+dist(v,x) } ≤ 2δ, for all u,v,x,y ∈ V.

Download

  • New: (2021) Implementations in C++ of the algorithms proposed in [BCCM15], [CCL15], [CNV21] and [CNV22] are on gitlab (and [CNV21c]).
     
  • (2015) Implementations of the exact algorithms proposed in [BCCM15] and [CCL15] are available in Sage (Python/Cython)
     
  • (2013) Implementation in C of the exact algorithm described in [CCL15] for computing the hyperbolicity of a graph, and a set of heuristics.
    The program is provided 'as is', with absolutely no warranty. It is written in C and has been tested on several linux and OSX computers. Note that the program uses the OpenMP library and assumes it is installed on your system. You may use and distribute this code, provided that you cite the paper describing our algorithms, [CCL15].
      → hyperbolicity.zip. The archive contains a README file, the C source code, and a simple test graph.

References

  • [BCMM15] M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. On Computing the Hyperbolicity of Real-World Graphs. 23rd Annual European Symposium on Algorithms (ESA), Sep 2015, Patras, Greece. pp.215-226, [doi:10.1007/978-3-662-48350-3_19] [hal].
  • [CCL15] N. Cohen, D. Coudert, and A. Lancin. On computing the Gromov hyperbolicity. ACM Journal on Experimental Algorithmics, 2015. [doi:10.1145/2780652]
  • [CCL12] N. Cohen, D. Coudert, and A. Lancin. Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs. Research Report RR-8074, Sep. 2012. [http://hal.inria.fr/hal-00735481]
  • [CNV21] D. Coudert, A. Nusser and L. Viennot. Enumeration of far-apart pairs by decreasing distance for faster hyperbolicity computation [Research Report] Inria; I3S, UniversitĂ© CĂ´te d'Azur. 2021. [hal] [pdf]
  • [CNV21c] D. Coudert, A. Nusser and L. Viennot. Hyperbolicity, 2021, (link Software Heritage)
  • [CNV22] D. Coudert, A. Nusser and L. Viennot. Hyperbolicity Computation through Dominating Sets. Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Jan 2022, Westin Alexandria Old Town, United States.
  • [Gromov87] M. Gromov. Hyperbolic groups. Essays in Group Theory, 8:75-263, 1987. (pdf)