Quantifying randomness in real networks

Abstract

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.

References in corpus (15)

• Scale-free brain functional networks
• Classes of complex networks defined by role-to-role connectivity profiles
• Triadic closure as a basic generating mechanism of communities in complex networks
• The entropy of randomized network ensembles
• Random graphs containing arbitrary distributions of subgraphs
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Systematic Topology Analysis and Generation Using Degree Correlations
• Clustering in complex networks. II. Percolation properties
• On the rich-club effect in dense and weighted networks
• Unbiased sampling of network ensembles
• Graph Annotations in Modeling Complex Network Topologies
• Exact sampling of graphs with prescribed degree correlations
• Fast and accurate determination of modularity and its effect size
• Optimization in Networks
• Structure of n-clique networks embedded in a complex network

Cited by in corpus (52)

• Networks beyond pairwise interactions: structure and dynamics
• The Statistical Physics of Real-World Networks
• Nestedness in complex networks: Observation, emergence, and implications
• Network Geometry
• Epidemic spreading on complex networks with community structures
• Scale-free Networks Well Done
• The hidden geometry of weighted complex networks
• Clustering implies geometry in networks
• Construction of and efficient sampling from the simplicial configuration model
• Low Algorithmic Complexity Entropy-deceiving Graphs
• Randomized reference models for temporal networks
• Network community detection using modularity density measures
• Reconstructing networks
• Emergence of dynamic properties in network hyper-motifs
• Higher order assortativity in complex networks
• Randomizing hypergraphs preserving degree correlation and local clustering
• Meta-validation of bipartite network projections
• Network nestedness as generalized core-periphery structures
• Separating Polarization from Noise: Comparison and Normalization of Structural Polarization Measures
• Randomizing growing networks with a time-respecting null model
• Lower bound of assortativity coefficient in scale-free networks
• Percolation and the effective structure of complex networks
• A general formulation of long-range degree correlations in complex networks
• Testing biological network motif significance with exponential random graph models
• Modeling framework unifying contact and social networks
• Weighted hypersoft configuration model
• Structure of percolating clusters in random clustered networks
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• Entropy of labeled versus unlabeled networks
• Grand canonical ensembles of sparse networks and Bayesian inference
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy
• Analytic solution of the two-star model with correlated degrees
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Emergence of Long-Range Correlations in Random Networks
• Compression-based inference of network motif sets
• Fundamental Structures in Dynamic Communication Networks
• Damage Maximization for Combat Network with Limited Costs
• Trust based attachment
• On the Privacy of dK-Random Graphs
• An algebraic Monte-Carlo algorithm for the Partition Adjacency Matrix realization problem
• Asymptotically Optimal Adversarial Strategies for the Probability Estimation Framework
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Revisiting finite size effect of percolation in degree correlated networks
• Alice and the Caterpillar: A more descriptive null model for assessing data mining results
• Interventions with Inversity in Unknown Networks Can Help Regulate Contagion
• Investigating cognitive ability using action-based models of structural brain networks
• Network Sparsification via Degree- and Subgraph-based Edge Sampling
• Hoeffding-type decomposition for $U$-statistics on bipartite networks
• Social Graph Restoration via Random Walk Sampling
• Transfer and routing of Gaussian states through quantum complex networks with and without community structure
• Mapping structural diversity in networks sharing a given degree distribution and global clustering: Adaptive resolution grid search evolution with Diophantine equation-based mutations