Quantifying randomness in real networks
arXiv:1505.07503 · doi:10.1038/ncomms9627
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 -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 -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 -random graphs.
References in corpus (40)
- The structure and function of complex networks
- Random graphs with arbitrary degree distributions and their applications
- Scale-free brain functional networks
- Detecting rich-club ordering in complex networks
- The statistical mechanics of networks
- Popularity versus Similarity in Growing Networks
- Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
- Classes of complex networks defined by role-to-role connectivity profiles
- Highly clustered scale-free networks
- Pattern Detection in Complex Networks: Correlation Profile of the Internet
- The topological relationship between the large-scale attributes and local interaction patterns of complex networks
- Generic scale of the "scale-free" growing networks
- Triadic closure as a basic generating mechanism of communities in complex networks
- Estimating and understanding exponential random graph models
- The entropy of randomized network ensembles
- Analytical maximum-likelihood method to detect patterns in real networks
- Random graphs containing arbitrary distributions of subgraphs
- Efficient and exact sampling of simple graphs with given arbitrary degree sequence
- Random graphs with a given degree sequence
- All scale-free networks are sparse
- Tuning clustering in random networks with arbitrary degree distributions
- Systematic Topology Analysis and Generation Using Degree Correlations
- Clustering in complex networks. II. Percolation properties
- Motifs emerge from function in model gene regulatory networks
- On the rich-club effect in dense and weighted networks
- Unbiased sampling of network ensembles
- Deciphering the global organization of clustering in real complex networks
- Clustering Drives Assortativity and Community Structure in Ensembles of Networks
- Constrained Markovian dynamics of random graphs
- Constructing and sampling directed graphs with given degree sequences
- Graph Annotations in Modeling Complex Network Topologies
- Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
- Fast and accurate determination of modularity and its effect size
- Exact sampling of graphs with prescribed degree correlations
- Reducing Degeneracy in Maximum Entropy Models of Networks
- On Realizations of a Joint Degree Matrix
- Optimization in Networks
- Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
- Structure of n-clique networks embedded in a complex network
- Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
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 -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 -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