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