Metric tree-like structures in real-world networks: an empirical study

Based on solid theoretical foundations, we present strong evidence that a number of real‐world networks, taken from different domains (such as Internet measurements, biological data, web graphs, and social and collaboration networks) exhibit tree‐like structures from a metric point of view. We investigate a few graph parameters, namely, the tree‐distortion and the tree‐stretch, the tree‐length and the tree‐breadth, Gromov's hyperbolicity, the cluster‐diameter and the cluster‐radius in a layering partition of a graph; such parameters capture and quantify this phenomenon of being metrically close to a tree. By bringing all those parameters together, we provide efficient means for detecting such metric tree‐like structures in large‐scale networks. We also show how such structures can be used. For example, they are helpful in efficient and compact encoding of approximate distance and almost shortest path information and in quick and accurate estimation of diameters and radii of those networks. Estimating the diameter and estimating the radius of a graph (or distances between arbitrary vertices) are fundamental primitives in many network and graph mining algorithms.