Fundamentals of Complex Networks

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

Autorentext
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

Klappentext

This book introduces readers to the notion of complex networks including the Internet, transportation networks, power grids, biological neural networks, and scientific cooperation networks, which provide challenges for future technological development. The recent spate of collapses in power grids and ongoing virus attacks on the Internet illustrates the need for knowledge about mathematical modeling, behavioral analysis, optimized planning and performance control in such networks. For advancement of methodologies and techniques, it has become clear that more fundamental knowledge will be needed in an engineering context about how dynamical networks work and how they can be controlled.

The book is divided into two parts: Part I consists of three chapters, presenting background information and basic materials needed to learn the subject, with a variety of exercises for illustrating fundamental concepts and familiarizing related modeling and analysis techniques. Part II contains several selected application-oriented stand-alone topics.

• A systematic presentation of dynamical evolving networks, with many up-to-date applications and homework projects to enhance study

• Complex networks are becoming an increasingly important area of research and applications

• Presented in a logical and constructive style, from basic graphs through to complex networks, and exploring research challenges of the future

Fundamentals of Complex Networks: Models, Structures and Dynamics is ideal for upper-level undergraduates, postgraduates and researchers in electrical and electronic engineering, mechanical engineering, computer science, information science, social science, applied physics and applied mathematics. The book is intended to be informal, emphasizing basic ideas and methodologies with elementary and sometimes heuristic mathematical arguments, easily readable by anyone having minimal knowledge of calculus, linear algebra and ordinary differential equations.

Inhalt

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 PowerLaw 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 TransitStub 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 Epidem...