Networks · an Introduction by Newman, Mark -- Read -- Imperial Library of Trantor

Index

Title Page Copyright Page PREFACE CHAPTER 1 - INTRODUCTION

WHY ARE WE INTERESTED IN NETWORKS? SOME EXAMPLES OF NETWORKS PROPERTIES OF NETWORKS OUTLINE OF THIS BOOK

PART I - THE EMPIRICAL STUDY OF NETWORKS CHAPTER 2 - TECHNOLOGICAL NETWORKS

2.1 THE INTERNET 2.2 THE TELEPHONE NETWORK 2.3 POWER GRIDS 2.4 TRANSPORTATION NETWORKS 2.5 DELIVERY AND DISTRIBUTION NETWORKS

CHAPTER 3 - SOCIAL NETWORKS

3.1 THE EMPIRICAL STUDY OF SOCIAL NETWORKS 3.2 INTERVIEWS AND QUESTIONNAIRES 3.3 DIRECT OBSERVATION 3.4 DATA FROM ARCHIVAL OR THIRD-PARTY RECORDS 3.5 AFFILIATION NETWORKS 3.6 THE SMALL-WORLD EXPERIMENT 3.7 SNOWBALL SAMPLING, CONTACT TRACING, AND RANDOM WALKS

CHAPTER 4 - NETWORKS OF INFORMATION

4.1 THE WORLD WIDE WEB 4.2 CITATION NETWORKS 4.3 OTHER INFORMATION NETWORKS

CHAPTER 5 - BIOLOGICAL NETWORKS

5.1 BIOCHEMICAL NETWORKS 5.2 NEURAL NETWORKS 5.3 ECOLOGICAL NETWORKS

PART II - FUNDAMENTALS OF NETWORK THEORY CHAPTER 6 - MATHEMATICS OF NETWORKS

6.1 NETWORKS AND THEIR REPRESENTATION 6.2 THE ADJACENCY MATRIX 6.3 WEIGHTED NETWORKS 6.4 DIRECTED NETWORKS 6.5 HYPERGRAPHS 6.6 BIPARTITE NETWORKS 6.7 TREES 6.8 PLANAR NETWORKS 6.9 DEGREE 6.10 PATHS 6.11 COMPONENTS 6.12 INDEPENDENT PATHS, CONNECTIVITY, AND CUT SETS 6.13 THE GRAPH LAPLACIAN 6.14 RANDOM WALKS PROBLEMS

CHAPTER 7 - MEASURES AND METRICS

7.1 DEGREE CENTRALITY 7.2 EIGENVECTOR CENTRALITY 7.3 KATZ CENTRALITY 7.4 PAGERANK 7.5 HUBS AND AUTHORITIES 7.6 CLOSENESS CENTRALITY 7.7 BETWEENNESS CENTRALITY 7.8 GROUPS OF VERTICES 7.9 TRANSITIVITY 7.10 RECIPROCITY 7.11 SIGNED EDGES AND STRUCTURAL BALANCE 7.12 SIMILARITY 7.13 HOMOPHILY AND ASSORTATIVE MIXING PROBLEMS

CHAPTER 8 - THE LARGE-SCALE STRUCTURE OF NETWORKS

8.1 COMPONENTS 8.2 SHORTEST PATHS AND THE SMALL-WORLD EFFECT 8.3 DEGREE DISTRIBUTIONS 8.4 POWER LAWS AND SCALE-FREE NETWORKS 8.5 DISTRIBUTIONS OF OTHER CENTRALITY MEASURES 8.6 CLUSTERING COEFFICIENTS 8.7 ASSORTATIVE MIXING PROBLEMS

PART III - COMPUTER ALGORITHMS CHAPTER 9 - BASIC CONCEPTS OF ALGORITHMS

9.1 RUNNING TIME AND COMPUTATIONAL COMPLEXITY 9.2 STORING NETWORK DATA 9.3 THE ADJACENCY MATRIX 9.4 THE ADJACENCY LIST 9.5 TREES 9.6 OTHER NETWORK REPRESENTATIONS 9.7 HEAPS PROBLEMS

CHAPTER 10 - FUNDAMENTAL NETWORK ALGORITHMS

10.1 ALGORITHMS FOR DEGREES AND DEGREE DISTRIBUTIONS 10.2 CLUSTERING COEFFICIENTS 10.3 SHORTEST PATHS AND BREADTH-FIRST SEARCH 10.4 SHORTEST PATHS IN NETWORKS WITH VARYING EDGE LENGTHS 10.5 MAXIMUM FLOWS AND MINIMUM CUTS PROBLEMS

CHAPTER 11 - MATRIX ALGORITHMS AND GRAPH PARTITIONING

