The unreasonable effectiveness of tree-based theory for networks with clustering

Sergey Melnik; Adam Hackett; Mason A. Porter; Peter J. Mucha; James P. Gleeson

Source-linked AI summary

The unreasonable effectiveness of tree-based theory for networks with clustering

Sergey Melnik, Adam Hackett, Mason A. Porter, Peter J. Mucha, James P. Gleeson

arXiv:1001.1439v1Jan 9, 2010cond-mat.dis-nncond-mat.stat-mech

TL;DR

Analytical results for realistic networks are limited, and common tree-based approaches face a challenge from the clustering found in many real networks. This paper tests tree-based theory across network processes and finds it can remain accurate on highly clustered networks when their mean intervertex distance is sufficiently close to that of a random network with the same degree correlations. The authors conclude that network distance, more than clustering level, is associated with the theory’s accuracy in the studied settings.

Problem
Analytical results for realistic networks are scarce, while many analyses assume locally tree-like structure despite the significant clustering and small cycles of real networks.
Source: §I · p. 1
Method
The paper compares tree-based predictions with simulations and examines how prediction error relates to clustering and mean intervertex distance across real-world and synthetic clustered networks.
Source: §I · p. 1, A. Watts-Strogatz Networks · p. 5, B. Real-World Networks and Additional… · pp. 6–7
Results
A mean intervertex distance differing from that of a random network with the same P(k, k′) and node count by no more than about 10% of mean degree z marks the authors’ heuristic accuracy condition.
Source: §IV · p. 7
Takeaways & Limitations
Tree-based theory can yield highly accurate results for several processes on significantly clustered networks when ℓ ≈ ℓ1, including Facebook and AS Internet networks that are not locally tree-like.
Source: §IV · pp. 7–8

Abstract

from arXiv · show

We demonstrate that a tree-based theory for various dynamical processes yields extremely accurate results for several networks with high levels of clustering. We find that such a theory works well as long as the mean intervertex distance $\ell$ is sufficiently small - i.e., as long as it is close to the value of $\ell$ in a random network with negligible clustering and the same degree-degree correlations. We confirm this hypothesis numerically using real-world networks from various domains and on several classes of synthetic clustered networks. We present analytical calculations that further support our claim that tree-based theories can be accurate for clustered networks provided that the networks are "sufficiently small" worlds.

I. INTRODUCTION

Analytical theory for network dynamics is scarce for realistic networks, while many existing approaches assume locally tree-like structure despite clustering in real networks. This paper finds that tree-based theory can nevertheless be accurate on highly clustered networks when their mean intervertex distance is sufficiently close to that of a randomly rewired network.

I. INTRODUCTION

Analytical results for realistic network topologies are scarce, and most analyses assume locally tree-like structure even though real networks often have many small cycles.The mismatch has motivated research on analytical results for clustered networks.Source: §I · p. 1
Existing unweighted-network theories typically use either the degree distribution p_k alone or that distribution together with degree-degree correlations P(k, k′).The paper names these approaches pk-theory and P(k, k′)-theory; clustering in their sample ensembles is typically low and decreases as N^-1 as N grows.Source: §I · p. 1
The study examines undirected, unweighted real-world networks using empirical degree distributions as inputs to theory and compares predictions with simulations on the original networks.The paper considers bond percolation, k-core sizes, and other processes.Source: §I · p. 1
Tree-based analytical results can accurately describe several processes on highly clustered networks when their mean intervertex distance is close to that of a randomly rewired version.The paper calls these networks “sufficiently small” small worlds.Source: §I · p. 1

A. Bond Percolation

For bond percolation, P(k, k′)-theory closely matches simulations on the Facebook and AS Internet networks but performs less accurately on the PGP and power-grid networks. The discrepancy is not explained by finite network size; rewiring evidence instead points to structural characteristics beyond degree correlations.

A. Bond Percolation

P(k, k′)-theory matches bond-percolation simulations very accurately for the AS Internet and Oklahoma Facebook networks, but much less accurately for the PGP and power-grid networks.The Oklahoma Facebook network has a high clustering coefficient despite its close theory–simulation match.Source: A. Bond Percolation · p. 3
The four networks’ global clustering coefficients are 0.23, 0.21, 0.27, and 0.08 for Facebook, AS Internet, PGP, and power grid, respectively.Across 100 Facebook networks, coefficients range from 0.19 to 0.41, with mean 0.24.Source: A. Bond Percolation · p. 3
The discrepancy on the PGP and power-grid networks does not arise from finite-size effects: P-rewired versions agree very well with P(k, k′)-theory.P-rewiring preserves P(k, k′) while randomizing connections.Source: A. Bond Percolation · p. 3
P(k, k′)- and pk-theory agree better in the Facebook and power-grid examples, where degree-correlation coefficients have smaller absolute values, than in the AS Internet and PGP examples.The reported Pearson coefficients are 0.074 (Facebook mean 0.063 over 100 networks), 0.0035, −0.2, and 0.24, respectively.Source: A. Bond Percolation · pp. 3–4
The highest nonzero k-core predictions from P(k, k′)-theory are closer to numerical values for Facebook and the AS Internet than for the PGP and power-grid networks.The predicted-to-numerical ratios are approximately 0.916 and 0.826 for panels (a) and (b), versus 0.516 and 0.368 for panels (c) and (d).Source: Figure 2 · p. 3, B. k-Cores · p. 4

