yeast protein interaction network
more pictures

Random Graph Dynamics

By Rick Durrett, Cornell U.

Published by Cambridge U. Press, October 2006
Second printing with typos corrected. Now out in paperback. You can buy it for $30 or less at Amazon.com or from the publisher.

Now available in Romanian

The bad news is that the index is missing from the second printing. You can get the first chapter by clicking on its title

1. Overview

1.1. Introduction to the introduction
1.2. Erdös, Renyi, Molloy and Reed
1.3. Six degrees, small worlds
1.4. Power laws, preferential attachment
1.5. Epidemics and percolation
1.6. Potts models and the contact process
1.7. Random walks and voter models
1.8. CHKNS model

2. Erdös-Renyi Random Graphs

2.1. Branching Processes
2.2. Cluster growth as an epidemics
2.3. Cluster growth as a random walk
2.4. Diameter of the giant component
2.5. CLT for the giant component
2.6. Combinatorial approach
2.7. Critical regime
2.8. Threshold for connectivity

3. Fixed Degree Distributions

3.1. Definitions and heuristics
3.2. Proof of phase transition
3.3. Subcritical estimates
3.4. Diameter: finite variance
3.5. Epidemics

4. Power Laws

4.1. Barabási-Albert Model
4.2. Related models
4.3. Martingales and urns
4.4. Scale-free trees
4.6. Diameter: Power Laws 2 < beta < 3
4.5. Diameter: Barabási-Albert model
4.7. Percolation, resilience
4.8. SIS epidemic

5. Small Worlds

5.1. Watts and Strogatz model
5.2. Path lengths
5.3. Epidemics
5.4. Ising and Potts models
5.5. Contact processes

6. Random Walks

6.1. Spectral gap
6.2. Conductance
6.3. Fixed degree distribution
6.4. Preferential attachment graph
6.5. Connected Erdös-Renyi graphs
6.6. Small worlds
6.7. Only degree two and three
6.8. Hitting times
6.9. Voter models

7. CHKNS model

7.1. Heuristic arguments
7.2. Proof of the phase transition
7.3. Subcritical estimate
7.4. Kosterlitz-Thouless transition
7.5. Results at the critical value

References