11.1 LEADING EIGENVECTORS AND EIGENVECTOR CENTRALITY 11.2 DIVIDING NETWORKS INTO CLUSTERS 11.3 GRAPH PARTITIONING 11.4 THE KERNIGHAN-LIN ALGORITHM 11.5 SPECTRAL PARTITIONING 11.6 COMMUNITY DETECTION 11.7 SIMPLE MODULARITY MAXIMIZATION 11.8 SPECTRAL MODULARITY MAXIMIZATION 11.9 DIVISION INTO MORE THAN TWO GROUPS 11.10 OTHER MODULARITY MAXIMIZATION METHODS 11.11 OTHER ALGORITHMS FOR COMMUNITY DETECTION PROBLEMS

PART IV - NETWORK MODELS CHAPTER 12 - RANDOM GRAPHS

12.1 RANDOM GRAPHS 12.2 MEAN NUMBER OF EDGES AND MEAN DEGREE 12.3 DEGREE DISTRIBUTION 12.4 CLUSTERING COEFFICIENT 12.5 GIANT COMPONENT 12.6 SMALL COMPONENTS 12.7 PATH LENGTHS 12.8 PROBLEMS WITH THE RANDOM GRAPH PROBLEMS

CHAPTER 13 - RANDOM GRAPHS WITH GENERAL DEGREE DISTRIBUTIONS

13.1 GENERATING FUNCTIONS 13.2 THE CONFIGURATION MODEL 13.3 EXCESS DEGREE DISTRIBUTION 13.4 CLUSTERING COEFFICIENT 13.5 GENERATING FUNCTIONS FOR DEGREE DISTRIBUTIONS 13.6 NUMBER OF SECOND NEIGHBORS OF A VERTEX 13.7 GENERATING FUNCTIONS FOR THE SMALL COMPONENTS 13.8 GIANT COMPONENT 13.9 SIZE DISTRIBUTION FOR SMALL COMPONENTS 13.10 POWER-LAW DEGREE DISTRIBUTIONS 13.11 DIRECTED RANDOM GRAPHS PROBLEMS

CHAPTER 14 - MODELS OF NETWORK FORMATION

14.1 PREFERENTIAL ATTACHMENT 14.2 THE MODEL OF BARABÁSI AND ALBERT 14.3 FURTHER PROPERTIES OF PREFERENTIAL ATTACHMENT MODELS 14.4 EXTENSIONS OF PREFERENTIAL ATTACHMENT MODELS 14.5 VERTEX COPYING MODELS 14.6 NETWORK OPTIMIZATION MODELS PROBLEMS

CHAPTER 15 - OTHER NETWORK MODELS

15.1 THE SMALL-WORLD MODEL 15.2 EXPONENTIAL RANDOM GRAPHS PROBLEMS

PART V - PROCESSES ON NETWORKS CHAPTER 16 - PERCOLATION AND NETWORK RESILIENCE

16.1 PERCOLATION 16.2 UNIFORM RANDOM REMOVAL OF VERTICES 16.3 NON-UNIFORM REMOVAL OF VERTICES 16.4 PERCOLATION IN REAL-WORLD NETWORKS 16.5 COMPUTER ALGORITHMS FOR PERCOLATION PROBLEMS

CHAPTER 17 - EPIDEMICS ON NETWORKS

17.1 MODELS OF THE SPREAD OF DISEASE 17.2 THE SI MODEL 17.3 THE SIR MODEL 17.4 THE SIS MODEL 17.5 THE SIRS MODEL 17.6 EPIDEMIC MODELS ON NETWORKS 17.7 LATE-TIME PROPERTIES OF EPIDEMICS ON NETWORKS 17.8 LATE-TIME PROPERTIES OF THE SIR MODEL 17.9 TIME-DEPENDENT PROPERTIES OF EPIDEMICS ON NETWORKS 17.10 TIME-DEPENDENT PROPERTIES OF THE SI MODEL 17.11 TIME-DEPENDENT PROPERTIES OF THE SIR MODEL 17.11.1 DEGREE-BASED APPROXIMATION FOR THE SIR MODEL 17.12 TIME-DEPENDENT PROPERTIES OF THE SIS MODEL PROBLEMS

CHAPTER 18 - DYNAMICAL SYSTEMS ON NETWORKS

18.1 DYNAMICAL SYSTEMS 18.2 DYNAMICS ON NETWORKS 18.3 DYNAMICS WITH MORE THAN ONE VARIABLE PER VERTEX 18.4 SYNCHRONIZATION PROBLEMS

CHAPTER 19 - NETWORK SEARCH

19.1 WEB SEARCH 19.2 SEARCHING DISTRIBUTED DATABASES 19.3 MESSAGE PASSING PROBLEMS

REFERENCES INDEX