Metric tree‐like structures in real‐world networks: an empirical study. Issue 1 (25th August 2015)

• Record Type: Journal Article
• Authors: Abu‐Ata, Muad; Dragan, Feodor F.
• Is Part Of: Networks. Volume 67:Issue 1(2016)
• Page Start: 49
• Page End: 68
• Publication Date: 2015-08-25
• Subjects: large‐scale networks -- metric tree‐like structures -- hyperbolicity -- tree‐stretch -- tree‐distortion -- tree‐length -- tree‐breadth -- layering partition -- graph algorithms -- approximation algorithms; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21631
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : 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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(1), 49–68 2016