2014/02/14 by Muad Abu‐Ata, Abu-Ata, Muad, Feodor F. Dragan +1
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Peer-to-Peer Network Technologies #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1402.3364
openalex publication_date 2014/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Based on solid theoretical foundations, we present strong evidences that a number of real-life networks, taken from different domains like Internet measurements, biological data, web graphs, social and collaboration networks, exhibit tree-like structures from a metric point of view. We investigate few graph parameters, namely, the tree-distortion and the tree-stretch, the tree-length and the tree-breadth, the Gromov's hyperbolicity, the cluster-diameter and the cluster-radius in a layering partition of a graph, which capture and quantify this phenomenon of being metrically close to a tree. By bringing all those parameters together, we not only provide efficient means for detecting such metric tree-like structures in large-scale networks but also show how such structures can be used, for example, to efficiently and compactly encode approximate distance and almost shortest path information and to fast and accurately estimate diameters and radii of those networks. Estimating the diameter and the radius of a graph or distances between its arbitrary vertices are fundamental primitives in many data and graph mining algorithms.