Dynamical Processes on Complex Networks

The availability of large data sets has allowed researchers to uncover complex properties such as large-scale fluctuations and heterogeneities in many networks, leading to the breakdown of standard theoretical frameworks and models. Until recently these systems were considered as haphazard sets of points and connections. Recent advances have generated a vigorous research effort in understanding the effect of complex connectivity patterns on dynamical phenomena. This book presents a comprehensive account of these effects. A vast number of systems, from the brain to ecosystems, power grids and the Internet, can be represented as large complex networks. This book will interest graduate students and researchers in many disciplines, from physics and statistical mechanics to mathematical biology and information science. Its modular approach allows readers to readily access the sections of most interest to them, and complicated maths is avoided so the text can be easily followed by non-experts in the subject. 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 The Availability Of Large Data Sets Has Allowed Researchers To Uncover Complex Properties Such As Large-scale Fluctuations And Heterogeneities In Many Networks, Leading To The Breakdown Of Standard Theoretical Frameworks And Models. Until Recently These Systems Were Considered As Haphazard Sets Of Points And Connections. Recent Advances Have Generated A Vigorous Research Effort In Understanding The Effect Of Complex Connectivity Patterns On Dynamical Phenomena. This Book Presents A Comprehensive Account Of These Effects. The Book Will Interest Graduate Students And Researchers In Many Disciplines, From Physics And Statistical Mechanics, To Mathematical Biology And Information Science. Its Modular Approach Allows Readers To Readily Access The Sections Of Most Interest To Them, And Complicated Maths Is Avoided So The Text Can Be Easily Followed By Non-experts In The Subject.--jacket. Networks And Graphs -- Networks And Complexity -- Network Models -- Introduction To Dynamical Processes : Theory And Simulation -- Phase Transitions On Complex Networks -- Resilience And Robustness Of Networks -- Synchronization Phenomena In Networks -- Walking And Searching On Networks -- Epidemic Spreading In Population Networks -- Social Networks And Collective Behavior -- Traffic On Complex Networks -- Networks In Biology : From The Cell To Ecosystems -- Postface : Critically Examining Complex Networks Science. Alain Barrat, Marc Barthélemy, Alessandro Vespignani. Includes Bibliographical References (p. 313-343) And Index. "The availability of large data sets has allowed researchers to uncover complex properties such as large-scale fluctuations and heterogeneities in many networks, leading to the breakdown of standard theoretical frameworks and models. Until recently these systems were considered as haphazard sets of points and connections. Recent advances have generated a vigorous research effort in understanding the effect of complex connectivity patterns on dynamical phenomena. This book presents a comprehensive account of these effects." "The book will interest graduate students and researchers in many disciplines, from physics and statistical mechanics, to mathematical biology and information science. Its modular approach allows readers to readily access the sections of most interest to them, and complicated maths is avoided so the text can be easily followed by non-experts in the subject."-- Jaquette The availability of large data sets have allowed researchers to uncover complex properties such as large scale fluctuations and heterogeneities in many networks which have lead to the breakdown of standard theoretical frameworks and models. Until recently these systems were considered as haphazard sets of points and connections. Recent advances have generated a vigorous research effort in understanding the effect of complex connectivity patterns on dynamical phenomena. For example, a vast number of everyday systems, from the brain to ecosystems, power grids and the Internet, can be represented as large complex networks. This new and recent account presents a comprehensive explanation of these effects. The availability of large data sets has allowed researchers to uncover complex properties such as large-scale fluctuations and heterogeneities in many networks, leading to the breakdown of standard theoretical frameworks and models. Until recently these systems were consdered a haphazard sets of pionts and connections. Recent advances have generated a vigourous research effort in understanding the effect of complex connectivity patterns on dynamical phenomena. This book presents a comprehensive account of these effects