The theory of random graphs began in the late 1950s in several papers by Erdos and Renyi. In the late twentieth century, the notion of six degrees of separation, meaning that any two people on the planet can be connected by a short chain of people who know each other, inspired Strogatz and Watts to define the small world random graph in which each site is connected to k close neighbors, but also has long-range connections. At about the same time, it was observed in human social and sexual networks and on the Internet that the number of neighbors of an individual or computer has a power law distribution. This inspired Barabasi and Albert to define the preferential attachment model, which has these properties. These two papers have led to an explosion of research. While this literature is extensive, many of the papers are based on simulations and nonrigorous arguments. The purpose of this book is to use a wide variety of mathematical argument to obtain insights into the properties of these graphs. A unique feature of this book is the interest in the dynamics of process taking place on the graph in addition to their geometric properties, such as connectedness and diameter.
Author(s): Rick Durrett
Series: Cambridge Series in Statistical and Probabilistic Mathematics
Edition: 1
Publisher: Cambridge University Press
Year: 2006
Language: English
Pages: 222
Cover......Page 1
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 < beta < 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