C. Watts’ Threshold Model

In Watts’ threshold model, cascade size has a sharp transition as the mean threshold rises. Theory captures the transition’s position for the Facebook and AS Internet networks, but not for the other examples.

C. Watts’ Threshold Model

The cascade-size transition’s position is accurately captured by theory for the Facebook and AS Internet networks, but not for the other examples.The comparison uses Gaussian threshold distributions with mean µ and variance σ^2 = 0.04.Source: C. Watts’ Threshold Model · p. 4
Cascade size shows a sharp transition as the mean threshold µ increases.The figure uses seed fraction ρ0 = 0 because nodes with negative thresholds turn on immediately and act as seeds.Source: C. Watts’ Threshold Model · p. 4, Figure 4 · p. 5
Figure 4 plots SIS infected fraction I(t) over time for Fig. 1 networks, with μ=1 throughout, I(0)=10^-3 in (a)–(c) and 0.002 in (d), and λ=0.02 in (a), 0.2 in (b)–(c), and 0.8 in (d).Source: Figure 4 · p. 5

D. Susceptible-Infected-Susceptible Model

For SIS dynamics, P(k, k′)-theory is accurate for some networks and inaccurate for others, consistent with the paper’s comparisons across processes. The cited SIS theory is expected to apply accurately only to early infection development.

D. Susceptible-Infected-Susceptible Model

The cited SIS theory is expected to describe accurately only the early-time development of infection.The comparison concerns the time evolution of the infected fraction.Source: D. Susceptible-Infected-Susceptible… · p. 5
P(k, k′)-theory gives accurate results on certain networks but is rather inaccurate on others for SIS dynamics.The authors describe this pattern as consistent with their results for the other studied processes.Source: D. Susceptible-Infected-Susceptible… · p. 5
The SIS comparison is presented as another example of theory–simulation agreement varying across networks and processes.Its interpretation is bounded by the theory’s stated early-time applicability.Source: D. Susceptible-Infected-Susceptible… · p. 5

III. MEASURE OF PREDICTION QUALITY

The section characterizes which networks allow P(k, k′)-theory to predict dynamical processes accurately, focusing on bond percolation because the earlier figures show the characterization holds across several processes.

Bond percolation is the main focus for characterizing when P(k, k′)-theory gives good results, although the characterization is shown to hold across several processes.Source: §III · p. 5

A. Watts-Strogatz Networks

The Watts–Strogatz networks provide a controlled test of how clustering and mean intervertex distance relate to tree-based theory’s accuracy. As rewiring increases, prediction error tracks excess distance more closely than clustering.

A. Watts-Strogatz Networks

The study starts with a 10,000-node ring where each node connects to 10 nearest neighbors, then randomly rewires a fraction f of links.It calculates clustering, mean intervertex distance, and the GCC size across bond-occupation probabilities, comparing the latter with P(k, k′)-theory.Source: A. Watts-Strogatz Networks · p. 5
With 1/M = 10^-3, E_f approximates the average vertical distance between the theoretical and numerical GCC-size curves over p ∈ [0, 1].Source: A. Watts-Strogatz Networks · p. 6
For rewiring fractions f > 10^-2, prediction error varies approximately linearly with ℓ_f − ℓ_1, unlike the nonlinear relationship with clustering C_f.The plotted error E_f is scaled by 100 and C_f by 10 for visualization; the inset compares both quantities with ℓ_f − ℓ_1.Source: A. Watts-Strogatz Networks · p. 6, Figure 5 · p. 6

B. Real-World Networks and Additional Examples

Across tested networks, excess mean intervertex distance relative to a degree-correlated random network predicts P(k, k′)-theory error better than clustering. The theory is accurate when this excess is sufficiently small, but not at larger values.

B. Real-World Networks and Additional Examples

