Quantifying Randomness in Real Networks

Chiara Orsini, Marija M. Dankulov, Pol Colomer-de-Simón, Almerima Jamakovic, Priya Mahadevan, Amin Vahdat, Kevin E. Bassler, Zoltán Toroczkai, Marián Boguñá, Guido Caldarelli, Santo Fortunato & Dmitri Krioukov
Nature Communications
6:8627, (2015)
October 20, 2015


Represented as  graphs, real networks are intricate combinations of order and disorder.  Fixing some of the structural properties of network models to their values  observed in real networks, many other properties appear as statistical  consequences of these fixed observables, plus randomness in other respects.  Here we employ the dk-series, a complete set of basic characteristics of the  network structure, to study the statistical dependencies between different  network properties. We consider six real networks the Internet, US airport  network, human protein interactions, technosocial web of trust, English word  network, and an fMRI map of the human brain and find that many important  local and global structural properties of these networks are closely reproduced  by dk-random graphs whose degree distributions, degree correlations and  clustering are as in the corresponding real network. We discuss important  conceptual, methodological, and practical implications of this evaluation of  network randomness, and release software to generate dk-random graphs.

Related publications