Source-linked AI summary
Quantifying randomness in real networks
Chiara Orsini, Marija Mitrović Dankulov, Almerima Jamakovic, Priya Mahadevan, Pol Colomer-de-Simón, Amin Vahdat, Kevin E. Bassler, Zoltán Toroczkai, Marián Boguñá, Guido Caldarelli, Santo Fortunato, Dmitri Krioukov
TL;DR
The paper asks which network properties are independent versus statistical consequences of others. It uses the dk-series to test real networks and finds that many local, mesoscopic, and global properties are reproduced by low-d dk-random graphs, with implications for network modeling.
Problem
The paper addresses how dependencies among network properties affect attempts to explain real-network structure and function.
Method
The paper uses the inclusive, converging dk-series to construct null-model ensembles that preserve increasingly detailed degree- and subgraph-based structure.
Results
Many considered networks are dk-random with d ≤2.5, so their local, mesoscopic, and global properties are reproduced by degree distributions, correlations, and clustering.
Takeaways & Limitations
When target properties are dk-random at low d, dk-random graph generators may replace mission-specific topology generators for reproducing them.
Takeaways & Limitations
Practical 3k-random graph analysis is limited because no feasible construction algorithm exists, rewiring may be non-ergodic, and the ensemble is not analytically tractable.
Abstract
from arXiv · showhide
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.
Introduction
Network properties can be statistically dependent, so assessing whether a feature is meaningful requires testing it against null models that preserve other structural properties. The dk-series provides a systematic basis for making these comparisons and identifying properties not explained by basic degree- and subgraph-based characteristics.
- Network representations support analysis of structural properties that may affect the functions of the systems they represent.
- A property X may be enforced by another property Y, making X a statistical consequence rather than an independent network feature.High density, for example, necessarily produces short path lengths and high clustering in the cited cortical network.
- Y-random graphs test whether X is typical among graphs sampled uniformly while preserving property Y.If X is typical, Y can explain X; if not, the test only shows that Y cannot explain X.
- Choosing a null-model property is unavoidable because no unique or universal base property Y exists.Degree distribution is common, but it is only one of infinitely many possible ways to specify a null model.
- The dk-series supplies a converging, systematic sequence of null models that progressively characterizes degree- and subgraph-based network structure.Its ensembles preserve distributions of differently sized subgraphs with node degrees labeled as in the real network.
- dk-series analysis can identify properties that cannot be reduced to basic local degree- or subgraph-based characteristics and may therefore relate to network function.
Results
The dk-series provides increasingly detailed, inclusive null models for testing which network properties are statistically explained by lower-order structure. Across six real networks, 2.5k-random graphs reproduced many microscopic, mesoscopic, and macroscopic properties, although convergence was slow or absent for some brain and community-structure properties.
- dk-series framework: The dk-series forms inclusive, convergent null models whose increasing d preserves all lower-order dk-distributions while adding structural detail.At d = N, only the original graph remains, whereas lower d yields increasingly random ensembles.
- dk-series framework: The dk-distributions progress from average degree and degree distribution to joint degree patterns and degree-labeled subgraphs.The 0k-distribution is average degree; 1k is the degree distribution; 2k counts edges between degree classes, while higher d counts larger degree-labeled subgraphs.
- Empirical results: 2.5k-random graphs fixed degree distribution and degree-dependent clustering while capturing many other important properties of the corresponding real networks.The experiments covered six networks: US air transportation, human-brain fMRI, Internet autonomous systems, PGP trust, human proteins, and English word adjacency.
- Empirical results: At d = 2.5, subgraph concentrations, k-coreness, k-density, and spectral properties generally converged, although the Internet’s Fiedler value was an exception.Subgraph concentrations improved especially from 2.1k to 2.5k, while mesoscopic and macroscopic properties converged more slowly.
- Empirical results: Some properties and network types remained poorly captured: many brain-network properties converged slowly or not at all, as did community structure in most tested cases.This limits the interpretation of convergence as a universal explanation for every structural property.
Discussion
The results show that low-order dk-randomizations reproduce many network properties, while brain organization and community structure remain non-random. The interpretation is limited by the absence of a uniquely preferred null model and by sampling caveats for higher-order ensembles.
- Non-random structure: Brain hemispheric separation is not expected to survive low-d dk-randomization because it is a non-local global feature.The considered brain network has two relatively weakly connected parts.
- Non-random structure: Community structure is not robust to dk-randomizations because cluster organization contains complex non-local features such as internal-link densities and boundaries.The randomizations are expected to affect these features even at high d.
- Results: In most cases, d ≤2.5 reproduces local, mesoscopic, and global network properties, making them effective consequences of degree distributions, correlations, and clustering.Features that remain non-random require separate explanations or different null models.
- Null-model choice: There is no a priori preferred null model, and structural significance claims require justification because properties, especially motif frequencies, depend strongly on d.A chosen null model must therefore be matched to the feature being evaluated.
- Practical implication: Topology generators should first test whether target properties are dk-random, since low-d properties may not require mission-specific generators.The dk-random graph algorithms can be used for this purpose.
- Caveat: The approach has no proof that d = 2.1 and d = 2.5 algorithms sample graphs uniformly from their ensembles.The relevant ensembles and rewiring processes can suffer from degeneracy and hysteresis.
Supplementary Figures
The supplementary figures compare structural distributions and network properties in real networks with their dk-randomizations. They cover degree-based, subgraph, centrality, distance, and distributional comparisons.
- Degree-based properties: Degree distributions are compared between real networks and their dk-randomizations.
- Degree-based properties: Average nearest neighbor degrees of nodes with a given degree are compared between real networks and their dk-randomizations.This is the ANND projection of degree correlations.
- Clustering: Average clustering of nodes with a given degree is compared between real networks and their dk-randomizations.
- Subgraph properties: Subgraph concentration differences and common-neighbor distributions are compared between real networks and their dk-randomizations.
- Mesoscopic and centrality properties: K-coreness, k-denseness, and average betweenness by degree are compared between real networks and their dk-randomizations.
- Global and distributional comparisons: Shortest-path distance distributions and Kolmogorov-Smirnov distances are compared between real networks and their dk-randomizations.
Supplementary Tables
The supplementary tables document spectral properties, network composition, randomization parameters, and the relationship between dk-series and d-series.
- Spectral properties: Largest eigenvalues are averaged across realizations for each d, with standard deviations in parentheses.
- Spectral properties: Spectral gaps are averaged across realizations for each d, with standard deviations in parentheses.
- Network data: The considered networks, their abbreviations, and their numbers of nodes and links are listed.
- Randomization parameters: Parameters for dk-randomization and 2.1k/2.5k-targeting 2k-preserving rewiring processes are reported.The parameters include M, average clustering, and degree-conditioned average clustering.
- Series comparison: The relationship between the dk-series and d-series is summarized.
Supplementary Notes
The supplementary notes define network properties used in the analysis and relate them to the dk-series. They introduce degree distributions and degree-correlation measures with their normalization and projection relationships.
- 1k-distribution: The distribution P(k) of node degrees is the 1k-distribution.
- 1k-distribution: P(k) is normalized using the total number of nodes, and the 1k-distribution fully defines the average degree but not vice versa.
- 2k-distribution: The average nearest-neighbor degree of nodes with degree k is a projection of the joint degree distribution P(k, k′), the 2k-distribution.
- 2k-distribution: The joint degree distribution counts links between node-degree classes and is normalized over degree pairs.It is defined using N(k, k′) and the total number of links M.
1.3 Clustering
Clustering and subgraph concentrations are organized through degree-labeled distributions, with higher-order dk-distributions fixing increasingly detailed local structure. The paper compares these concentrations directly across dk-random graph ensembles rather than using fixed-null-model z-scores.
- Clustering: The 3k-distribution separates wedges and triangles by the degrees of their participating nodes.Its wedge component is symmetric in the two non-central degrees, while the triangle component is symmetric in all three degrees.
- Clustering: The 3k-distribution defines the 2k-distribution, but the reverse does not hold.This makes 3k a strictly more detailed characterization of local structure than 2k.
- Subgraph frequencies: The concentration of size-3 subgraphs is fixed exactly only by the 3k-distribution, while size-4 concentrations require the 4k-distribution.Size-3 connected subgraphs comprise two non-isomorphic types: triangles and wedges.
- Subgraph frequencies: The paper compares subgraph concentrations directly because z-scores are tailored to one fixed null model, whereas the dk-series contains a sequence of null models indexed by d.The authors note that the definitions do not readily provide estimates of how quickly subgraph frequencies converge across the series.
1.5 Common neighbors
Common-neighbor structure is measured through edge multiplicity and its distribution, while k-core and k-dense decompositions provide related local-structure summaries. The dk-series does not exactly fix these recursive decompositions at the lower listed orders.
- Common neighbors: The common-neighbor distribution gives the probability that connected node pairs have m common neighbors.For a connected edge, m is its multiplicity and is computed from the adjacency matrix.
- Common neighbors: The common-neighbor distribution is fixed exactly only by the 3k-distribution.Thus, lower-order constraints need not determine this property exactly.
- k-coreness and k-denseness: A k-core is a maximal connected subgraph whose nodes each have degree at least k within that subgraph.The decomposition is a nested set of subgraphs induced by nodes with the same k-coreness.
- k-coreness and k-denseness: A k-dense subgraph is a maximal connected subgraph whose connected node pairs each have at least k − 1 common neighbors within the subgraph.Its nested decomposition is induced by edges with the same k-denseness.
- k-coreness and k-denseness: The dk-distributions with d = 0, 1, 2, 2.1, 2.5 do not exactly fix k-core or k-dense distributions because these decompositions are recursive.Both decompositions begin from local node or edge properties but apply them recursively.
1.8 Shortest path distance
Shortest-path structure is characterized by hop-length distributions, average distance, and network diameter, alongside spectral quantities tied to network dynamics. The study applies dk-series analysis across six networks spanning transportation, biological, language, communication, and brain data.
- Shortest path distance: The distance distribution records the hop lengths of shortest paths between node pairs.The average distance summarizes these pairwise distances, while the diameter is the maximum hop distance.
- Spectral properties: The adjacency matrix’s largest eigenvalue relates to spreading speed, while the spectral gap determines random-walk convergence speed.These spectral quantities connect network structure with dynamical processes.
- Networks: The analysis covers the US airport, fMRI brain, word-adjacency, Internet, PGP trust, and human protein-interaction networks.The networks represent transportation, biological, language, communication, and social or brain systems.
- Method: The dk-randomization and p-targeting dk-preserving rewiring processes use network-specific parameters reported in Table 4.The passage identifies the parameter table but does not enumerate its values.
Supplementary Note 3: Results
Across six real networks and multiple structural properties, dk-random graphs reproduce many observed distributions once the corresponding degree-labeled constraints are imposed. The required order varies by property and network, with the brain network often remaining hardest to reproduce.
- Degree distribution: d ≥1 dk-random graphs reproduce real-network degree distributions exactly, whereas 0k-randomizations are far off.This follows because the 1k-distribution is the degree distribution.
- Average nearest neighbor degree: d ≥2 dk-random graphs reproduce average neighbor degrees exactly, while 1k graphs are generally closer than 0k graphs.In WORDS, INTERNET, and PPI, even 1k graphs show no noticeable ANND difference from the real networks.
- Clustering: 2.5k-random graphs match degree-dependent clustering, while AIR matches at 2.1k and WORDS nearly matches at 1k.For d < 2.5, clustering differs substantially in many cases.
- Subgraph frequencies: 2k-random graphs reproduce subgraph frequencies in most networks, but BRAIN and PGP require d = 2.5.The result shows that the order needed for subgraph reproduction is network-dependent.
- Common neighbors: 1k-random graphs reproduce common-neighbor distributions except for BRAIN, which requires d = 2, and PGP, which requires d = 2.5.The required order therefore differs across networks for this local property.
- k-coreness and k-denseness: 2.5k-random graphs reproduce all k-denseness distributions and all k-coreness distributions except those of PGP and BRAIN, which require d = 2.5.AIR and WORDS already reproduce k-denseness with 2k-random graphs.
- Betweenness: BRAIN betweenness is not approximated even at 2.5k, whereas INTERNET betweenness is reproduced at 1k and the other networks are similar at 2k or 2.5k.PGP requires all constraints imposed by the 2.5k-distribution.
- Shortest path distance: INTERNET and WORDS distance distributions are reproduced at 1k, but BRAIN remains unreproduced even at d = 2.5.The same d = 2.5 value suffices for all the other networks.
Supplementary Discussion
The dk-series preserves degree labels on subgraphs, making its successive distributions inclusive and systematically informative. Unlike the d-series, it converges faster because higher-order dk-distributions retain preceding information and can distinguish topologies that share aggregate subgraph counts.
- Series definitions: The dk-series records d-sized subgraph distributions labeled by node degrees, whereas the d-series ignores degree information.The distinction explains why the dk-series retains more structural information at each level.
- Inclusiveness: The (d+1)k-distribution contains the full dk-distribution plus additional information, making the dk-series inclusive.The corresponding inclusion does not hold for the d-series.
- Topology examples: W = N −2 in a chain and W = (N −1)(N −2)/2 in a star, while both networks have M = N −1 edges and no triangles.The same edge count therefore does not distinguish these two topologies through the d-series statistics shown.
- Limits of the d-series: The d-series is not inclusive because successive elements convey unrelated or only loosely related topological information.Although it converges at d = N, this convergence is slower than for the dk-series.
- Topology examples: The 3k-distributions define the chain and star topologies exactly, whereas their wedge and triangle counts do not uniquely fix topology.Many non-isomorphic graphs can share the same (W, T) counts.
- Why degree labels matter: Node degrees identify subgraph locations, speeding convergence with d and making the dk-series inclusive and systematic.This degree information is the structural feature that distinguishes the dk-series from the d-series in this respect.
Supplementary Methods
The methods generate dk-random graphs through degree-preserving rewiring and, when needed, simulated-annealing targeting of another network property. The rewiring rules vary by preserved dk-distribution, while targeting stops when the property matches or acceptance falls below a threshold.
- dk-randomization: dk-randomization swaps edges in the original graph while preserving a selected dk-distribution.Its inputs include the original graph, the number of rewirings, and the d index identifying the preserved distribution.
- Rewiring rules: For d = 0, the method replaces a random edge with a randomly selected non-edge.This rewiring changes the connection while following the d = 0 rule.
- Rewiring rules: For d = 1, two edges are rewired by cross-connecting their endpoints when the proposed edges do not already exist.The move is discarded if either proposed cross-edge is already present.
- Rewiring rules: For d = 2, the rewired edges are selected from endpoints with equal degrees before applying the same non-edge checks and cross-connection.The equal-degree condition is the additional constraint in this rule.
- Targeted rewiring: p-targeting dk-preserving rewiring uses simulated annealing after randomization to adjust a target property while retaining dk constraints.The procedure decreases temperature by βfactor, reducing acceptance of rewirings that increase energy.
- Stopping conditions: The targeting phase ends when the target-property energy reaches zero or the accepted-rewiring percentage falls below α.Energy zero means the rewired graph matches the original graph's target-property value.
- Implementation: The authors release software implementing the dk-randomization algorithms for generating dk-random graphs.The package is described as freely available.