Quantifying randomness in real networks

Introduction

• Network properties can affect system dynamics, and self-organization may favor efficient functions, so reverse engineering must test dependencies —for example, density can induce brain small-world structure.The paper notes that high density in a primate brain network entails short paths and high clustering, making its small-world property a consequence of density rather than an independent feature.Source: Introduction · p. 2
• Y-random graphs test whether X is typical among graphs constrained by Y; if so, Y explains X, while failure only shows that Y cannot explain X [13, 14].An atypical X under this null model does not establish that X is important, because some other property Z may explain it.Source: Introduction · pp. 2–3
• Degree distribution is a common null-model constraint for properties such as motifs, but it has no rigorous justification as a uniquely preferred choice.The paper argues that degree distribution is only one of infinitely many ways to specify a null model.Source: Introduction · p. 3
• The dk-series provides increasingly detailed null models, and six networks are largely reproduced when their degree distributions, degree correlations, and clustering are fixed.Its graph ensembles match distributions of degree-labeled subgraphs, generalizing null models that fix properties such as average degree, degree distribution, correlations, or clustering.Source: Introduction · p. 3
• The method also identifies properties that remain unexplained by degrees, correlations, and clustering and may therefore be related to network function.Such properties cannot be reduced to basic local degree- or subgraph-based characteristics.Source: Introduction · pp. 3–4

Results

• A systematic property series must be inclusive and converge to the network itself, allowing the minimal d that explains any property X to be identified.Once properties at that d are explained, inclusiveness means higher-d properties also have property X.Source: Results · p. 4

dk-series

• The dk-series uses degree-labeled subgraph distributions, progressing from average degree to degree distribution, degree correlations, and clustering, and is inclusive and convergent.Retaining degree labels makes the subgraph series inclusive; at d = N, the distribution specifies the network adjacency matrix.Source: dk-series · p. 5

dk-random graph sampling

• Because practical 3k sampling failed or was infeasible, the study sampled 20 graphs per network at d = 0, 1, 2, 2.1, and 2.5 using swaps and clustering-targeting rewiring.Sampling was not exactly uniform; the targeting algorithm was modified to ensure convergence in all cases.Source: dk-random graph sampling · pp. 9–10

Real versus dk-random networks

• In most cases, properties converged as d increased, and many showed no statistically significant difference from 2.5k-random graphs preserving degree distribution and degree-dependent clustering.The experiments covered six real networks and compared graphs with d = 0, 1, 2, 2.1, and 2.5.Source: Real versus dk-random networks · pp. 12–13
• At d = 2.5, subgraph concentrations and many mesoscopic and macroscopic properties converged, but mesoscopic and especially macroscopic properties generally converged more slowly.Subgraphs of size 3 and most of size 4 were reproduced well; k-coreness, k-density, and spectral properties converged in all cases except the Internet Fiedler value.Source: Real versus dk-random networks · p. 13, Figure 4 · p. 15, Figure 5 · p. 16
• Many brain-network properties converged slowly or not at all, and community-structure convergence was usually slow or nonexistent.The brain network was the exception to convergence of spectral properties at d = 2.5.Source: Real versus dk-random networks · pp. 12–13

Discussion

• The brain’s weakly connected halves are not reproduced by low-d randomizations, and its shortest-path and betweenness distributions differ drastically from those of the randomized graphs.Community structure is also not robust to dk-randomization: it disrupts cluster organization, whose variable internal-link densities and boundaries are complex non-local features.Source: Discussion · p. 18
• The authors propose that 3k constraints may cross an NP-hard satisfiability barrier, while locally evolving networks may have correlations below d = 3.They suggest the primate brain may instead reflect global constraints, citing dense connectivity across functional areas and a strong core-periphery structure centered on associative cortex.Source: Discussion · p. 18
• In most cases, dk-random graphs with d ≤2.5 reproduce local, mesoscopic, and global properties, making these properties effective consequences of degree distributions, correlations, and clustering.The authors argue that explanations should focus on how these degree-based features emerge; properties found to be non-random may need separate explanations or different null models.Source: Discussion · p. 18
• No null model is preferred a priori: motif frequencies and other properties can depend strongly on d, so choosing a model requires justification before claiming a feature matters for network function.The same structural feature must be compared between the real network and an ensemble of random graphs.Source: Discussion · p. 19
• For topology generation in biology or computer science, first test whether target properties are dk-random at low d; if so, dk-random generators may suffice.An extension of some algorithms handles networks with arbitrary link and node annotations, including directed or colored multilayer networks.Source: Discussion · p. 19
• Uniform sampling by the d = 2.1 and d = 2.5 algorithms is unproven, and rigorous treatment of global properties under sparse-network constraints above d = 2 remains difficult.The authors note that exact expected values are currently available only for simple properties in soft ensembles with d = 0, 1, or 2, and argue that rigorous methods for higher-d constraints are important future work.Source: Discussion · p. 19

