Part Ⅰ FUNDAMENTAL THEORY 1 Introduction 1.1 Background and Motivation 1.2 A Brief History of Complex Network Research 1.2.1 The Konigsburg Seven-Bridge Problem 1.2.2 Random Graph Theory 1.2.3 Small-World Experiments 1.2.4 Strengths of Weak Ties 1.2.5 Heterogeneity and the WWW 1.3 New Era of Complex-Network Studies Exercises References 2 Preliminaries 2.1 Elementary Graph Theory 2.1.1 Background 2.1.2 Basic Concepts 2.1.3 Adjacency Incidence and Laplacian Matrices 2.1.4 Degree Correlation and Assortativity 2.1.5 Some Basic Results on Graphs 2.1.6 Eulerian and Hamiltonian Graphs 2.1.7 Plane and Planar Graphs 2.1.8 Trees and Bipartite Graphs 2.1.9 Directed Graphs 2.1.10 Weighted Graphs 2.1.11 Some Applications 2.2 Elementary Probability and Statistics 2.2.1 Probability Preliminaries 2.2.2 Statistics Preliminaries 2.2.3 Law of Large Numbers and Central Limit Theorem 2.2.4 Markov Chains 2.3 Elementary Dynamical Systems Theory 2.3.1 Background and Morivation 2.3.2 Some Analytical Tools 2.3.3 Chaos in Nonlinear Systems 2.3.4 Kolmogorov-Sinai Entropy 2.3.5 Some Examples of Chaoric Sysrems 2.3.6 Stabilities of Nonlinear Systems Exercises References 3 Network Topologies: Basic Models and Properties 3.1 Introduction 3.2 Regular Networks 3.3 ER Random-Graph Model 3.4 Small-World Network Models 3.4.1 WS Small-World Nerwork Model 3.4.2 NW Small- World Network Model 3.4.3 Sratistical Properties of Small-World Network Models 3.5 Navigable Small-World Network Model 3.6 Scale-Free Network Models 3.6.1 BA Scale-Free Network Model 3.6.2 Robustness versus Fragiliry 3.6.3 Modified BA Models 3.6.4 A Simple Model with Power-Law Deg-ree Distribution 3.6.5 Local- World and Multi-Local- Wortd Network Models Exercises References
Part Ⅱ APPLICATIONS-SELECTED TOPICS 4 Internet: Topology and Modeling 4.1 Introduction 4.2 Topological Properties of the Internet 4.2.1 Power-Low Node-Degree Distribution 4.2.2 Hierarchical Structure 4.2.3 Rich-Club Structure 4.2.4 Disassortative Property 4.2.5 Coreness and Betweenness 4.2.6 Growrh of the Internet 4.2.7 Router-Level Internet Topology 4.2.8 Geographic Layout of the Interner 4.3 Random-Graph Network Topology Generator 4.4 Structural Network Topology Generators 4.4.1 Tiers Topology Generaror 4.4.2 Transir-Stub Topology Generator 4.5 Connectivity-Based Network Topology Generators 4.5.1 Inet 4.5.2 BRITE Model 4.5.3 GLP Model 4.5.4 PFP Model 4.5.5 TANG Model Index