Premium
Metric tree‐like structures in real‐world networks: an empirical study
Author(s) -
AbuAta Muad,
Dragan Feodor F.
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21631
Subject(s) - tree (set theory) , computer science , mathematics , theoretical computer science , graph , tree structure , metric (unit) , partition (number theory) , algorithm , combinatorics , binary tree , operations management , economics
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