Networks

Structure, Centrality and Spreading on Graphs

This session connects graph structure (who is connected to whom) with dynamics on graphs (how processes spread along edges). Our main applications are epidemic spreading with the SIS and SIR models (Kermack and McKendrick 1927; Pastor-Satorras et al. 2015).

You will work with both:

Synthetic graph models (random, small-world, scale-free) to build intuition.
Real networks (Enron email, USA flights) to test your ideas.

Use notebooks for this session

I recommend following this session using Jupyter notebooks rather than standalone scripts.

You can iterate faster (run one cell at a time).
You can keep figures, outputs, and notes next to the code.
It’s easier to debug simulations and compare parameter sweeps.

From Collective Motion to Networks

In the previous session on collective motion, you simulated agent-based models in continuous space (e.g., Vicsek/Couzin): who interacts with whom was determined by geometry (metric distance, vision cones, neighborhoods).

In this session we switch the lens: we keep the same simulation mindset, but we represent interactions with a graph. Edges encode the possible transmission/interaction channels.

Geometry-based interactions → network topology.
Local rules in space → local rules along edges.
Same themes: heterogeneity, hubs, robustness, emergent outcomes.

Back to Collective Motion

Why simulate on networks instead of using ODEs?

In classical epidemic models, we use mean-field ODEs:

dS/dt, dI/dt, dR/dt.

Those assume homogeneous mixing: every individual interacts with every other with equal probability (Keeling and Rohani 2008).

Real systems are not homogeneous:

Some nodes have 2 connections.
Others have 200.
Paths are constrained by topology.
Clusters slow or accelerate spreading.

On networks, infection propagates only along edges. Structure matters.

This lets you connect:

Degree heterogeneity.
Centrality.
Robustness.
Epidemic thresholds.

Case Studies

Network Fundamentals Network Connectivity

Graph Models

SIS Model SIR Model

Assignment: Real-World Networks

Learning Goals

By the end of this session, you should be able to:

Represent real systems as graphs and load datasets with networkx.
Measure core properties (degree, density, components, paths, clustering).
Quantify node importance with centrality (degree, closeness, betweenness, PageRank).
Generate and compare standard graph models (Erdős–Rényi, Watts–Strogatz, Barabási–Albert).
Implement SIS and SIR simulations using node attributes for state.
Run reproducible experiments (fixed SEED, multiple trials, summary curves) and interpret results.

Flow of this Session

Fundamentals: graphs in `networkx`

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks (Hagberg, Schult, and Swart 2008).

We start with the basic data structure:

nodes, edges, and attributes,
visualization,
reading graphs from files.

This tutorial is based on A First Course in Network Science (Menczer, Fortunato, and Davis 2020). You can see their official Github repository here.. Please take a look at the folder references/networkx_indiana for more information.

You will practice:

undirected vs directed graphs,
weighted edges,
adjacency/edge lists,
connected components.

These concepts follow the formal definitions of nodes, links, directed and weighted graphs introduced in the lecture notes.

Connectivity + centrality

Next we measure structure:

degree and density,
paths, diameter, components,
clustering coefficient,
centrality measures (degree/closeness/betweenness/PageRank) and what they mean.

Graph models (synthetic networks)

We generate synthetic networks to compare structure:

Erdos–Rényi random graphs.
Watts–Strogatz small-world networks.
Barabási–Albert preferential attachment networks.

These models aim to reproduce properties of real networks such as short paths, clustering, and heavy-tailed degree distributions (Watts and Strogatz 1998; Barabasi and Albert 1999; Newman 2018).

You will measure:

Average degree.
Average path length.
Clustering coefficient.
Degree distribution.

Spreading: SIS and SIR

This is the core computational part of the lab.

We simulate:

SIS model Susceptible → Infected → Susceptible No permanent immunity.
SIR model Susceptible → Infected → Recovered Permanent immunity.

Key questions you will answer:

How does network structure affect epidemic size?
What is the epidemic threshold?
How do hubs change the outcome?
What happens if we remove high-degree nodes first?

You will compare spreading on:

Random networks.
Small-world networks.
Scale-free networks.
Real datasets such as air transportation or email communication .

Assignment

The final project is Assignment: Real-World Networks.

You will choose one real network (Enron or USA Flights), then:

Characterize the network (structure + centrality).
Run both SIS and SIR simulations on that same network.

Your submission includes:

Code that reproduces results end-to-end.
A short report (figures + interpretation).

The emphasis is on reproducible experiments and clear interpretation of how structure changes outcomes.

References

Barabasi, Albert-Laszlo, and Reka Albert. 1999. “Emergence of Scaling in Random Networks.” Science 286 (5439): 509–12. https://doi.org/10.1126/science.286.5439.509.

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.

Keeling, Matt J., and Pejman Rohani. 2008. Modeling Infectious Diseases in Humans and Animals. Princeton University Press.

Kermack, William O., and Anderson G. McKendrick. 1927. “A Contribution to the Mathematical Theory of Epidemics.” Proceedings of the Royal Society A 115 (772): 700–721. https://doi.org/10.1098/rspa.1927.0118.

Menczer, Filippo, Santo Fortunato, and Clayton A. Davis. 2020. A First Course in Network Science. Cambridge University Press.

Newman, Mark. 2018. Networks. 2nd ed. Oxford University Press.

Pastor-Satorras, Romualdo, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. “Epidemic Processes in Complex Networks.” Reviews of Modern Physics 87 (3): 925–79. https://doi.org/10.1103/RevModPhys.87.925.

