Dynamical Processes on Complex Networks

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 13
Acknowledgements......Page 17
List of abbreviations......Page 19
1.1 What is a network?......Page 21
1.2.1 Graphs and subgraphs......Page 22
1.2.2 Paths and connectivity......Page 25
1.2.3 Degree and centrality measures......Page 28
Betweenness centrality......Page 29
1.2.4 Clustering......Page 30
1.3 Statistical characterization of networks......Page 31
1.3.2 Betweenness distribution......Page 32
1.3.3 Mixing patterns and degree correlations......Page 33
1.3.4 Clustering spectrum......Page 37
1.3.5 Rich-club phenomenon......Page 38
1.4 Weighted networks......Page 39
2.1 Real-world systems......Page 44
2.1.1 Networks everywhere......Page 45
Social networks......Page 46
Transportation networks......Page 47
Internet......Page 49
World Wide Web......Page 51
Biological networks......Page 52
2.1.2 Measurements and biases......Page 53
2.2 Network classes......Page 54
2.2.1 Small-world yet clustered......Page 55
2.2.2 Heterogeneity and heavy tails......Page 57
2.2.3 Higher order statistical properties of networks......Page 63
2.3 The complicated and the complex......Page 67
3.1 Randomness and network models......Page 70
3.1.1 Generalized random graphs......Page 72
3.1.2 Fitness or “hidden variables” models......Page 73
3.1.3 The Watts–Strogatz model......Page 75
3.2 Exponential random graphs......Page 78
3.3 Evolving networks and the non-equilibrium approach......Page 80
3.3.1 The preferential attachment class of models......Page 84
3.3.2 Copy and duplication models......Page 88
3.3.3 Trade-off and optimization models......Page 90
3.4 Modeling higher order statistics and other attributes......Page 92
3.5 Modeling frameworks and model validation......Page 94
4.1 A microscopic approach to dynamical phenomena......Page 97
4.2 Equilibrium and non-equilibrium systems......Page 99
4.3 Approximate solutions of the Master Equation......Page 102
4.4 Agent-based modeling and numerical simulations......Page 105
5.1 Phase transitions and the Ising model......Page 112
5.2 Equilibrium statistical physics of critical phenomena......Page 116
5.2.1 Mean-field theory of phase transitions......Page 119
5.3.1 Small-world networks......Page 121
5.3.2 Networks with generic degree distributions......Page 124
5.4 Dynamics of ordering processes......Page 128
5.5 Phenomenological theory of phase transitions......Page 131
6.1 Damaging networks......Page 136
6.2 Percolation phenomena as critical phase transitions......Page 140
6.3 Percolation in complex networks......Page 144
6.4 Damage and resilience in networks......Page 146
6.5 Targeted attacks on large degree nodes......Page 149
6.5.1 Alternative ranking strategies......Page 152
6.5.2 Weighted networks......Page 154
6.6 Damage in real-world networks......Page 155
7.1 General framework......Page 156
7.2 Linearly coupled identical oscillators......Page 158
7.2.1 Small-world networks......Page 161
7.2.2 Degree fluctuations: the paradox of heterogeneity......Page 163
7.2.3 Degree-related asymmetry......Page 166
7.3 Non-linear coupling: firing and pulse......Page 168
7.4 Non-identical oscillators: the Kuramoto model......Page 171
7.4.1 The mean-field Kuramoto model......Page 173
7.4.2 The Kuramoto model on complex networks......Page 174
7.5 Synchronization paths in complex networks......Page 176
7.6 Synchronization phenomena as a topology probing tool......Page 178
8.1 Diffusion processes and random walks......Page 180
8.2 Diffusion in directed networks and ranking algorithms......Page 186
8.3 Searching strategies in complex networks......Page 190
8.3.1 Search strategies......Page 192
8.3.2 Search in a small world......Page 194
8.3.3 Taking advantage of complexity......Page 197
9.1 Epidemic models......Page 200
9.1.1 Compartmental models and the homogeneous assumption......Page 202
9.1.2 The linear approximation and the epidemic threshold......Page 206
9.2 Epidemics in heterogeneous networks......Page 209
9.2.1 The SI model......Page 210
9.2.2 The SIR and SIS models......Page 212
9.2.3 The effect of mixing patterns......Page 213
9.2.4 Numerical simulations......Page 215
9.3 The large time limit of epidemic outbreaks......Page 217
9.3.1 The SIS model......Page 218
9.3.2 The SIR model......Page 221
9.3.3 Epidemic models and phase transitions......Page 223
9.3.4 Finite size and correlations......Page 224
9.4.1 Uniform immunization......Page 227
9.4.2 Targeted immunization......Page 228
9.4.3 Immunization without global knowledge......Page 230
10.1 Social influence......Page 236
10.2 Rumor and information spreading......Page 238
10.3 Opinion formation and the Voter model......Page 245
10.4 The Axelrod model......Page 252
10.5 Prisoner’s dilemma......Page 255
10.6 Coevolution of opinions and network......Page 258
11.1 Traffic and congestion......Page 262
11.2 Traffic and congestion in distributed routing......Page 266
11.2.1 Heterogeneity and routing policies......Page 270
11.2.2 Adaptive (traffic-aware) routing policies......Page 273
11.3 Avalanches......Page 276
11.3.1 Breakdown models......Page 277
11.3.2 Avalanches by local failures......Page 279
11.3.3 Avalanche and routing dynamics......Page 280
11.3.4 Partial failures and recovery......Page 281
11.3.5 Reinforcement mechanisms......Page 283
11.4 Stylized models and real-world infrastructures......Page 284
12 Networks in biology: from the cell to ecosystems......Page 287
12.1 Cell biology and networks......Page 288
12.2 Flux-balance approaches and the metabolic activity......Page 291
12.3 Boolean networks and gene regulation......Page 294
12.4 The brain as a network......Page 299
12.5 Ecosystems and food webs......Page 302
12.5.1 Dynamics and stability of ecosystems......Page 307
12.5.2 Coupling topology and dynamics......Page 311
12.6 Future directions......Page 313
13 Postface: critically examining complex networks science......Page 314
Appendix 1 Random graphs......Page 318
Appendix 2 Generating functions formalism......Page 323
A3.1 Purely directed networks......Page 326
A3.2 General case......Page 328
Appendix 4 Laplacian matrix of a graph......Page 330
Appendix 5 Return probability and spectral density......Page 331
References......Page 333
Index......Page 364