Complex Networks: Structure, Robustness and Function

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
1 Introduction......Page 11
1.2 Scale-free processes and fractal structures......Page 14
Part I Random Network Models......Page 17
2.1 Erdos–Rényi graphs......Page 19
2.2 Scale-free networks......Page 20
2.3 Diameter and fractal dimensions......Page 22
2.4 Random graphs as a model of real networks......Page 23
2.5 Outlook and applications......Page 24
3.1.1 Computer networks and the Internet......Page 26
3.1.3 Virtual technological networks and the WWW......Page 27
3.1.6 Biological networks......Page 29
3.2.1 Degree distribution......Page 31
3.2.4 Clustering......Page 34
3.2.6 Modular and hierarchical networks......Page 36
3.3 Betweenness centrality what is your importance in the network?......Page 37
3.4 Conclusions......Page 39
4.2.1 Introduction......Page 41
4.2.2 Clustering in a small-world network......Page 43
4.3.1 Introduction......Page 45
4.3.2 Random regular graphs......Page 46
4.3.3 Generalized random graphs......Page 47
4.3.4 A related model......Page 48
4.5.1 Introduction......Page 49
4.5.2 Generalized randomly directed graphs......Page 50
4.6.1 Introduction......Page 51
4.6.2 Defining the model......Page 52
4.6.3 Additional methods......Page 54
4.6.4 Random geometrical graphs, continuum percolation, and ad hoc networks......Page 55
4.7 Hierarchical and fractal networks......Page 58
Exercises......Page 59
5.1 The Barabasi–Albert model......Page 61
5.1.1 Analysis......Page 62
5.2.1 Non-linear growing models......Page 64
5.2.3 Copying models......Page 66
5.3 Linearized chord diagram (LCD)......Page 67
5.4 Fitness models......Page 69
Exercises......Page 72
Part II Structure and Robustness of Complex Networks......Page 73
6.1 Introduction......Page 75
6.2 Minimal distance networks......Page 77
6.3 Random scale-free networks......Page 79
6.4.1 Description......Page 82
6.4.2 Theory......Page 83
6.4.3 Simulations......Page 86
6.4.4 Bounds and implications......Page 87
6.5 Discussion and conclusions......Page 89
Exercises......Page 90
7 Self-similarity in complex networks......Page 91
8 Distances in geographically embedded networks......Page 98
9.2.1 Condition for the existence of a giant component......Page 101
9.2.2 Generating functions......Page 103
9.3.1 Description......Page 104
Exercises......Page 105
10.1 Introduction......Page 107
10.2.2 Critical threshold for percolation......Page 108
10.2.3 Scale-free networks......Page 110
10.3.1 Description......Page 111
10.3.2 Theory......Page 112
10.4.1 Introduction......Page 115
10.4.2 Size of the giant component at criticality......Page 116
10.4.3 Finite component size distribution......Page 119
10.4.5 Fractal and upper critical dimensions......Page 121
10.5 Percolation in networks with correlations......Page 124
10.5.1 Percolation in correlated scale-free networks......Page 125
10.6 k-core percolation: fault tolerant networks......Page 126
10.7 Conclusions......Page 130
Exercises......Page 131
11.1 Introduction......Page 133
11.3 The giant component......Page 134
11.4 Percolation in directed scale-free networks......Page 135
11.5 Critical exponents......Page 138
11.5.1 Size of the giant component......Page 139
11.5.2 Finite component sizes......Page 140
Exercises......Page 141
12.1 Introduction......Page 143
12.2 Random weighted networks......Page 144
12.3 Correlated weighted networks......Page 150
Exercises......Page 152
Part III Network function: Dynamics and Applications......Page 153
13.1 Introduction......Page 155
13.2 Optimization analysis......Page 156
13.3 General results......Page 159
13.4 Summary......Page 162
14.1 Introduction......Page 164
14.2 Epidemic dynamics and epidemiological models......Page 165
14.2.1 The SIS model......Page 166
The SIS model in networks......Page 167
The SIR model as bond percolation......Page 168
14.2.3 The SIRS model......Page 169
Exercises......Page 170
15.1 Random immunization......Page 171
15.2 Targeted immunization: choosing the right people to immunize......Page 172
15.3.1 Description......Page 173
15.3.2 Analysis......Page 174
15.3.3 Discussion......Page 177
15.3.4 Practical issues......Page 179
15.5 Conclusion......Page 180
Exercises......Page 182
16.1 Introduction......Page 183
16.2 The Ising model in complex networks......Page 184
16.2.1 The critical temperature......Page 186
16.2.2 The critical exponents......Page 187
16.3 Summary......Page 189
Exercises......Page 190
17.1 The spectrum of the adjacency matrix......Page 191
17.2 The Laplacian......Page 192
17.3 The spectral gap and diffusion on graphs......Page 194
17.3.1 The spectral gap......Page 195
17.3.2 Expander graphs......Page 196
17.3.3 Expansion of random networks......Page 199
17.5 Summary......Page 201
Exercises......Page 202
18.2 Searching using degrees......Page 203
18.3 Searching in networks using shortcuts......Page 205
18.4 Summary......Page 208
Exercises......Page 209
19 Biological networks and network motifs......Page 210
19.3 Network motifs......Page 211
19.4 Summary......Page 216
A.1 Probabilities and distributions......Page 217
A.2 Continuous variables and probability densities......Page 218
A.3 Conditional probabilities and Bayes’ rule......Page 219
A.4 Branching processes......Page 220
A.5.1 Abelian and Tauberian theorems......Page 221
Exercises......Page 222
Exercises......Page 223
C.1.1 Generating scale-free networks......Page 225
C.1.2 Simulation of random breakdown......Page 226
C.3 Networks with different properties: Metropolis style algorithms......Page 227
C.4 Finding shortest and optimal paths......Page 229
C.6 Finding communities in networks......Page 230
References......Page 232
Index......Page 246