Dynamical Systems
Complex Networks and Graph Dynamics
The internet, the brain, social networks, and epidemics are all complex networks with nontrivial topology. Power laws, small worlds, and hubs determine resilience to failure, speed of information spread, and epidemic threshold. Network dynamics mathematics unifies all these phenomena.
- Epidemiology: COVID-19 spread was accelerated by hubs (international airports), explaining why targeting the top 20% most-connected nodes is more effective than random quarantine of 80% of the population
- Neuroscience: the human connectome has small-world structure; deviations in network topology correlate with schizophrenia and Alzheimer's disease in imaging studies
- Infrastructure: the 2003 North American blackout started from a single overloaded node and cascaded to disconnect 55 million people in 8 seconds - Laplacian spectral analysis could have predicted it
- Web search: Google PageRank is the principal eigenvector of the web graph's modified Laplacian, measuring node importance by link quality rather than link count
Предварительные знания
- Graph theory (basics)
- Adjacency and degree matrices
- Kuramoto model
Scale-free networks
In 1998, Watts and Strogatz found that the C. elegans neural network (302 neurons, 2359 synapses) has a 'small world': mean path length L ~ 2.65, close to a random graph, with high clustering C ~ 0.28. In 1999, Barabasi and Albert showed the internet (n > 10^9 pages) grows via preferential attachment, producing a power-law degree distribution P(k) ~ k^{-3}.
What characterises a scale-free network?
A scale-free network (Barabási-Albert, 1999) has a power-law degree distribution P(k) ~ k^(-gamma). This explains hubs - nodes with very high degree (Google, Wikipedia in the web graph). Most real networks (web, citation, social) are scale-free with 2 < gamma < 3.
Small-world networks
Watts-Strogatz small-world model: start with a regular ring (n nodes, each connected to k neighbors), then rewire each edge with probability p. At p ~ 0.01, the result has small L (like a random graph) and large C (like the regular ring) - exactly the structure found in neural and social networks.
Scale-free networks and hubs. The internet is scale-free: Google, Amazon, Wikipedia are hubs with billions of links, while most sites have only a few. Randomly disabling 90% of sites leaves the network connected (hubs survive). But deliberately targeting Google would shatter connectivity.
What distinguishes a Watts-Strogatz small-world network?
Watts and Strogatz (1998) showed that adding a small fraction of random edges to a regular lattice reduces the diameter from O(N) to O(log N) while preserving local clustering. The Milgram '6 degrees of separation' experiment (1967) is the empirical example: a social small-world network.
Dynamics on networks: epidemics and cascades
Robustness against random failures versus vulnerability to targeted attacks - the fundamental trade-off of scale-free networks. This drives hub-targeted vaccination strategies and the design of fault-tolerant infrastructure.
Diffusion on networks: dx/dt = -L*x, where L is the graph Laplacian. Diffusion rate is governed by lambda_2. The spectral gap (lambda_2/lambda_n) determines the mixing time of the Markov chain - connecting graph theory to ergodic theory. PageRank is the leading eigenvector of a modified Laplacian of the web graph.
| Model | P(k) | <L> | C | Feature |
|---|---|---|---|---|
| Random (Erdos-Renyi) | Poisson | log(N)/log(<k>) | ~<k>/N | Uniform, connectivity threshold |
| Small world (Watts-Strogatz) | Exponential | ~log(N) | High | Short paths + clustering |
| Scale-free (Barabasi-Albert) | k^{-3} | log(N)/log(log(N)) | Low | Hubs, no epidemic threshold |
Why does the epidemic threshold approach zero in scale-free networks as N → infinity?
Pastor-Satorras & Vespignani (2001): for SIS epidemics on a network with P(k) ~ k^(-gamma) and 2 < gamma <= 3, the second moment <k²> diverges as N → ∞, so the critical infection rate lambda_c = <k>/<k²> → 0. This explains why computer viruses and infectious diseases spread 'by default' on real networks.
Connections to other areas
Complex networks unite graph theory, dynamical systems, statistical physics, and applications from epidemiology to neuroscience.
- Synchronization: The Kuramoto Model — Kuramoto is the simplest graph dynamics that lives on complex networks
- Network Dynamics: Epidemics, Cascades, and PageRank — Introductory chapter on epidemics, cascades and PageRank on networks
- Ergodic Theory: Mixing and KS Entropy — Ergodicity of random walks on networks links to ergodic theory
Итоги
- Graph Laplacian L = D - A: spectrum 0 = lambda_1 <= lambda_2 <= ... <= lambda_n; Fiedler value lambda_2 measures algebraic connectivity
- BA scale-free network: preferential attachment gives P(k) ~ k^{-3}; <k^2>/<k> -> inf, no epidemic threshold
- Small world (Watts-Strogatz): short paths L ~ log(N) with high clustering C; typical of social and neural networks
- SIR on networks: R_0 = beta/gamma * <k^2>/<k>; diverges for BA networks so any epidemic spreads
- Kuramoto on networks: K_c ~ <k>/<k^2> -> 0 for scale-free networks
- Diffusion: dx/dt = -L*x; mixing speed ~ lambda_2; spectral gap determines MCMC efficiency
What does the Fiedler value lambda_2 of a graph Laplacian measure?
By Fiedler's theorem, lambda_2 > 0 iff the graph is connected. It measures how hard it is to partition the graph into two parts (Cheeger inequality). For complete K_n: lambda_2 = n. For a path graph: lambda_2 ~ 1/n^2 (slow diffusion). A larger spectral gap means faster Markov chain mixing.