Thursday, February 17, 2011

Random Graph Dynamics






Contents
Preface page vii
1. Overview 1
1.1 Introduction to the Introduction 1
1.2 Erd ̈ s, R ́ nyi, Molloy, and Reed
o e 3
1.3 Six Degrees, Small Worlds 7
1.4 Power Laws, Preferential Attachment 11
1.5 Epidemics and Percolation 15
1.6 Potts Models and the Contact Process 18
1.7 Random Walks and Voter Models 20
1.8 CHKNS Model 21
2. Erd ̈ s–R ́ nyi Random Graphs
o e 27
2.1 Branching Processes 27
2.2 Cluster Growth as an Epidemic 34
2.3 Cluster Growth as a Random Walk 37
2.4 Diameter of the Giant Component 43
2.5 CLT for the Giant Component 46
2.6 Combinatorial Approach 50
2.7 Critical Regime 56
2.8 Threshold for Connectivity 62
3. Fixed Degree Distributions 70
3.1 Definitions and Heuristics 70
3.2 Proof of Phase Transition 75
3.3 Subcritical Estimates 82
3.4 Distances: Finite Variance 84
3.5 Epidemics 85
4. Power Laws 90
4.1 Barab ́ si-Albert Model
a 90
4.2 Related Models 93
4.3 Martingales and Urns 99
4.4 Scale-Free Trees 105
4.5 Distances: Power Laws 2 < β < 3 110
4.6 Diameter: Barab ́ si-Albert Model
a 116
4.7 Percolation, Resilience 121
4.8 SIS Epidemic 125
5. Small Worlds 132
5.1 Watts and Strogatz Model 132
5.2 Path Lengths 134
5.3 Epidemics 140
5.4 Ising and Potts Models 144
5.5 Contact Process 148
6. Random Walks 153
6.1 Spectral Gap 153
6.2 Conductance 156
6.3 Fixed Degree Distribution 159
6.4 Preferential Attachment Graph 164
6.5 Connected Erd ̈ s–R ́ nyi Graphs
o e 169
6.6 Small Worlds 171
6.7 Only Degrees 2 and 3 175
6.8 Hitting Times 177
6.9 Voter Models 181
7. CHKNS Model 187
7.1 Heuristic Arguments 187
7.2 Proof of the Phase Transition 190
7.3 Subcritical Estimates 193
7.4 Kosterlitz-Thouless Transition 197
7.5 Results at the Critical Value 200
References 203
Index 211


Another Graph Theory Books
Download

No comments:

Post a Comment

Related Posts with Thumbnails

Put Your Ads Here!