Math 777: Random Graphs
1. Erdos-Renyi Random Graphs
Branching processes (9/6)
Epidemics (9/6)
The random walk viewpoint (9/6)
CLT for the giant component (9/15)
The combinatorial approach (9/15)
The critical regime (9/21)
Threshold for connectivity (9/20)
2. Arbitrary degree distributions
Newman-Strogatz Watts, Phys Rev E 64, paper 026118
(notes) Supercritical proof, Molloy and Reed results.
van der Hofstad et al. Distances in random graphs with finite variance random degrees
notes on Chung and Lu (10/07)
Chung and Lu - average distances - PNAS
Chung and Lu - connected components - Ann. of Comb.
3. Random Regular Graphs
Janson-Luczak-Rucinski - Sections 9.1-9.4
my notes on JLR, 10/13
Eigenvalues and Expanders, revised 10/18
Mixing Times
4. Small Worlds
Watts and Strogatz (1998)
*
News and Views
Path Lengths
Barbour and Reinert (2001)
Epidemics and Percolation on Small Worlds, Moore and Newman (2000)
5. Barbasi-Albert model
Original paper, Science (1999)
Degree distribution
Other powers, Krapivsky, Redner, Leyvraz (2000)
Diameter, Bollobas and Riordan (2004)
*
Notes
Mixing Times - revised 11/17
Epidemics on Molloy Reed Graphs, Newman (2002)
*
Notes
6. Calloway-Hopcroft-Kleinberg-Strogatz-Watts
Original CHKNS paper, Phys Rev. E.
DMS proof of smooth phase transition, Phys. Rev. E.
my paper for Discrete Random Walks 2003
slides from my talk = class notes for Tuesday Nov. 30 ***
Bollobas, Janson, Riordan (postscript file)
Notes on BJR