Complex networks such as the Internet, WWW, transportation networks, power grids, biological neural networks, and scientific cooperation networks of all kinds provide challenges for future technological development.
* The first systematic presentation of dynamical evolving networks, with many up-to-date applications and homework projects to enhance study
* The authors are all very active and well-known in the rapidly evolving field of complex networks
* Complex networks are becoming an increasingly important area of research
* Presented in a logical, constructive style, from basic through to complex, examining algorithms, through to construct networks and research challenges of the future
Inhaltsverzeichnis
About the Authors xi
Preface xiii
Acknowledgements xv
Part I FUNDAMENTAL THEORY
1 Introduction 3
1. 1 Background and Motivation 3
1. 2 A Brief History of Complex Network Research 5
1. 2. 1 The Kö nigsburg Seven-Bridge Problem 5
1. 2. 2 Random Graph Theory 7
1. 2. 3 Small-World Experiments 7
1. 2. 4 Strengths of Weak Ties 10
1. 2. 5 Heterogeneity and the WWW 10
1. 3 New Era of Complex-Network Studies 11
Exercises 13
References 13
2 Preliminaries 15
2. 1 Elementary Graph Theory 15
2. 1. 1 Background 15
2. 1. 2 Basic Concepts 15
2. 1. 3 Adjacency, Incidence and Laplacian Matrices 24
2. 1. 4 Degree Correlation and Assortativity 26
2. 1. 5 Some Basic Results on Graphs 31
2. 1. 6 Eulerian and Hamiltonian Graphs 35
2. 1. 7 Plane and Planar Graphs 37
2. 1. 8 Trees and Bipartite Graphs 39
2. 1. 9 Directed Graphs 41
2. 1. 10 Weighted Graphs 45
2. 1. 11 Some Applications 46
2. 2 Elementary Probability and Statistics 52
2. 2. 1 Probability Preliminaries 52
2. 2. 2 Statistics Preliminaries 58
2. 2. 3 Law of Large Numbers and Central Limit Theorem 59
2. 2. 4 Markov Chains 61
2. 3 Elementary Dynamical Systems Theory 62
2. 3. 1 Background and Motivation 62
2. 3. 2 Some Analytical Tools 70
2. 3. 3 Chaos in Nonlinear Systems 72
2. 3. 4 Kolmogorov-Sinai Entropy 77
2. 3. 5 Some Examples of Chaotic Systems 78
2. 3. 6 Stabilities of Nonlinear Systems 85
Exercises 90
References 100
3 Network Topologies: Basic Models and Properties 103
3. 1 Introduction 103
3. 2 Regular Networks 103
3. 3 ER Random-Graph Model 105
3. 4 Small-World Network Models 108
3. 4. 1 WS Small-World Network Model 108
3. 4. 2 NW Small-World Network Model 108
3. 4. 3 Statistical Properties of Small-World Network Models 109
3. 5 Navigable Small-World Network Model 112
3. 6 Scale-Free Network Models 114
3. 6. 1 BA Scale-Free Network Model 114
3. 6. 2 Robustness versus Fragility 118
3. 6. 3 Modified BA Models 122
3. 6. 4 A Simple Model with Power-Law Degree Distribution 126
3. 6. 5 Local-World and Multi-Local-World Network Models 126
Exercises 133
References 135
Part II APPLICATIONS - SELECTED TOPICS
4 Internet: Topology and Modeling 139
4. 1 Introduction 139
4. 2 Topological Properties of the Internet 141
4. 2. 1 Power-Law Node-Degree Distribution 141
4. 2. 2 Hierarchical Structure 143
4. 2. 3 Rich-Club Structure 145
4. 2. 4 Disassortative Property 147
4. 2. 5 Coreness and Betweenness 148
4. 2. 6 Growth of the Internet 151
4. 2. 7 Router-Level Internet Topology 152
4. 2. 8 Geographic Layout of the Internet 153
4. 3 Random-Graph Network Topology Generator 155
4. 4 Structural Network Topology Generators 156
4. 4. 1 Tiers Topology Generator 157
4. 4. 2 Transit-Stub Topology Generator 158
4. 5 Connectivity-Based Network Topology Generators 159
4. 5. 1 Inet 160
4. 5. 2 BRITE Model 161
4. 5. 3 GLP Model 163
4. 5. 4 PFP Model 165
4. 5. 5 TANG Model 166
4. 6 Multi-Local-World Model 167
4. 6. 1 Theoretical Considerations 167
4. 6. 2 Numerical Results with Comparison 169
4. 6. 3 Performance Comparison 176
4. 7 HOT Model 178
4. 8 Dynamical Behaviors of the Internet Topological Characteristics 181
4. 9 Traffic Fluctuation on Weighted Networks 181
4. 9. 1 Weighted Networks 183
4. 9. 2 GRD Model 183
4. 9. 3 Data Traffic Fluctuations 184
References 190
5 Epidemic Spreading Dynamics 195
5. 1 Introduction 195
5. 2 Epidemic Threshold Theory 196
5. 2. 1 Epidemic (SI, SIS, SIR) Models 196
5. 2. 2 Epidemic Thresholds on Homogenous Networks 197
5. 2. 3 Statistical Data Analysis 198
5. 2. 4 Epidemic Thresholds on Heterogeneous Networks 199
5. 2. 5 Epidemic Thresholds on BA Networks 200
5. 2. 6 Epidemic Thresholds on Finite-Sized Scale-Free Networks 202
5. 2. 7 Epidemic Thresholds on Correlated Networks 202
5. 2. 8 SIR Model of Epidemic Spreading 203
5. 2. 9 Epidemic Spreading on Quenched Networks 205
5. 3 Epidemic Spreading on Spatial Networks 206
5. 3. 1 Spatial Networks 206
5. 3. 2 Spatial Network Models for Infectious Diseases 207
5. 3. 3 Impact of Spatial Clustering on Disease Transmissions 209
5. 3. 4 Large-Scale Spatial Epidemic Spreading 211
5. 3. 5 Impact of Human Location-Specific Contact Patterns 212
5. 4 Immunization on Complex Networks 213
5. 4. 1 Random Immunization 213
5. 4. 2 Targeted Immunization 213
5. 4. 3 Acquaintance Immunization 215
5. 5 Computer Virus Spreading over the Internet 215
5. 5. 1 Random Constant-Spread Model 216
5. 5. 2 A Compartment-Based Model 217
5. 5. 3 Spreading Models of Email Viruses 219
5. 5. 4 Effects of Computer Virus on Network Topologies 221
References 222
6 Community Structures 225
6. 1 Introduction 225
6. 1. 1 Various Scenarios in Real-World Social Networks 225
6. 1. 2 Generalization of Assortativity 226
6. 2 Community Structure and Modularity 230
6. 2. 1 Community Structure 230
6. 2. 2 Modularity 230
6. 2. 3 Modularity of Weighted and Directed Networks 233
6. 3 Modularity-Based Community Detecting Algorithms 234
6. 3. 1 CNM Scheme 234
6. 3. 2 BGLL Scheme 236
6. 3. 3 Multi-Slice Community Detection 237
6. 3. 4 Detecting Spatial Community Structures 240
6. 4 Other Community Partitioning Schemes 240
6. 4. 1 Limitations of the Modularity Measure 240
6. 4. 2 Clique Percolation Scheme 242
6. 4. 3 Edge-Based Community Detection Scheme 244
6. 4. 4 Evaluation Criteria for Community Detection Algorithms 249
6. 5 Some Recent Progress 253
References 253
7 Network Games 257
7. 1 Introduction 257
7. 2 Two-Player/Two-Strategy Evolutionary Games on Networks 261
7. 2. 1 Introduction to Games on Networks 261
7. 2. 2 Two-Player/Two-Strategy Games on Regular Lattices 261
7. 2. 3 Two-Player/Two-Strategy Games on BA Scale-Free Networks 264
7. 2. 4 Two-Player/Two-Strategy Games on Correlated Scale-Free Networks 267
7. 2. 5 Two-Player/Two-Strategy Games on Clustered Scale-Free Networks 271
7. 3 Multi-Player/Two-Strategy Evolutionary Games on Networks 273
7. 3. 1 Introduction to Public Goods Game 273
7. 3. 2 Multi-Player/Two-Strategy Evolutionary Games on BA Networks 273
7. 3. 3 Multi-Player/Two-Strategy Evolutionary Games on Correlated Scale-free Networks 276
7. 3. 4 Multi-Player/Two-Strategy Evolutionary Games on Clustered Scale-free Networks 280
7. 4 Adaptive Evolutionary Games on Networks 284
References 286
8 Network Synchronization 289
8. 1 Introduction 289
8. 2 Complete Synchronization of Continuous-Time Networks 290
8. 2. 1 Complete Synchronization of General Continuous-Time Networks 293
8. 2. 2 Complete Synchronization of Linearly Coupled Continuous-Time Networks 297
8. 3 Complete Synchronization of Some Typical Dynamical Networks 299
8. 3. 1 Complete Synchronization of Regular Networks 300
8. 3. 2 Synchronization of Small-World Networks 301
8. 3. 3 Synchronization of Scale-Free Networks 302
8. 3. 4 Complete Synchronization of Local-World Networks 306
8. 4 Phase Synchronization 306
8. 4. 1 Phase Synchronization of the Kuramoto Model 308
8. 4. 2 Phase Synchronization of Small-World Networks 310
8. 4. 3 Phase Synchronization of Scale-Free Networks 310
8. 4. 4 Phase Synchronization of Nonuniformly Coupled Networks 314
References 316
9 Network Control 319
9. 1 Introduction 319
9. 2 Spatiotemporal Chaos Control on Regular CML 319
9. 3 Pinning Control of Complex Networks 322
9. 3. 1 Augmented Network Approach 322
9. 3. 2 Pinning Control of Scale-Free Networks 323
9. 4 Pinning Control of General Complex Networks 326
9. 4. 1 Stability Analysis of General Networks under Pinning Control 326
9. 4. 2 Pinning and Virtual Control of General Networks 328
9. 4. 3 Pinning and Virtual Control of Scale-Free Networks 330
9. 5 Time-Delay Pinning Control of Complex Networks 333
9. 6 Consensus and Flocking Control 335
References 340
10 Brief Introduction to Other Topics 343
10. 1 Human Opinion Dynamics 343
10. 2 Human Mobility and Behavioral Dynamics 346
10. 3 Web PageRank, SiteRank and BrowserRank 348
10. 3. 1 Methods Based on Edge Analysis 348
10. 3. 2 Methods Using Users' Behavior Data 348
10. 4 Recommendation Systems 349
10. 5 Network Edge Prediction 350
10. 6 Living Organisms and Bionetworks 351
10. 7 Cascading Reactions on Networks 353
References 356
Index 363