Supplementary Figures

• Supplementary Figure 7 compares degree distributions in real networks and their dk-randomizations.Source: Figure 7 · p. 21
• Supplementary Figures 8 and 9 compare average nearest neighbor degrees and average clustering by node degree in real networks and their dk-randomizations.Source: Figure 8 · p. 22, Figure 9 · p. 23
• Supplementary Figures 10 and 11 show subgraph concentration differences and common neighbor distributions for real networks and their dk-randomizations.Source: Figure 10 · p. 24, Figure 11 · p. 25
• Supplementary Figures 12 and 13 compare k-coreness and k-denseness distributions in real networks and their dk-randomizations.Source: Figure 12 · p. 26, Figure 13 · p. 27
• Supplementary Figure 14 compares average betweenness by node degree in real networks and their dk-randomizations.Source: Figure 14 · p. 28
• Supplementary Figure 15 compares shortest path distance distributions in real networks and their dk-randomizations.Source: Figure 15 · p. 29
• Supplementary Figure 16 reports Kolmogorov-Smirnov distances between real networks and their dk-randomizations.Source: Figure 16 · p. 30

• Supplementary Table 1 reports largest eigenvalues, and Supplementary Table 2 reports spectral gaps, each averaged across realizations for each d with standard deviations in parentheses.Source: Table 1 · p. 31, Table 2 · p. 31
• Supplementary Table 3 lists the considered networks, their abbreviations, and their node and link counts.Source: Table 3 · p. 31

Network properties

• The notes describe properties measured in Supplementary Note 3 and their relations to the dk-series where meaningful.Source: Supplementary Note 1: Network properties · p. 33

1.1 Degree distribution

• The 1k-distribution P(k) is the distribution of node degrees k.Source: §1.1 · p. 33
• P(k) is normalized using the number of nodes of degree k and the total number of nodes.Source: §1.1 · p. 33
• The 1k-distribution fully determines average degree, but average degree does not determine the 1k-distribution.Source: §1.1 · p. 33

1.2 Average nearest neighbor degree (ANND)

• Average nearest neighbor degree for nodes of degree k is a commonly used projection of the joint degree distribution, or 2k-distribution.Source: §1.2 · p. 33
• The joint degree distribution counts links between nodes of degrees k and k′, and is normalized over degree pairs.Source: §1.2 · p. 33
• The 2k-distribution fully determines the 1k-distribution, but the 1k-distribution does not determine the 2k-distribution.Source: §1.2 · p. 33

1.3 Clustering

• The 3k-distribution comprises distributions of degree-labeled wedges and triangles, the two non-isomorphic subgraphs of size 3.Wedges are indexed by the central node degree and the two endpoint degrees; triangle degree arguments are symmetric under permutation.Source: §1.3 · p. 34
• Degree-dependent clustering is presented as a commonly used projection of the 3k-distribution.Source: §1.3 · p. 34
• The 3k-distribution defines the 2k-distribution, but the 2k-distribution does not determine the 3k-distribution.Source: §1.3 · p. 34

1.4 Subgraph frequencies