The error measure E is the average distance between numerical GCC-size results and the P(k, k′)-theory prediction.The real-world comparison uses logarithmic axes to resolve variables spanning one or more orders of magnitude.Source: B. Real-World Networks and Additional… · p. 6
The study also examines Watts–Strogatz and clustered random networks, including γ-theory networks, under several P-rewiring fractions.The γ-theory examples use the network models described in Refs..Source: B. Real-World Networks and Additional… · p. 6
The normalized excess distance (ℓ − ℓ_1)/z predicts error E better than clustering C, with R² ≈ 0.94 versus R² ≈ 0.087.Here ℓ_1 is the mean distance after full P-rewiring, preserving degree correlations; z is mean degree.Source: B. Real-World Networks and Additional… · p. 7, Figure 6 · p. 7
When ℓ − ℓ_1 is sufficiently small—e.g., below z/10—P(k, k′)-theory can accurately predict GCC size, k-core sizes, and several dynamical processes.The AS Internet graph has (ℓ − ℓ_1)/z ≈ 3.3 × 10^-2; all 100 Facebook networks have values much smaller.Source: B. Real-World Networks and Additional… · p. 7
At larger excess distances, P(k, k′)-theory is not accurate; the PGP and Power Grid networks have (ℓ − ℓ_1)/z values of approximately 0.45 and 3.9, respectively.Source: B. Real-World Networks and Additional… · p. 7
The claim that E depends primarily on ℓ − ℓ_1 rather than C is supported by the real-world analysis, though the stated analytical result is restricted in applicability.Source: B. Real-World Networks and Additional… · p. 7

IV. CONCLUSIONS

Tree-based theory can be highly accurate for several processes on clustered networks when their mean intervertex distance ℓ is close to that of a random network with the same degree correlations. The paper gives a heuristic distance bound and notes a process-specific exception for uniform-threshold Watts’ model.

IV. CONCLUSIONS

ℓ should differ from the distance in a same-size, degree-correlation-matched random network by no more than about 10% of mean degree z.The authors describe this as a heuristic answer to how small a small-world network must be.Source: §IV · p. 7
For Watts’ threshold model with σ = 0, theory and simulation differ even on Facebook networks, making this case a useful test for clustered-network models.The paper says accuracy depends on the process under scrutiny.Source: §IV · p. 7, Figure 7 · p. 8
Tree-based theory accurately predicts several processes, including bond percolation and k-core sizes, when ℓ ≈ ℓ1, even with significant clustering.The AS Internet and Facebook social networks are examples; the theory’s locally tree-like premise does not hold for these graphs.Source: §IV · pp. 7–8

Appendix A: Scaling of Prediction Error with Mean Intervertex Distance

The appendix analyzes how prediction error E relates to excess mean intervertex distance ℓ − ℓ1 near a fully P-rewired network. Its analytical expression fits real-world network results, while relying on assumptions that limit its scope.

Appendix A: Scaling of Prediction Error with Mean Intervertex Distance

For networks close to fully P-rewired, the analysis derives E’s dependence on ℓ − ℓ1; because clustering is negligible in the infinite-network setting, E cannot depend on clustering coefficient C.The derivation approximates the percolation-threshold change as the prediction error when the perturbation shifts the entire percolation curve.Source: Appendix A · pp. 8–9
The branching matrix describes connection probabilities and characterizes mean intervertex distance ℓ; its largest eigenvalue λ determines the bond-percolation threshold.The appendix compares a network’s λ with λ1, the largest eigenvalue for its fully P-rewired counterpart, which is determined by degree correlations.Source: Appendix A · pp. 8–9
R2 ≈ 0.87 and fitted slope 1.09: Eq. (A6) fits the relationship between actual and predicted E for real-world networks.The figure compares numerical E values with Eq. (A6) predictions, using numerically calculated ℓ and ℓ1.Source: Figure 8 · p. 9, Appendix A · p. 9

Appendix B: Scatter Plots

The appendix compares prediction error E with candidate network characteristics across real-world and synthetic networks. Excess distance ℓ − ℓ1 has a strong association with E, while clustering has a weak one; available datasets do not establish the best scaling function.

Appendix B: Scatter Plots

R2 > 0.9 for predictors involving ℓ − ℓ1, versus R2 < 0.3 for predictors involving clustering coefficients.The plots include real-world networks, Watts–Strogatz networks, and γ-theory networks.Source: Appendix B · p. 9
The 1/z and Eq. (A6) scaling functions both fit E ≈ F(z, ℓ, …)(ℓ − ℓ1) satisfactorily, but the available datasets cannot identify the best function.The appendix describes the tested predictors as combinations of mean degree z, mean intervertex distance ℓ, and clustering coefficients.Source: Appendix B · p. 9
The network summary reports N, mean degree z, original-network distance ℓ, and fully P-rewired distance ℓ1 for the real-world datasets.The rewired comparison networks retain the original degree correlation and size.Source: Appendix B · p. 9, Table I · p. 10