Networks

Cover......Page 1
Networks......Page 4
Copyright......Page 5
Contents......Page 6
Preface......Page 10
 Examples of networks......Page 14
 What can we learn from networks?......Page 20
 Properties of networks......Page 21
 Outline of this book......Page 24
Part I. The Empirical study of networks......Page 26
 Chapter 2. Technological networks......Page 27
  2.1 The Internet......Page 28
   2.1.1 Measuring Internet structure using traceroute......Page 30
   2.1.2 Measuring Internet structure using routing tables......Page 34
  2.2 The telephone network......Page 38
  2.3 Power grids......Page 40
  2.4 Transportation networks......Page 41
  2.5 Delivery and distribution networks......Page 42
  3.1 The World Wide Web......Page 45
  3.2 Citation networks......Page 50
   3.2.1 Patent and legal citations......Page 52
  3.3 Other information networks......Page 54
   3.3.1 Peer-to-peer networks......Page 55
   3.3.2 Recommender networks......Page 57
   3.3.3 Keyword indexes......Page 58
  4.1 The empirical study of social networks......Page 60
  4.2 Interviews and questionnaires......Page 64
   4.2.1 Ego-centered networks......Page 68
  4.3 Direct observation......Page 70
  4.4 Data from archival or third-party records......Page 71
  4.5 Affiliation networks......Page 73
  4.6 The small-world experiment......Page 75
  4.7 Snowball sampling, contact tracing, and random walks......Page 78
   5.1.1 Metabolic networks......Page 83
   5.1.2 Protein–protein interaction networks......Page 89
   5.1.3 Genetic regulatory networks......Page 93
   5.1.4 Other biochemical networks......Page 99
   5.2.1 Networks of neurons......Page 101
   5.2.2 Networks of functional connectivity in the brain......Page 107
  5.3 Ecological networks......Page 108
   5.3.1 Food webs......Page 109
   5.3.2 Other ecological networks......Page 113
Part II. Fundamentals of network theory......Page 116
  6.1 Networks and their representation......Page 118
  6.2 The adjacency matrix......Page 119
  6.3 Weighted networks......Page 121
  6.4 Directed networks......Page 123
   6.4.1 Acyclic networks......Page 124
  6.5 Hypergraphs......Page 127
  6.6 Bipartite networks......Page 128
   6.6.1 The incidence matrix and network projections......Page 129
  6.7 Multilayer and dynamic networks......Page 131
  6.8 Trees......Page 134
  6.9 Planar networks......Page 136
  6.10 Degree......Page 139
   6.10.1 Density and sparsity......Page 141
   6.10.2 Directed networks......Page 143
  6.11 Walks and paths......Page 144
   6.11.1 Shortest paths......Page 145
  6.12 Components......Page 146
   6.12.1 Components in directed networks......Page 147
  6.13 Independent paths, connectivity, and cut sets......Page 150
   6.13.1 Maximum flows and cut sets on weighted networks......Page 154
  6.14 The graph Laplacian......Page 155
   6.14.1 Graph partitioning......Page 156
   6.14.2 Network visualization......Page 158
   6.14.3 Random walks......Page 160
   6.14.4 Resistor networks......Page 161
   6.14.5 Properties of the graph Laplacian......Page 163
  Exercises......Page 166
 Chapter 7. Measures and metrics......Page 171
   7.1.2 Eigenvector centrality......Page 172
   7.1.3 Katz centrality......Page 176
   7.1.4 PageRank......Page 178
   7.1.5 Hubs and authorities......Page 181
   7.1.6 Closeness centrality......Page 183
   7.1.7 Betweenness centrality......Page 186
  7.2 Groups of nodes......Page 190
   7.2.2 Cores......Page 191
   7.2.3 Components and k-components......Page 193
  7.3 Transitivity and the clustering coefficient......Page 196
   7.3.1 Local clustering and redundancy......Page 199
  7.4 Reciprocity......Page 202
  7.5 Signed edges and structural balance......Page 203
  7.6 Similarity......Page 207
   7.6.1 Measures of structural equivalence......Page 208
   7.6.2 Measures of regular equivalence......Page 211
  7.7 Homophily and assortative mixing......Page 214
   7.7.1 Assortative mixing by unordered characteristics......Page 216
   7.7.2 Assortative mixing by ordered characteristics......Page 219
   7.7.3 Assortative mixing by degree......Page 222
  Exercises......Page 224
 Chapter 8. Computer algorithms......Page 231
  8.1 Software for network analysis and visualization......Page 232
  8.2 Running time and computational complexity......Page 234
  8.3 Storing network data......Page 238
   8.3.1 The adjacency matrix......Page 239
   8.3.2 The adjacency list......Page 242
   8.3.3 Other network representations......Page 246
  8.4 Algorithms for basic network quantities......Page 250
   8.4.1 Degrees......Page 251
   8.4.2 Clustering coefficients......Page 252
   8.5.1 Description of the breadth-first search algorithm......Page 254
   8.5.2 A naive implementation......Page 256
   8.5.3 A better implementation......Page 257
   8.5.4 Variants of breadth-first search......Page 260
   8.5.5 Finding shortest paths......Page 262
   8.5.6 Betweenness centrality......Page 265
  8.6 Shortest paths in networks with varying edge lengths......Page 270
  8.7 Maximum flows and minimum cuts......Page 275
   8.7.1 The augmenting path algorithm......Page 276
   8.7.2 Implementation and running time......Page 278
   8.7.3 Why the algorithm gives correct answers......Page 279
   8.7.4 Finding independent paths and minimum cut sets......Page 281
   8.7.5 Node-independent paths......Page 282
  Exercises......Page 285
 Chapter 9. Network statistics and measurement error......Page 288
  9.1 Types of error......Page 289
  9.2 Sources of error......Page 291
   9.3.1 Conventional statistics of measurement error......Page 294
   9.3.2 The method of maximum likelihood......Page 295
   9.3.3 Errors in network data......Page 298
   9.3.4 The EM algorithm......Page 299
   9.3.5 Independent edge errors......Page 303
   9.3.6 Example......Page 306
   9.3.7 Estimation of other quantities......Page 308
   9.3.8 Other error models......Page 309
  9.4 Correcting errors......Page 310
   9.4.1 Link prediction......Page 311
   9.4.2 Node disambiguation......Page 313
  Exercises......Page 314
  10.1 Components......Page 317
   10.1.1 Components in directed networks......Page 321
  10.2 Shortest paths and the small-world effect......Page 323
  10.3 Degree distributions......Page 326
  10.4 Power laws and scale-free networks......Page 330
   10.4.1 Detecting and visualizing power laws......Page 332
   10.4.2 Properties of power-law distributions......Page 338
  10.5 Distributions of other centrality measures......Page 343
  10.6 Clustering coefficients......Page 345
   10.6.1 Local clustering coefficient......Page 347
  10.7 Assortative mixing......Page 348
  Exercises......Page 350
