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.

A new version called gamma.

Jan 15, 2025 build - 409 pages

The index has now been added and there is a new six page section in the front matter called Notation, Terminology and Overview which gives an overview of the main results. Comments on this section, especially criticisms are welcome.

1. Erdos-Renyi Random Graphs

1.1. Branching Processes
1.2. Cluster growth as an epidemics
1.3. Cluster growth as a random walk
1.4. * Long paths (rewritten)
1.5. CLT for the giant component
1.6. Combinatorial approach
1.7. Critical regime
1.8. * Critical exponents
1.9. Threshold for connectivity

2. General Degree Distributions

2.1. Configuration model
2.2. Limiting degree distribution approach
2.3. Subcritical cluster sizes
2.4. Distances 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. Results for the survival probability
3.5. Survival probabilities for examples
3.6. Component sizes in the subcritical case
3.7. * Multivariate Erdos-Renyi graphs (new 21 page section)

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 model
4.7. Forest fires and epdiemics on Z2

5. Contact process

5.1. Basic Properties
5.2. Mean[filed theory
5.3 Trees, random regular 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. Exponential tails
5.9. Threshold-θ contact process

6. Random Walks

6.1. Basic definitions
6.2. Markov chains and electrical networks
6.3. Conductance
6.4. First degree distribution, min degree 3
6.5. Effect of degree 2 vertrices
6.6. Connected Erdos-Renyi graphs
6.7. Cutoff
6.8. Random regular graphs
6.9. Random walk on Galton-Watson trees
6.10. Sparse Erdos-Renyi graphs

7. Voter model, coalescing random walk

7.1. On Zd and on graphs
7.2. On Z and in your colon
7.3. Coalescing random walk on the torus
7.4. * Hitting times for two random walks
7.5. * A bound on the coallescence time
7.6. * Mean-field behavior of CRW on general graphs
7.7. * Asymptotics for CRW densities
7.8. * Voter model at intermediat times

8. Evolving Networks

8.1. Voter models
8.2. SIS epidemics
8.3. SIR epidemics

Appendix. Large Deviation

A.1. Chernoff's theorem
A.2. Azuma-Hoeffding inequality

Book References