• Size-3 subgraph concentration is fixed exactly only by the 3k-distribution or 3-distribution, while size-4 concentration is fixed exactly only by the 4k-distribution or 4-distribution.For size 3, the connected subgraphs are wedges and triangles, and their total count is the sum of the two counts.Source: §1.4 · p. 35
• The six non-isomorphic connected subgraphs of size 4 are each measured as their count divided by the total number of connected subgraphs of size 4.Source: §1.4 · p. 35
• The comparisons use subgraph concentrations directly rather than z-scores because z-scores are tailored to a fixed null model, whereas the dk-series varies the null model with d.The paper states that convergence rates for subgraph-frequency means and standard deviations as functions of d are not readily estimated, making z-score comparisons across d meaningless.Source: §1.4 · p. 35

1.5 Common neighbors

• The common-neighbor distribution gives the probability that two connected nodes have m shared neighbors, and is exactly fixed only by the 3k-distribution.The number of common neighbors is also the multiplicity of the edge connecting the two nodes.Source: §1.5 · pp. 35–36

1.6 k-coreness and k-denseness

• A node has k-coreness k when it belongs to a maximal connected subgraph in which every node has degree at least k.The k-core decomposition consists of nested subgraphs induced by nodes of the same k-coreness.Source: §1.6 · p. 36
• An edge has k-denseness k when it belongs to a maximal connected subgraph where every edge has multiplicity at least k −1.The k-dense decomposition consists of nested subgraphs induced by edges of the same k-denseness; multiplicity is the number of common neighbors.Source: §1.6 · p. 36
• Because k-core and k-dense decompositions are recursive, dk-distributions with d = 0, 1, 2, 2.1, or 2.5 do not exactly fix either distribution.Source: §1.6 · p. 36

1.7 Betweenness

• Node betweenness b(i) measures importance by the number of shortest paths passing through node i.It is defined using the fraction of shortest paths between pairs s and t that pass through i.Source: §1.7 · p. 36
• Degree-dependent betweenness ¯b(k) is obtained by averaging betweenness over all nodes of degree k.Source: §1.7 · p. 36

1.8 Shortest path distance

• The distance distribution P(h) describes shortest-path hop lengths, with N(h) counting node pairs separated by h hops.Source: §1.8 · p. 37
• Average distance summarizes shortest-path lengths, while network diameter is the maximum hop distance between nodes.Source: §1.8 · p. 37

1.9 Spectral properties

• The largest adjacency-matrix eigenvalue relates to spreading speed, while the spectral gap—the difference between the two largest eigenvalues—determines random-walk convergence speed.Source: §1.9 · p. 37
• For L = D − A, the zero smallest Laplacian eigenvalue is associated with the random walker’s stationary distribution, while the smallest nonzero eigenvalue (Fiedler value) sets the slowest diffusion mode’s timescale.Source: §1.9 · p. 37

Considered networks

• The study applies dk-series analysis to six networks, including US airports linked by direct flights and the largest connected component of an fMRI voxel graph linked above correlation 0.7.Source: Supplementary Note 2: Considered… · p. 37
• The set includes adjacent words in the largest connected component of Charles Darwin’s The Origin of Species and Internet Autonomous Systems linked by traffic-exchange business relationships.Source: Supplementary Note 2: Considered… · p. 38
• It also includes the largest strongly connected component of the PGP web of mutual trust and the largest connected component of the human protein interaction network.Source: Supplementary Note 2: Considered… · p. 38

Degree distribution; average nearest neighbor degree (ANND)

• For degree distributions, every dk-random graph with d ≥1 matches exactly; ANND matches exactly at d ≥2, though 1k is already close in some networks.The 1k ANNDs in WORDS, INTERNET, and PPI show no noticeable differences from the real networks.Source: Degree distribution · p. 38

Clustering

• Degree-dependent clustering matches at 2.5k; AIR shows no noticeable difference at 2.1k, while WORDS is nearly exact already at 1k.For d < 2.5, degree-dependent clustering differs noticeably in many cases.Source: Clustering · p. 38

Subgraph frequencies; k-coreness and k-denseness

• 2k-random graphs reproduce most subgraph frequencies and k-coreness distributions; BRAIN and PGP require d = 2.5 for both.2.5k-random graphs reproduce k-denseness across all networks, while AIR and WORDS already match at 2k.Source: Subgraph frequencies · p. 39, k-coreness and k-denseness · p. 39