Part III. Network models......Page 354
 Chapter 11. Random graphs......Page 355
  11.1 Random graphs......Page 356
  11.2 Mean number of edges and mean degree......Page 358
  11.3 Degree distribution......Page 359
  11.5 Giant component......Page 360
   11.5.1 Can there be more than one giant component?......Page 367
  11.6 Small components......Page 368
  11.7 Path lengths......Page 373
  11.8 Problems with the random graph......Page 377
  Exercises......Page 379
 Chapter 12. The configuration model......Page 382
  12.1 The configuration model......Page 383
   12.1.1 Edge probability in the configuration model......Page 386
   12.1.2 Random graphs with given expected degree......Page 388
  12.2 Excess degree distribution......Page 390
  12.3 Clustering coefficient......Page 394
  12.4 Locally tree-like networks......Page 395
  12.5 Number of second neighbors of a node......Page 396
  12.6 Giant component......Page 397
   12.6.1 Example......Page 400
   12.6.2 General solution for the size of the giant component......Page 402
  12.7 Small components......Page 404
   12.7.1 Degrees of nodes in the small components......Page 405
   12.7.2 Average number of nodes reached along an edge......Page 406
  12.8 Networks with power-law degree distributions......Page 408
  12.9 Diameter......Page 412
   12.10.1 Generating functions......Page 414
   12.10.2 Examples......Page 415
   12.10.3 Power-law distributions......Page 416
   12.10.4 Normalization and moments......Page 417
   12.10.5 Products of generating functions......Page 419
   12.10.6 Generating functions for degree distributions......Page 420
   12.10.7 Number of second neighbors of a node......Page 421
   12.10.8 Generating functions for the small components......Page 424
   12.10.9 Complete distribution of small component sizes......Page 427
   12.11.1 Directed networks......Page 429
   12.11.3 Acyclic networks......Page 432
   12.11.4 Degree correlations......Page 433
   12.11.6 Assortative mixing and community structure......Page 434
   12.11.7 Dynamic networks......Page 437
   12.11.8 The small-world model......Page 438
  Exercises......Page 441
 Chapter 13. Models of network formation......Page 447
  13.1 Preferential attachment......Page 448
   13.1.1 Degree distribution of Price’s model......Page 451
   13.1.2 Computer simulation of Price’s model......Page 456
  13.2 The model of Barabasi and Albert......Page 461
  13.3 Time evolution of the network and the first mover effect......Page 464
  13.4 Extensions of preferential attachment models......Page 471
   13.4.1 Addition of extra edges......Page 472
   13.4.2 Removal of edges......Page 474
   13.4.3 Non-linear preferential attachment......Page 479
  13.5 Node copying models......Page 485
  13.6 Network optimization models......Page 492
   13.6.1 Trade-offs between travel time and cost......Page 493
   Exercises......Page 500
