Random graph dynamics

Rick Durrett0521866561, 9780521866569, 9780511349836

The notion of six degrees of separation – that any two people on the planet can be connected by a short chain of people – inspired Strogatz and Watts to define the small world random graph, where each site is connected to close neighbours, but also has long range connections. At about the same time, it was observed in human social networks and on the internet that the number of neighbours of an individual has a power law distribution. This inspired Barabasi and Albert to define the preferential attachment model, which has these properties. These two papers led to an explosion of research, but much was nonrigorous and relied on simulations. This book uses mathematical arguments to obtain insights into these graphs. A unique feature of this book is the interest in the dynamics of process taking place on the graphs in addition to their geometric properties, like correctness and diameter.

---

Table of contents :
Half-title……Page 3
Series-title……Page 4
Title……Page 5
Copyright……Page 6
Contents……Page 7
Preface……Page 9
1.1 Introduction to the Introduction……Page 13
1.2 Erdös, Rényi, Molloy, and Reed……Page 15
1.3 Six Degrees, Small Worlds……Page 19
1.4 Power Laws, Preferential Attachment……Page 23
1.5 Epidemics and Percolation……Page 27
1.6 Potts Models and the Contact Process……Page 30
1.7 Random Walks and Voter Models……Page 32
1.8 CHKNS Model……Page 35
2.1 Branching Processes……Page 39
2.2 Cluster Growth as an Epidemic……Page 46
2.3 Cluster Growth as a Random Walk……Page 49
2.4 Diameter of the Giant Component……Page 55
2.5 CLT for the Giant Component……Page 58
2.6 Combinatorial Approach……Page 62
2.7 Critical Regime……Page 68
2.8 Threshold for Connectivity……Page 74
3.1 Definitions and Heuristics……Page 82
3.2 Proof of Phase Transition……Page 87
3.3 Subcritical Estimates……Page 94
3.4 Distances: Finite Variance……Page 96
3.5 Epidemics……Page 97
4.1 Barabási–Albert Model……Page 102
4.2 Related Models……Page 105
4.3 Martingales and Urns……Page 111
4.4 Scale-Free Trees……Page 117
4.5 Distances: Power Laws 2 < β < 3……Page 122
4.6 Diameter: Barabási–Albert Model……Page 128
4.7 Percolation, Resilience……Page 133
4.8 SIS Epidemic……Page 137
5.1 Watts and Strogatz Model……Page 144
5.2 Path Lengths……Page 146
5.3 Epidemics……Page 152
5.4 Ising and Potts Models……Page 156
5.5 Contact Process……Page 160
6.1 Spectral Gap……Page 165
6.2 Conductance……Page 168
6.3 Fixed Degree Distribution……Page 171
6.4 Preferential Attachment Graph……Page 176
6.5 Connected Erdös–Rényi Graphs……Page 181
6.6 Small Worlds……Page 183
6.7 Only Degrees 2 and 3……Page 187
6.8 Hitting Times……Page 189
6.9 Voter Models……Page 193
7.1 Heuristic Arguments……Page 199
7.2 Proof of the Phase Transition……Page 202
7.3 Subcritical Estimates……Page 205
7.4 Kosterlitz–Thouless Transition……Page 209
7.5 Results at the Critical Value……Page 212
References……Page 215
Index……Page 223