Dynamics on Graphs

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

Book summary: (from the cover) This extensive revision of the 2007 book Random Graph Dynamics, covering the current state of mathematical research in the field, is ideal for researchers and graduate students. It considers a small number of types of graphs, primarily the configuration model and inhomogeneous random graphs. However, it investigates a wide variety of dynamics. The author 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.

The whole book in one pdf The current version which is 350 pages is dated April 16, 2024 contains an index. It is enetering the publication process at Cambridge U. Press, but the book will not be available in hard cover until October.

Subsubsections have been omitted from this table of contents, but are there in the pdf. Each chapter has a separate set of references which is both a feature and a bug.

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
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

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. Trees, random regular graphs
5.3. Power-law random graphs
5.4. Results for the star graph
5.5. Sub-exponential degree distributions
5.6. Exponential tails
5.7. 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. In d=1 and in your colon
7.3. Coalescing random walk on the torus
7.4. Using ideas from Markov chains
7.5. Cooper's bound
7.6. Random regular graphs
7.7. Oliveira's results
7.8. Asymptotics for CRW densities

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