Dynamics on Graphs

By Rick Durrett, James B. Duke Emeritus Professor of Math

Summary: This book is an extensive revision of the 2007 book Random Graph Dynamics. In contrast to RGD, the new version considers a small number of types of graphs, primarily the configuration model and inhomogeneous random graphs, but investigates a wide variety of dynamics. It describes results for the convergence to equilibrium for random walks on random graphs as well as topics that have emerged as mature research areas since the publication of the first edition, such as epidemics, the contact process, voter models, and coalescing random walk. Chapter 8 discusses a new challenging and largely uncharted direction: systems in which the graph and the states of their vertices coevolve.

To be published by Springer in July 2026

According to my contract no more than 10 percent of the content can be on my we page, so I made a

20 page summary

which consists of short paragraphs describing the contents of the various sections. One structural change in the published version follows the traditional style with all the references are in one section at the end.

1. Erdos-Renyi Random Graphs

1.1. Branching Processes
1.2. Cluster growth as a brnaching process
1.3. Cluster growth as a random walk
1.4. Threshold for connectivity
1.5. Long paths
1.6. CLT for the size of the giant component
1.7. Combinatorial approach
1.8. Critical regime
1.9. Critical exponents

2. General Degree Distributions

2.1. Configuration model
2.2. Limiting degree distribution approach
2.3. Subcritical cluster sizes
2.4. Distance between two randonly chosen vertices
2.5. First passage percolation
2.6. Critical regime
2.7. Percolation

3. Inhomogenenous Random Graphs

3.1. Finitely many types
3.2. Motivating examples
3.3. Welcome to the machinge
3.4. Computing the survival probability
3.5. Survival probabilities for examples
3.6. Component sizes in the subcritical case

4. SIR Epidemics

4.1. On the complete graph
4.2. Fixed infection times
4.3. General infection times
4.4. Miller-Volz equations
4.5. Rigorous derivations of the equations
4.6. Household and dorm models
4.7. Epidemics on Z²

5. Contact process

5.1. Basic properties
5.2. Mean-field theory
5.3 Bounded degree graphs
5.4 Erdos-Renyi graphs
5.5. Power-law random graphs
5.6. Results for the star graph
5.7. Sub-exponential degree distributions
5.8. Exponentially bounded degrees
5.9. Threshold-θ contact process

6. Random Walks

6.1. General convergence results
6.2. Conductance
6.3. Fixed degree distribution, min degree 3
6.4. Effect of degree 2 vertrices
6.5. Erdos-Renyi graphs
6.6. Cutoff phenomena
6.7. Random regular graphs

7. Voter model, coalescing random walk

7.1. On Z^d and on graphs
7.2. Coalescing random walk on the torus in d≥ 3
7.3. Hitting times for two random walks
7.4. A bound on the coalescence time
7.5. Mean-field behavior of CRW on general graphs
7.6. Asymptotics for CRW densities
7.7. Voter model at intermediate times