2021/04/26 by David Coudert, Coudert, David, André Nusser +3 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2104.12523
openalex publication_date 2021/04/26 · openalex created_date 2022/11/06 · openalex updated_date 2026/07/28
Hyperbolicity is a graph parameter which indicates how much the shortest-path\ndistance metric of a graph deviates from a tree metric. It is used in various\nfields such as networking, security, and bioinformatics for the classification\nof complex networks, the design of routing schemes, and the analysis of graph\nalgorithms. Despite recent progress, computing the hyperbolicity of a graph\nremains challenging. Indeed, the best known algorithm has time complexity\nO(n3.69), which is prohibitive for large graphs, and the most efficient\nalgorithms in practice have space complexity O(n2). Thus, time as well as\nspace are bottlenecks for computing hyperbolicity.\n In this paper, we design a tool for enumerating all far-apart pairs of a\ngraph by decreasing distances. A node pair (u, v) of a graph is far-apart if\nboth v is a leaf of all shortest-path trees rooted at u and u is a leaf\nof all shortest-path trees rooted at v. This notion was previously used to\ndrastically reduce the computation time for hyperbolicity in practice. However,\nit required the computation of the distance matrix to sort all pairs of nodes\nby decreasing distance, which requires an infeasible amount of memory already\nfor medium-sized graphs. We present a new data structure that avoids this\nmemory bottleneck in practice and for the first time enables computing the\nhyperbolicity of several large graphs that were far out-of-reach using previous\nalgorithms. For some instances, we reduce the memory consumption by at least\ntwo orders of magnitude. Furthermore, we show that for many graphs, only a very\nsmall fraction of far-apart pairs have to be considered for the hyperbolicity\ncomputation, explaining this drastic reduction of memory.\n As iterating over far-apart pairs in decreasing order without storing them\nexplicitly is a very general tool, we believe that our approach might also be\nrelevant to other problems.\n