Fundamentals of Complex Networks Models, Structures and Dynamics
, by Chen, Guanrong; Wang, Xiaofan; Li, Xiang
- ISBN: 9781118718117 | 1118718119
- Cover: Hardcover
- Copyright: 6/29/2015
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
• 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
GUANRONG CHEN City University of Hong Kong, Hong Kong SAR, China
XIAOFAN WANG Shanghai Jiao Tong University, Shanghai, China
XIANG LI Fudan University, Shanghai, China
XIAOFAN WANG Shanghai Jiao Tong University, Shanghai, China
XIANG LI Fudan University, Shanghai, China
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
What is included with this book?
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.
Please wait while the item is added to your bag...