Watts, Duncan J., and Steven H. Strogatz. 1998. “Collective Dynamics of ’Small-World’ Networks.” Nature 393 (6684): 440–42. https://doi.org/10.1038/30918.

--- title: "Networks" subtitle: "Structure, Centrality and Spreading on Graphs" format: html --- This session connects **graph structure** (who is connected to whom) with **dynamics on graphs** (how processes spread along edges). Our main applications are epidemic spreading with the **SIS** and **SIR** models [@kermack1927contribution; @pastor2015epidemic]. You will work with both: - **Synthetic graph models** (random, small-world, scale-free) to build intuition. - **Real networks** (Enron email, USA flights) to test your ideas. ::: {.callout-tip} ## Use notebooks for this session I recommend following this session using **Jupyter notebooks** rather than standalone scripts. - You can iterate faster (run one cell at a time). - You can keep figures, outputs, and notes next to the code. - It's easier to debug simulations and compare parameter sweeps. ::: ## From Collective Motion to Networks In the previous session on **collective motion**, you simulated agent-based models in continuous space (e.g., Vicsek/Couzin): who interacts with whom was determined by **geometry** (metric distance, vision cones, neighborhoods). In this session we switch the lens: we keep the same simulation mindset, but we represent interactions with a **graph**. Edges encode the possible transmission/interaction channels. - Geometry-based interactions → **network topology**. - Local rules in space → local rules **along edges**. - Same themes: heterogeneity, hubs, robustness, emergent outcomes. [Back to Collective Motion](../collective-motion/index.qmd){.btn .btn-secondary} ### Why simulate on networks instead of using ODEs? In classical epidemic models, we use mean-field ODEs: dS/dt, dI/dt, dR/dt. Those assume homogeneous mixing: every individual interacts with every other with equal probability [@keeling2008modeling]. Real systems are not homogeneous: * Some nodes have 2 connections. * Others have 200. * Paths are constrained by topology. * Clusters slow or accelerate spreading. On networks, infection propagates only along edges. Structure matters. This lets you connect: * Degree heterogeneity. * Centrality. * Robustness. * Epidemic thresholds. ## Case Studies [Network Fundamentals](fundamentals.qmd){.btn .btn-primary} [Network Connectivity](connectivity.qmd){.btn .btn-primary} [Graph Models](models.qmd){.btn .btn-primary} [SIS Model](sis.qmd){.btn .btn-primary} [SIR Model](sir.qmd){.btn .btn-primary} [Assignment: Real-World Networks](assignment.qmd){.btn .btn-secondary} ## Learning Goals By the end of this session, you should be able to: - Represent real systems as graphs and load datasets with `networkx`. - Measure core properties (degree, density, components, paths, clustering). - Quantify **node importance** with centrality (degree, closeness, betweenness, PageRank). - Generate and compare standard graph models (Erdős–Rényi, Watts–Strogatz, Barabási–Albert). - Implement **SIS** and **SIR** simulations using **node attributes** for state. - Run reproducible experiments (fixed `SEED`, multiple trials, summary curves) and interpret results. ## Flow of this Session ### Fundamentals: graphs in `networkx` NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks [@hagberg2008networkx]. We start with the basic data structure: - nodes, edges, and attributes, - visualization, - reading graphs from files. This tutorial is based on *A First Course in Network Science* [@menczer2020firstcourse]. [You can see their official Github repository here.](https://github.com/CambridgeUniversityPress/FirstCourseNetworkScience/tree/master). Please take a look at the folder [references/networkx_indiana](../../references/networkx_indiana/) for more information. You will practice: * undirected vs directed graphs, * weighted edges, * adjacency/edge lists, * connected components. These concepts follow the formal definitions of nodes, links, directed and weighted graphs introduced in the lecture notes. ### Connectivity + centrality Next we measure structure: * degree and density, * paths, diameter, components, * clustering coefficient, * centrality measures (degree/closeness/betweenness/PageRank) and what they mean. ### Graph models (synthetic networks) We generate synthetic networks to compare structure: * Erdos–Rényi random graphs. * Watts–Strogatz small-world networks. * Barabási–Albert preferential attachment networks. These models aim to reproduce properties of real networks such as short paths, clustering, and heavy-tailed degree distributions [@watts1998collective; @barabasi1999emergence; @newman2018networks]. You will measure: * Average degree. * Average path length. * Clustering coefficient. * Degree distribution. ### Spreading: SIS and SIR This is the core computational part of the lab. We simulate: * **SIS model** Susceptible → Infected → Susceptible No permanent immunity. * **SIR model** Susceptible → Infected → Recovered Permanent immunity. Key questions you will answer: * How does network structure affect epidemic size? * What is the epidemic threshold? * How do hubs change the outcome? * What happens if we remove high-degree nodes first? You will compare spreading on: * Random networks. * Small-world networks. * Scale-free networks. * Real datasets such as air transportation or email communication . ## Assignment The final project is [Assignment: Real-World Networks](assignment.qmd). You will choose **one** real network (Enron or USA Flights), then: 1. **Characterize the network** (structure + centrality). 2. Run **both** **SIS** and **SIR** simulations on that same network. Your submission includes: - **Code** that reproduces results end-to-end. - A short **report** (figures + interpretation). The emphasis is on **reproducible experiments** and clear interpretation of how structure changes outcomes.