Random Networks for Communication

Contents
page ix
Preface
List of notation xi
1 Introduction 1
1.1 Discrete network models 3
1.1.1 The random tree 3
1.1.2 The random grid 5
1.2 Continuum network models 6
1.2.1 Poisson processes 6
1.2.2 Nearest neighbour networks 10
1.2.3 Poisson random connection networks 11
1.2.4 Boolean model networks 12
1.2.5 Interference limited networks 13
1.3 Information-theoretic networks 14
1.4 Historical notes and further reading 15
2 Phase transitions in infinite networks 17
2.1 The random tree; infinite growth 17
2.2 The random grid; discrete percolation 21
2.3 Dependencies 29
2.4 Nearest neighbours; continuum percolation 31
2.5 Random connection model 37
2.6 Boolean model 48
2.7 Interference limited networks 51
2.7.1 Mapping on a square lattice 56
2.7.2 Percolation on the square lattice 58
2.7.3 Percolation of the interference model 62
2.7.4 Bound on the percolation region 63
2.8 Historical notes and further reading 66
3 Connectivity of finite networks 69
3.1 Preliminaries: modes of convergence and Poisson approximation 69
3.2 The random grid 71
3.2.1 Almost connectivity 71
3.2.2 Full connectivity 72
3.3 Boolean model 77
3.3.1 Almost connectivity 78
3.3.2 Full connectivity 81
3.4 Nearest neighbours; full connectivity 88
3.5 Critical node lifetimes 92
3.6 A central limit theorem 98
3.7 Historical notes and further reading 98
4 More on phase transitions 100
4.1 Preliminaries: Harris–FKG Inequality 100
4.2 Uniqueness of the infinite cluster 101
4.3 Cluster size distribution and crossing paths 107
4.4 Threshold behaviour of fixed size networks 114
4.5 Historical notes and further reading 119
5 Information flow in random networks 121
5.1 Information-theoretic preliminaries 121
5.1.1 Channel capacity 122
5.1.2 Additive Gaussian channel 124
5.1.3 Communication with continuous time signals 127
5.1.4 Information-theoretic random networks 129
5.2 Scaling limits; single source–destination pair 131
5.3 Multiple source–destination pairs; lower bound 136
5.3.1 The highway 138
5.3.2 Capacity of the highway 139
5.3.3 Routing protocol 142
5.4 Multiple source–destination pairs; information-theoretic upper
bounds 146
5.4.1 Exponential attenuation case 148
5.4.2 Power law attenuation case 151
5.5 Historical notes and further reading 155
6 Navigation in random networks 157
6.1 Highway discovery 157
6.2 Discrete short-range percolation (large worlds) 159
6.3 Discrete long-range percolation (small worlds) 161
6.3.1 Chemical distance, diameter, and navigation length 162
6.3.2 More on navigation length 167
6.4 Continuum long-range percolation (small worlds) 171
6.5 The role of scale invariance in networks 181
6.6 Historical notes and further reading 182
Appendix 185
A.1 Landau’s order notation 185
A.2 Stirling’s formula 185
A.3 Ergodicity and the ergodic theorem 185
A.4 Deviations from the mean 187
A.5 The Cauchy–Schwartz inequality 188
A.6 The singular value decomposition 189
References 190
Index 194

Another Statistic Books
Another Social Network Books
Download