Fundamentals of Complex Networks

GUANRONG CHEN City University of Hong Kong, Hong Kong SAR, ChinaXIAOFAN WANG Shanghai Jiao Tong University, Shanghai, ChinaXIANG LI Fudan University, Shanghai, China

• About the Authors xiPreface xiiiAcknowledgements xvPart I FUNDAMENTAL THEORY1 Introduction 31.1 Background and Motivation 31.2 A Brief History of Complex Network Research 51.2.1 The Königsburg Seven-Bridge Problem 51.2.2 Random Graph Theory 71.2.3 Small-World Experiments 71.2.4 Strengths of Weak Ties 101.2.5 Heterogeneity and the WWW 101.3 New Era of Complex-Network Studies 11Exercises 13References 132 Preliminaries 152.1 Elementary Graph Theory 152.1.1 Background 152.1.2 Basic Concepts 152.1.3 Adjacency, Incidence and Laplacian Matrices 242.1.4 Degree Correlation and Assortativity 262.1.5 Some Basic Results on Graphs 312.1.6 Eulerian and Hamiltonian Graphs 352.1.7 Plane and Planar Graphs 372.1.8 Trees and Bipartite Graphs 392.1.9 Directed Graphs 412.1.10 Weighted Graphs 452.1.11 Some Applications 462.2 Elementary Probability and Statistics 522.2.1 Probability Preliminaries 522.2.2 Statistics Preliminaries 582.2.3 Law of Large Numbers and Central Limit Theorem 592.2.4 Markov Chains 612.3 Elementary Dynamical Systems Theory 622.3.1 Background and Motivation 622.3.2 Some Analytical Tools 702.3.3 Chaos in Nonlinear Systems 722.3.4 Kolmogorov-Sinai Entropy 772.3.5 Some Examples of Chaotic Systems 782.3.6 Stabilities of Nonlinear Systems 85Exercises 90References 1003 Network Topologies: Basic Models and Properties 1033.1 Introduction 1033.2 Regular Networks 1033.3 ER Random-Graph Model 1053.4 Small-World Network Models 1083.4.1 WS Small-World Network Model 1083.4.2 NW Small-World Network Model 1083.4.3 Statistical Properties of Small-World Network Models 1093.5 Navigable Small-World Network Model 1123.6 Scale-Free Network Models 1143.6.1 BA Scale-Free Network Model 1143.6.2 Robustness versus Fragility 1183.6.3 Modified BA Models 1223.6.4 A Simple Model with Power-Law Degree Distribution 1263.6.5 Local-World and Multi-Local-World Network Models 126Exercises 133References 135Part II APPLICATIONS - SELECTED TOPICS4 Internet: Topology and Modeling 1394.1 Introduction 1394.2 Topological Properties of the Internet 1414.2.1 Power–Law Node-Degree Distribution 1414.2.2 Hierarchical Structure 1434.2.3 Rich-Club Structure 1454.2.4 Disassortative Property 1474.2.5 Coreness and Betweenness 1484.2.6 Growth of the Internet 1514.2.7 Router-Level Internet Topology 1524.2.8 Geographic Layout of the Internet 1534.3 Random-Graph Network Topology Generator 1554.4 Structural Network Topology Generators 1564.4.1 Tiers Topology Generator 1574.4.2 Transit–Stub Topology Generator 1584.5 Connectivity-Based Network Topology Generators 1594.5.1 Inet 1604.5.2 BRITE Model 1614.5.3 GLP Model 1634.5.4 PFP Model 1654.5.5 TANG Model 1664.6 Multi-Local-World Model 1674.6.1 Theoretical Considerations 1674.6.2 Numerical Results with Comparison 1694.6.3 Performance Comparison 1764.7 HOT Model 1784.8 Dynamical Behaviors of the Internet Topological Characteristics 1814.9 Traffic Fluctuation on Weighted Networks 1814.9.1 Weighted Networks 1834.9.2 GRD Model 1834.9.3 Data Traffic Fluctuations 184References 1905 Epidemic Spreading Dynamics 1955.1 Introduction 1955.2 Epidemic Threshold Theory 1965.2.1 Epidemic (SI, SIS, SIR) Models 1965.2.2 Epidemic Thresholds on Homogenous Networks 1975.2.3 Statistical Data Analysis 1985.2.4 Epidemic Thresholds on Heterogeneous Networks 1995.2.5 Epidemic Thresholds on BA Networks 2005.2.6 Epidemic Thresholds on Finite-Sized Scale-Free Networks 2025.2.7 Epidemic Thresholds on Correlated Networks 2025.2.8 SIR Model of Epidemic Spreading 2035.2.9 Epidemic Spreading on Quenched Networks 2055.3 Epidemic Spreading on Spatial Networks 2065.3.1 Spatial Networks 2065.3.2 Spatial Network Models for Infectious Diseases 2075.3.3 Impact of Spatial Clustering on Disease Transmissions 2095.3.4 Large-Scale Spatial Epidemic Spreading 2115.3.5 Impact of Human Location-Specific Contact Patterns 2125.4 Immunization on Complex Networks 2135.4.1 Random Immunization 2135.4.2 Targeted Immunization 2135.4.3 Acquaintance Immunization 2155.5 Computer Virus Spreading over the Internet 2155.5.1 Random Constant-Spread Model 2165.5.2 A Compartment-Based Model 2175.5.3 Spreading Models of Email Viruses 2195.5.4 Effects of Computer Virus on Network Topologies 221References 2226 Community Structures 2256.1 Introduction 2256.1.1 Various Scenarios in Real-World Social Networks 2256.1.2 Generalization of Assortativity 2266.2 Community Structure and Modularity 2306.2.1 Community Structure 2306.2.2 Modularity 2306.2.3 Modularity of Weighted and Directed Networks 2336.3 Modularity-Based Community Detecting Algorithms 2346.3.1 CNM Scheme 2346.3.2 BGLL Scheme 2366.3.3 Multi-Slice Community Detection 2376.3.4 Detecting Spatial Community Structures 2406.4 Other Community Partitioning Schemes 2406.4.1 Limitations of the Modularity Measure 2406.4.2 Clique Percolation Scheme 2426.4.3 Edge-Based Community Detection Scheme 2446.4.4 Evaluation Criteria for Community Detection Algorithms 2496.5 Some Recent Progress 253References 2537 Network Games 2577.1 Introduction 2577.2 Two-Player/Two-Strategy Evolutionary Games on Networks 2617.2.1 Introduction to Games on Networks 2617.2.2 Two-Player/Two-Strategy Games on Regular Lattices 2617.2.3 Two-Player/Two-Strategy Games on BA Scale-Free Networks 2647.2.4 Two-Player/Two-Strategy Games on Correlated Scale-Free Networks 2677.2.5 Two-Player/Two-Strategy Games on Clustered Scale-Free Networks 2717.3 Multi-Player/Two-Strategy Evolutionary Games on Networks 2737.3.1 Introduction to Public Goods Game 2737.3.2 Multi-Player/Two-Strategy Evolutionary Games on BA Networks 2737.3.3 Multi-Player/Two-Strategy Evolutionary Games on Correlated Scale-free Networks 2767.3.4 Multi-Player/Two-Strategy Evolutionary Games on Clustered Scale-free Networks 2807.4 Adaptive Evolutionary Games on Networks 284References 2868 Network Synchronization 2898.1 Introduction 2898.2 Complete Synchronization of Continuous-Time Networks 2908.2.1 Complete Synchronization of General Continuous-Time Networks 2938.2.2 Complete Synchronization of Linearly Coupled Continuous-Time Networks 2978.3 Complete Synchronization of Some Typical Dynamical Networks 2998.3.1 Complete Synchronization of Regular Networks 3008.3.2 Synchronization of Small-World Networks 3018.3.3 Synchronization of Scale-Free Networks 3028.3.4 Complete Synchronization of Local-World Networks 3068.4 Phase Synchronization 3068.4.1 Phase Synchronization of the Kuramoto Model 3088.4.2 Phase Synchronization of Small-World Networks 3108.4.3 Phase Synchronization of Scale-Free Networks 3108.4.4 Phase Synchronization of Nonuniformly Coupled Networks 314References 3169 Network Control 3199.1 Introduction 3199.2 Spatiotemporal Chaos Control on Regular CML 3199.3 Pinning Control of Complex Networks 3229.3.1 Augmented Network Approach 3229.3.2 Pinning Control of Scale-Free Networks 3239.4 Pinning Control of General Complex Networks 3269.4.1 Stability Analysis of General Networks under Pinning Control 3269.4.2 Pinning and Virtual Control of General Networks 3289.4.3 Pinning and Virtual Control of Scale-Free Networks 3309.5 Time-Delay Pinning Control of Complex Networks 3339.6 Consensus and Flocking Control 335References 34010 Brief Introduction to Other Topics 34310.1 Human Opinion Dynamics 34310.2 Human Mobility and Behavioral Dynamics 34610.3 Web PageRank, SiteRank and BrowserRank 34810.3.1 Methods Based on Edge Analysis 34810.3.2 Methods Using Users’ Behavior Data 34810.4 Recommendation Systems 34910.5 Network Edge Prediction 35010.6 Living Organisms and Bionetworks 35110.7 Cascading Reactions on Networks 353References 356Index 363