Networks constitute the backbone of complex systems, from the human brain to computer communications, transport infrastructures to online social systems and metabolic reactions to financial markets. Characterising their structure improves our understanding of the physical, biological, economic and social phenomena that shape our world. Rigorous and thorough, this textbook presents a detailed overview of the new theory and methods of network science. Covering algorithms for graph exploration, node ranking and network generation, among others, the book allows students to experiment with network models and real-world data sets, providing them with a deep understanding of the basics of network theory and its practical applications. Systems of growing complexity are examined in detail, challenging students to increase their level of skill. An engaging presentation of the important principles of network science makes this the perfect reference for researchers and undergraduate and graduate students in physics, mathematics, engineering, biology, neuroscience and the social sciences.

Preface xi

Introduction xii

The Backbone of a Complex System xii

Complex Networks Are All Around Us xiv

Why Study Complex Networks? xv

Overview of the Book xvii

Acknowledgements xx

1 Graphs and Graph Theory 1

1.1 What Is a Graph? 1

1.2 Directed, Weighted and Bipartite Graphs 9

1.3 Basic Definitions 13

1.4 Trees 17

1.5 Graph Theory and the Bridges of Konigsberg 19

1.6 How to Represent a Graph 23

1.7 What We Have Learned and Further readings 28

Problems 28

2 Centrality Measures 31

2.1 The Importance of Being Central 31

2.2 Connected Graphs and Irreducible Matrices 34

2.3 Degree and Eigenvector Centrality 39

2.4 Measures Based on Shortest Paths 47

2.5 Movie Actors 56

2.6 Group Centrality 62

2.7 What We Have Learned and Further readings 64

Problems 65

3 Random Graphs 69

3.1 Erdos and Renyi(ER) Models 69

3.2 Degree Distribution 76

3.3 Trees, Cycles and Complete Subgraphs 79

3.4 Giant Connected Component 84

3.5 Scientific Collaboration Networks 90

3.6 Characteristic Path Length 94

3.7 What We Have Learned and Further Readings 103

Problems 104

4 Small-World Networks 107

4.1 Six Degrees of Separation 107

4.2 The Brain of a Worm 112

4.3 Clustering Coefficient 116

4.4 The Watts-Strogatz(WS) Model 127

4.5 Variations to the Theme 135

4.6 Navigating Small-World Networks 144

4.7 What We Have Learned and Further Readings 148

Problems 148

5 Generalised Random Graphs 151

5.1 The World Wide Web 151

5.2 Power-Law Degree Distributions 161

5.3 The Configuration Model 171

5.4 Random Graphs with Arbitrary Degree Distribution 178

5.5 Scale-Free Random Graphs 184

5.6 Probability Generating Functions 188

5.7 What We Have Learned and Further readings 202

Problems 204

6 Models of Growing Graphs 206

6.1 Citation Networks and the Linear Preferential Attachment 206

6.2 The Barabasi-Albert(BA) Model 215

6.3 The Importance of Being Preferential and Linear 224

6.4 Variations to the Theme 230

6.5 Can Latecomers Make It? The Fitness Model 241

6.6 Optimisation Models 248

6.7 What We Have Learned and Further Readings 252

Problems 253

7 Degree correlations 257

7.1 The Internet and Other Correlated Networks 257

7.2 Dealing with Correlated Networks 262

7.3 Assortative and Disassortative Networks 268

7.4 Newmans Correlation Coefficient 275

7.5 Models of Networks with Degree-Degree Correlations 285

7.6 What We Have Learned and Further Reading 290

Problems 291

8 Cydes and Motifs 294

8.1 Counting Cycles 294

8.2 Cycles in Scale-Free Networks 303

8.3 Spatial Networks of Urban Streets 307

8.4 Transcription Regulation Networks 316

8.5 Motif Analysis 324

8.6 What We Have Learned and Further Readings 329

Problems 330

9 Community Structure 332

9.1 Zacharys Karate Club 332

9.2 The Spectral Bisection Method 336

9.3 Hierarchical Clusterin 342

9.4 The Girvan-Newman Method 349

9.5 Computer Generated Benchmarks 354

9.6 The Modular 357

9.7 A Local Method 365

9.8 What We Have Learned and Further readings 369

Problems 371

10 Weighted Networks 374

10.1 Tuning the Interactions 374

10.2 Basic Measures 381

10.3 Motifs and Communities 387

10.4 Growing Weighted Networks 393

10.5 Networks of Stocks in a Financial Market 401

10.6 What We Have Learned and Further readings 407

Problems 408

Appendices 410

A.1 Problems, Algorithms and Time Complexity 410

A.2 A Simple Introduction to Computational

Complexity 420

A.3 Elem entary Data Structures 425

A.4 Basic Operations with Sparse matrices 440

A.5 Eigenvalue and Eigenvector Computation 444

A.6 Computation of Shortest Paths 452

A.7 Computation of Node Betweenness 462

A.8 Component Analysis 467

A.9 Random Sampling 474

A.10 Erdos and Renyi Random Graph Models 485

A.11 The Watts-Strogatz Small-World Model 489

A.12 The Configuration Model 492

A.13 Growing Unweighted Graphs 499

A.14 Random Graphs with Degree-Degree Correlations 506

A.15 Johnson's Algorithm to Enumerate Cycles 508

A.16 Motifs Analysis 511

A.17 Girvan-Newman Algorithm 515

A.18 Greedy Modularity Optimisation 519

A.19 Label Propagation 524

A.20 Kruskal,s Algorithm for Minimum Spanning Tree 528

A.21 Models for Weighted Networks 531

List of programs 533

References 535

Author Index 550

Index 552

Vito Latora is Professor of Applied Mathematics and Chair of Complex Systems at Queen Mary University of London. Noted for his research in statistical physics and in complex networks, his current interests include time-varying and multiplex networks, and their applications to socio-economic systems and to the human brain. PA\Vincenzo Nicosia is a Lecturer in Networks and Data Analysis at the School of Mathematical Sciences at Queen Mary University of London. His research spans several aspects of network structure and dynamics, and his recent interests include multi-layer networks and their applications to big data modelling. PA\Giovanni Russo is Professor of Numerical Analysis in the Department of Mathematics and Computer Science at the Università degli Studi di Catania, Italy, focusing on numerical methods for partial differential equations, with particular application to hyperbolic and kinetic problems.

中科院文献情报中心