Percolation on networks

A network is connected when every node can reach every other along a path of links. With few links it falls apart into separate components; add links and, past a critical point, one giant component suddenly holds a finite share of all nodes. This is the percolation transition. On Erdős–Rényi random graphs the threshold is sharp. On scale-free networks with p(k) ∝ k−γ and 2 < γ < 3, the degree has a finite mean but an infinite variance, the hubs make the threshold vanish, and an epidemic can always spread.

Based on lecture slides by Sang Hoon Lee for an introductory network science course. References

Largest component of this network against p Blue: this network, exactly, since every link keeps its own random number. Dashed: theory for an infinitely large network with the same degrees. Click or drag on the chart to set p.

Network
p =
pc

Largest component
Coloring
Links kept
–
Mean degree of the kept network
–
Density d = 2M / N(N − 1)
–
S, share of nodes in the largest component
–
Second-largest component
–
Number of components
–
⟨s⟩, mean size of the other components
–
pc = ⟨k⟩ / (⟨k²⟩ − ⟨k⟩) for this network
–
Outbreak
not started

Density and the giant component

In an Erdős–Rényi graph every pair of the N nodes is linked with the same probability, so the density d = 2M / N(N − 1) and the mean degree ⟨k⟩ = d(N − 1) carry the same information. The giant component appears at ⟨k⟩ = 1, which means a critical density dc = 1/(N − 1) that shrinks as the network grows; that is why the curves below use ⟨k⟩. Links are added one at a time in random order, so a single run traces the whole curve, and runs are averaged for five network sizes. Above the threshold the giant share solves S = 1 − e−⟨k⟩S, and the mean size of the other components is ⟨s⟩ = 1 / (1 − ⟨k⟩ + ⟨k⟩S).

Giant component S against ⟨k⟩Colored: simulations. Dashed: S = 1 − e−⟨k⟩S. The step sharpens as N grows.
Mean size of the other components ⟨s⟩It diverges at ⟨k⟩ = 1 as N → ∞, like a susceptibility. Dashed: 1 / (1 − ⟨k⟩ + ⟨k⟩S).
S ∝ (⟨k⟩ − 1)β above the thresholdLog–log. Dashed: the theory S = 1 − e−⟨k⟩S. Dotted: slope β = 1.

⟨s⟩ ∝ (1 − ⟨k⟩)−γp below the thresholdLog–log. Dashed: the theory ⟨s⟩ = 1/(1 − ⟨k⟩), slope −γp = −1. (γp is the percolation exponent, not the degree exponent.)

Largest component at ⟨k⟩ = 1: Smax ∝ N2/3At the threshold the largest component is large but not giant.

Component sizes at ⟨k⟩ = 1: ns ∝ s−τComponents of size s per node, log-binned, for N = 100 000. Dashed: τ = 5/2.

These are the mean-field exponents of percolation, the same as on the Bethe lattice and on lattices above the upper critical dimension d = 6. There the incipient cluster has fractal dimension D = 4, so its mass grows as L4 = N4/6 = N2/3.

Random versus scale-free networks

Now take a whole network and keep each link with probability p. Scale-free networks are built with the configuration model: every node draws a degree from p(k) ∝ k−γ, and link ends are paired at random (self-loops and repeated links are dropped). Each Erdős–Rényi network is given the same mean degree as the scale-free network of the same size. For any network with random wiring, the giant component appears at pc = ⟨k⟩ / (⟨k²⟩ − ⟨k⟩), the Molloy–Reed criterion. For Erdős–Rényi graphs ⟨k²⟩ − ⟨k⟩ = ⟨k⟩², so pc = 1/⟨k⟩ whatever the size. For 2 < γ < 3 the mean stays finite but ⟨k²⟩ grows with the largest hub, so pc → 0 as N → ∞.

Degree distribution p(k)Log-binned, N = 100 000. Red: scale-free, with the dashed slope −γ. Dark: Erdős–Rényi, which is Poisson and has no hubs.
Erdős–Rényi: giant component against pNothing spreads until pc = 1/⟨k⟩ (dashed verticals), then the giant grows suddenly. Dashed curve: generating-function theory for N = 100 000.
Scale-free: giant component against pThe threshold drifts toward zero as N grows and the curve rises from almost p = 0: there is no critical point in the infinite network.
Mean size of the other components ⟨s⟩ against pSolid: scale-free. Dashed: Erdős–Rényi. The peaks mark the finite-size thresholds.
Threshold against network sizeLines: pc = ⟨k⟩/(⟨k²⟩ − ⟨k⟩) from the simulated degrees. Dots: the peak of ⟨s⟩. The scale-free threshold keeps falling.

Epidemics and the vanishing threshold

An outbreak in which each infected person passes the disease to each contact with probability T, then recovers, is bond percolation with p = T: the final outbreak is the component of the first case in the network of links that transmitted. Try “Start an outbreak” at the top of the page and compare the result with that node’s component. On a random network nothing spreads below Tc = 1/⟨k⟩, and past it an epidemic suddenly becomes possible. On a scale-free network the hubs, like super-spreading events, keep Tc near zero, so even rarely transmitted diseases can reach a finite fraction of the population. The size of the epidemic then grows very slowly from zero, which is the convex red curve of the lecture.

Near the threshold the giant grows as S ∝ (p − pc)β. The values for scale-free networks come from the generating-function analysis of Cohen, ben-Avraham and Havlin.

References

  1. P. Erdős and A. Rényi, “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  2. A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science 286, 509 (1999).
  3. M. Molloy and B. Reed, “A critical point for random graphs with a given degree sequence,” Random Struct. Algorithms 6, 161 (1995).
  4. M. E. J. Newman, S. H. Strogatz and D. J. Watts, “Random graphs with arbitrary degree distributions and their applications,” Phys. Rev. E 64, 026118 (2001). Generating functions used for the theory curves.
  5. D. S. Callaway, M. E. J. Newman, S. H. Strogatz and D. J. Watts, “Network robustness and fragility: Percolation on random graphs,” Phys. Rev. Lett. 85, 5468 (2000).
  6. R. Cohen, K. Erez, D. ben-Avraham and S. Havlin, “Resilience of the Internet to random breakdowns,” Phys. Rev. Lett. 85, 4626 (2000).
  7. R. Cohen, D. ben-Avraham and S. Havlin, “Percolation critical exponents in scale-free networks,” Phys. Rev. E 66, 036113 (2002).
  8. M. E. J. Newman, “Spread of epidemic disease on networks,” Phys. Rev. E 66, 016128 (2002). Outbreaks as bond percolation.
  9. R. Pastor-Satorras and A. Vespignani, “Epidemic spreading in scale-free networks,” Phys. Rev. Lett. 86, 3200 (2001).
  10. M. E. J. Newman and R. M. Ziff, “Efficient Monte Carlo algorithm and high-precision results for percolation,” Phys. Rev. Lett. 85, 4104 (2000). Adding links one at a time to trace a whole curve per run.
  11. A.-L. Barabási, Network Science, Cambridge University Press (2016).
  12. M. E. J. Newman, Networks, 2nd ed., Oxford University Press (2018).