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.

The whole publication process broke down recently. In violation of an explicit agreement I (thought I) had with my editor, the copyeditor made extensive changes to the text and made more than two dozen changes to the mathematics introducing a number of errors. Surprising hubris for a guy who doesn't know how to differentiate log(f(x)) or take limits. Over a two week period May 24 - June 6 I reviewed the copyedited manuscript and wrote 27 pages of comments (more than 600) on what had to be fixed. My editor, Lauren Cowles and her staff did not acknowledge my submission of my comments on June 6. Despite multiple follow-up emails I have not had a reply of any kind.

At this point I have started going through the book correcting the handful of useful comments made by the copyeditor. Having not read the book for a couple of months I have found a number of things that need clarification. The book is in draft mode with each section starting on a new page, and there are still anumber of things to fix.

The whole book in one pdf.

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