Fundamentals of Complex Networks

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

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