Part IV. Applications......Page 506
 Chapter 14. Community structure......Page 507
  14.1 Dividing networks into groups......Page 508
  14.2 Modularity maximization......Page 511
   14.2.1 The form of the modularity function......Page 513
   14.2.2 A simple modularity maximization algorithm......Page 515
   14.2.3 Spectral modularity maximization......Page 518
   14.2.4 Division into more than two groups......Page 522
   14.2.5 The Louvain algorithm......Page 524
   14.2.6 Resolution limit for modularity maximization......Page 525
  14.3 Methods based on information theory......Page 528
  14.4 Methods based on statistical inference......Page 533
   14.4.1 Community detection using statistical inference......Page 535
  14.5 Other algorithms for community detection......Page 542
   14.5.1 Betweenness-based methods......Page 543
   14.5.2 Hierarchical clustering......Page 547
  14.6 Measuring algorithm performance......Page 551
   14.6.1 Tests on real-world networks......Page 552
   14.6.2 Artificial test networks......Page 555
   14.6.3 Quantifying performance......Page 557
   14.6.4 Comparison of community detection algorithms......Page 563
   14.7.1 Overlapping communities......Page 564
   14.7.2 Hierarchical communities......Page 566
   14.7.3 Core–periphery structure......Page 568
   14.7.4 Latent spaces, stratified networks, and rank structure......Page 571
  Exercises......Page 579
  15.1 Percolation......Page 582
  15.2 Uniform random removal of nodes......Page 584
   15.2.1 Uniform removal in the configuration model......Page 587
  15.3 Non-uniform removal of nodes......Page 599
  15.4 Percolation in real-world networks......Page 606
  15.5 Computer algorithms for percolation......Page 607
   15.5.1 Results for real-world networks......Page 612
  Exercises......Page 615
 Chapter 16. Epidemics on networks......Page 620
  16.1 Models of the spread of infection......Page 621
   16.1.1 The SI model......Page 622
   16.1.2 The SIR model......Page 625
   16.1.3 Solution of the SIR model......Page 627
   16.1.4 Basic reproduction number......Page 629
   16.1.5 The SIS model......Page 630
   16.1.6 The SIRS model......Page 632
   16.1.8 Combinations of diseases......Page 633
   16.1.9 Complex contagion and the spread of information......Page 635
  16.2 Epidemic models on networks......Page 637
  16.3 Outbreak sizes and percolation......Page 638
   16.3.1 Outbreak sizes in the SIR model......Page 639
   16.3.2 SIR model and the configuration model......Page 642
   16.3.3 Coexisting diseases......Page 646
   16.3.4 Coinfection......Page 650
   16.3.5 Complex contagion......Page 652
  16.4 Time-dependent properties of epidemics on networks......Page 658
  16.5 Time-dependent properties of the SI model......Page 659
   16.5.1 Pair approximation......Page 663
   16.5.2 Degree-based approximation for the SI model......Page 667
  16.6 Time-dependent properties of the SIR model......Page 673
   16.6.1 Degree-based approximation for the SIR model......Page 675
  16.7 Time-dependent properties of the SIS model......Page 680
   16.7.1 Degree-based approximation for the SIS model......Page 682
  Exercises......Page 684
 Chapter 17. Dynamical systems on networks......Page 688
  17.1 Dynamical systems......Page 689
   17.1.1 Fixed points and linearization......Page 690
  17.2 Dynamics on networks......Page 698
   17.2.1 Linear stability analysis......Page 699
   17.2.2 Special cases......Page 701
   17.2.3 An example......Page 706
  17.3 Dynamics with more than one variable per node......Page 707
   17.3.1 Special cases......Page 709
  17.4 Spectra of networks......Page 711
  17.5 Synchronization......Page 714
  Exercises......Page 719
  18.1 Web search......Page 723
  18.2 Searching distributed databases......Page 726
   18.3.1 Kleinberg’s model......Page 731
   18.3.2 A hierarchical model for messages......Page 736
  Exercises......Page 743
References......Page 745
Index......Page 764