Quantifying randomness in real networks.
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.
CAIDA, University of California San Diego, San Diego, California 92093, USA.|Information Engineering Department, University of Pisa, Pisa 56122, Italy.
Chiara
C
Orsini
Scientific Computing Laboratory, Institute of Physics Belgrade, University of Belgrade, Belgrade 11080, Serbia.|Department of Biomedical Engineering and Computational Science, Aalto University School of Science, Helsinki 00076, Finland.
Marija M
MM
Dankulov
Departament de Física Fonamental, Universitat de Barcelona, Barcelona 08028, Spain.
Pol
P
Colomer-de-Simón
Communication and Distributed Systems group, Institute of Computer Science and Applied Mathematics, University of Bern, Bern 3012, Switzerland.
Almerima
A
Jamakovic
Palo Alto Research Center, Palo Alto, California 94304, USA.
Priya
P
Mahadevan
Google, Mountain View, California 94043, USA.
Amin
A
Vahdat
Department of Physics and Texas Center for Superconductivity, University of Houston, Houston, Texas 77204, USA.|Max Planck Institut für Physik komplexer Systeme, Dresden 01187, Germany.
Kevin E
KE
Bassler
Department of Physics and Interdisciplinary Center for Network Science and Applications, University of Notre Dame, Notre Dame, IN 46556, USA.
Zoltán
Z
Toroczkai
Departament de Física Fonamental, Universitat de Barcelona, Barcelona 08028, Spain.
Marián
M
Boguñá
IMT Alti Studi, Lucca 55100, Italy.
Guido
G
Caldarelli
Department of Computer Science, Aalto University School of Science, Helsinki 00076, Finland.
Santo
S
Fortunato
CAIDA, University of California San Diego, San Diego, California 92093, USA.|Department of Physics, Department of Mathematics, Department of Electrical and Computer Engineering, Northeastern University, Boston, Massachusetts 02115, USA.
Dmitri
http://orcid.org/0000-0001-9478-8182
D
Krioukov