Common neighbors

• 1k-random graphs reproduce common-neighbor distributions in all cases except BRAIN, which requires d = 2, and PGP, which requires d = 2.5.Source: Common neighbors · p. 39

Betweenness

• Betweenness remains unreproduced for BRAIN even at 2.5k, while INTERNET matches at 1k; PGP requires 2.5k and other networks are similar at 2k.Source: Betweenness · p. 39

Shortest path distance

• Shortest-path distances match at 1k for INTERNET and WORDS, but not at 2.5k for BRAIN; d = 2.5 suffices for the other networks.Source: Shortest path distance · p. 39

Spectral properties

• At 2.5k, largest adjacency eigenvalues are close but not exact for all six networks, and spectral gaps are relatively close, with about 5% relative difference for AIR, BRAIN, and WORDS.The large spectral gaps at 2k and 2.1k indicate greater robustness, in the sense of better connectivity and interlinking, than the original networks.Source: Spectral properties · p. 39

Kolmogorov-Smirnov distance

• KS distances compare real-network per-node property CDFs with those across dk-random realizations, capturing node-level differences that dk-distributions do not distinguish.Even when two networks have identical 2k-distributions and ANNDs, their per-node neighbor-degree distributions can differ, yielding a nonzero KS distance.Source: Spectral properties · pp. 39–40

Supplementary Discussion

• The dk-series labels d-sized subgraphs with node degrees, while the d-series counts such subgraphs without degree information.Here, d denotes subgraph size and k denotes node degree.Source: Supplementary Discussion · p. 40
• The dk-series is inclusive: each (d+1)k-distribution contains the full dk-distribution, unlike the d-series, whose elements convey unrelated or loosely related information.The d-series still converges at d = N, when it specifies the whole network topology, but more slowly than the dk-series.Source: Supplementary Discussion · pp. 40–41
• W = N −2 in chains and W = (N −1)(N −2)/2 in stars, yet both have M = N −1, so d=3 counts do not recover d=2.Both networks also have T = 0; wedge and triangle counts therefore fail to define the preceding d-series element, M.Source: Supplementary Discussion · p. 41
• For chains and stars, the 3k-distributions define each topology exactly, whereas their shared d-series counts do not uniquely determine topology.The d-series is not inclusive: its elements capture different kinds of topological statistics, and even W and T leave many non-isomorphic graphs possible.Source: Supplementary Discussion · p. 41
• Node-degree information identifies subgraph locations, speeding convergence with d and making the dk-series an inclusive, systematic basis for topology analysis.The paper contrasts this with subgraph-frequency series, which it says cannot provide a systematic basis for topology analysis.Source: Supplementary Discussion · pp. 40–41

• The two methods are dk-randomizing rewiring, which preserves d=0, 1, or 2 distributions, and p-targeting rewiring, which preserves 2k structure while targeting p=2.1k or 2.5k.The randomization method takes the original graph, a rewiring count, and the d index as inputs; the targeting method takes a target property and annealing parameters.Source: Supplementary Methods · pp. 41–42
• For d=0, rewiring replaces an edge with a non-edge; for d=1 or 2, it swaps two edges, with d=2 requiring equal-degree endpoints.For d=1 and d=2, the swap is discarded if either proposed replacement edge already exists.Source: Supplementary Methods · p. 42
• In p-targeting, the graph is first 2k-randomized, then 2k-rewired with acceptance probability min[exp(−βH), 1], where H measures distance from the original target-property value.Temperature decreases by βfactor after each round of R rewirings, reducing acceptance of energy-increasing rewires; the process stops when energy reaches zero or the accepted-rewiring percentage falls below α.Source: Supplementary Methods · pp. 42–43
• The targeted property is average clustering for d=2.1 or average degree-dependent clustering for d=2.5, and the corresponding energy measures distance from its original value.For d=2.5, the distance is the sum over k of |cGi(k) − cGT(k)|.Source: Supplementary Methods · p. 43
• The authors released the dk-randomization software package freely online [51].Source: Supplementary Methods · p. 43