yeast protein interaction network
more pictures

Random Graph Dynamics

By Rick Durrett, Cornell U.

Published by Cambridge U. Press. Second printing with typos corrected.

Also available in Romanian

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