Module 5: Complex Networks
Structure, Robustness and Spreading on Graphs
This module replaces the well-mixed populations of Modules 1 and 2 by networks: who interacts with whom is now given by a graph. You will measure the structure of networks, build the classical models of network growth, and study three processes whose outcome depends on that structure: percolation under node removal, cascades of overload failures, and epidemic spreading (Newman 2003; Newman 2018). The code uses networkx (Hagberg et al. 2008). Reusable functions are in amlab/networks_cascades/ and amlab/networks_spreading/.
Session Structure
Session 23: Networks: fundamental concepts
Network Concepts Robustness and Percolation PageRank
Toolkit (self-study before the labs):
NetworkX Basics Edges and Weights Drawing Graphs Drawing Attributes Graphs from Edge Lists Paths and Components Paths in Directed Graphs Degree and Clustering Centrality in NetworkX
Session 24: Laboratory: cascading failures in power grids
The Iberian Blackout The Motter-Lai Model Cascade Simulation Swing Equation
Session 25: Models of network growth
Erdős-Rényi Random Graphs Small-World Networks Preferential Attachment Comparing Graph Models Scaling of Path Length and Clustering Triadic Closure (Holme-Kim) The Configuration Model
Session 26: Laboratory: spreading processes on networks
SIS Model on Networks SIS Initial State SIS Simulation Comparing Networks under SIS SIR on Networks SIR Simulation Epidemic Threshold SIR as Bond Percolation Vaccination Strategies Metapopulation Epidemics
Practice: Real Networks Practice: Flights and Other Networks Practice: Propagation
Learning Goals
By the end of this module, you should be able to:
- Represent a real system as a graph and load network data with
networkx. - Compute and interpret degree distributions, path lengths, clustering, centrality and communities.
- Apply the Molloy-Reed criterion to predict when a network keeps a giant component under random failure, and explain why targeted attacks are more damaging on heterogeneous networks.
- Implement the Motter-Lai cascade model, validate it, and explain what it leaves out compared with a real power grid event.
- Generate Erdős-Rényi, Watts-Strogatz and Barabási-Albert networks and relate their properties to the model rules.
- Simulate SIS and SIR on networks with reproducible seeds, derive the threshold \(\lambda_c = \langle k \rangle / \langle k^2 \rangle\), and state the assumptions behind the vanishing threshold of scale-free networks.
- Compare random, targeted and acquaintance vaccination.
- Compute PageRank by power iteration and explain the role of the damping factor and of dangling nodes.
- Explain how path length and clustering scale with network size in the ER, WS and BA models, and how triadic closure raises clustering in growing networks.
- Build configuration-model graphs and degree-preserving null models, and relate SIR to bond percolation through the transmissibility.
- Simulate an epidemic on a network of patches linked by mobility and distinguish its effect on arrival time from its effect on final size.