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 (newman2003structure?; Newman 2018). The code uses networkx (Hagberg, Schult, and Swart 2008). Reusable functions are in amlab/networks_cascades/ and amlab/networks_spreading/.

Session Structure

Session 23: Networks: fundamental concepts

Network Concepts Robustness and Percolation

Toolkit (self-study before the labs):

NetworkX Basics Drawing Graphs Paths and Components 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

Session 26: Laboratory: spreading processes on networks

SIS Model on Networks SIS Simulation SIR on Networks Epidemic Threshold Vaccination Strategies

Practice: Real Networks

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.

References

Hagberg, Aric A., Daniel A. Schult, and Pieter J. Swart. 2008. “Exploring Network Structure, Dynamics, and Function Using NetworkX.” In Proceedings of the 7th Python in Science Conference (SciPy 2008), 11–15.
Newman, Mark. 2018. Networks. 2nd ed. Oxford University Press.