.

0 (hodnocen0 x )

BK

1st print.

Oxford : Oxford University Press, 2010

xi, 772 s. : il. ; 25 cm

ISBN 978-0-19-920665-0 (váz.)

Obsahuje bibliografické odkazy a rejstřík

000194534

Contents // Preface x // 1 Introduction 1 // 1 The empirical study of networks 15 // 2 Technological networks 17 // 2.1 The Internet... 18 // 2.2 The telephone network... 28 // 2.3 Power grids... 31 // 2.4 Transportation networks... 32 // 2.5 Delivery and distribution networks... 33 // 3 Social networks 36 // 3.1 The empirical study of social networks... 36 // 3.2 Interviews and questionnaires... 39 // 3.3 Direct observation... 46 // 3.4 Data from archival or third-party records... 47 // 3.5 Affiliation networks... 53 // 3.6 The small-world experiment... 54 // 3.7 Snowball sampling, contact tracing, and random walks ... 58 // 4 Networks of information 63 // 4.1 The World Wide Web... 63 // 4.2 Citation networks... 67 // 4.3 Other information networks... 72 // 5 Biological networks 78 // 5.1 Biochemical networks ... 78 // 5.2 Neural networks... 94 // 5.3 Ecological networks... 99 // v // II Fundamentals of network theory 107 // 6 Mathematics of networks IO9 // 6.1 Networks and their representation... 109 // 6.2 The adjacency matrix... 1? // 6.3 Weighted networks... 122 // 6.4 Directed networks... ?4 // 6.5 Hypergraphs... 122 // 6.6 Bipartite networks... I23 // 6.7 Trees ... I27 // 6.8 Planar networks... I29 // 6.9 Degree... I33 // 6.10 Paths... 136 // 6.11 Components... 142 // 6.12 Independent paths, connectivity, and cut sets... 145 // 6.13 The graph Laplacian... 152 // 6.14 Random walks... I57 // 7 Measures and metrics 168 // 7.1 Degree centrality ... 16g // 7.2 Eigenvector centrality...

I69 // 7.3 Katz centrality... 172 // 7.4 PageRank... I75 // 7.5 Hubs and authorities... 17g // 7.6 Closeness centrality... Igl // 7.7 Betweenness centrality... Ig5 // 7.8 Groups of vertices... I93 // 7.9 Transitivity... 19g // 7.10 Reciprocity... 204 // 7.11 Signed edges and structural balance...2?6 // 7.12 Similarity... 211 // 7.13 Homophily and assortative mixing...220 // 8 The large-scale structure of networks 235 // 8.1 Components... 235 // 8.2 Shortest paths and the small-world effect...241 // 8.3 Degree distributions ... 243 // 8.4 Power laws and scale-free networks...247 // 8.5 Distributions of other centrality measures...261 // 8.6 Clustering coefficients ... 262 // Contents // 8.7 Assortative mixing... 266 // III Computer algorithms 273 // 9 Basic concepts of algorithms 275 // 9.1 Running time and computational complexity...278 // 9.2 Storing network data...282 // 9.3 The adjacency matrix... 283 // 9.4 The adjacency list... 286 // 9.5 Trees ... 290 // 9.6 Other network representations ...298 // 9.7 Heaps...301 // 10 Fundamental network algorithms 308 // 10.1 Algorithms for degrees and degree distributions...308 // 10.2 Clustering coefficients ... 310 // 10.3 Shortest paths and breadth-first search...315 // 10.4 Shortest paths in networks with varying edge lengths...329 // 10.5 Maximum flows and minimum cuts...333 // 11 Matrix algorithms and graph partitioning 345 // 11.1 Leading eigenvectors and eigenvector centrality...345 // 11.2 Dividing networks into clusters...354

// 11.3 Graph partitioning... 358 // 11.4 The Kernighan-Lin algorithm...360 // 11.5 Spectral partitioning ... 364 // 11.6 Community detection... 371 // 11.7 Simple modularity maximization...373 // 11.8 Spectral modularity maximization...375 // 11.9 Division into more than two groups...378 // 11.10 Other modularity maximization methods...380 // 11.11 Other algorithms for community detection...382 // IV Network models 395 // 12 Random graphs 397 // 12.1 Random graphs... 398 // 12.2 Mean number of edges and mean degree ...400 // 12.3 Degree distribution...401 // vii // Contents // 12.4 Clustering coefficient... 402 // 12.5 Giant component...403 // 12.6 Small components... 408 // 12.7 Path lengths... 419 // 12.8 Problems with the random graph...423 // 13 Random graphs with general degree distributions 428 // 13.1 Generating functions... 429 // 13.2 The configuration model...434 // 13.3 Excess degree distribution... 445 // 13.4 Clustering coefficient... 449 // 13.5 Generating functions for degree distributions...450 // 13.6 Number of second neighbors of a vertex...451 // 13.7 Generating functions for the small components...456 // 13.8 Giant component... 480 // 13.9 Size distribution for small components...465 // 13.10 Power-law degree distributions...470 // 13.11 Directed random graphs...473 // 14 Models of network formation 486 // 14.1 Preferential attachment... 487 // 14.2 The model of Barabási and Albert...500 // 14.3 Further properties of preferential attachment models ...503

// 14.4 Extensions of preferential attachment models...514 // 14.5 Vertex copying models... 534 // 14.6 Network optimization models...541 // 15 Other network models 552 // 15.1 The small-world model... 552 // 15.2 Exponential random graphs... 565 // V Processes on networks 589 // 16 Percolation and network resilience 591 // 16.1 Percolation... 592 // 16.2 Uniform random removal of vertices...594 // 16.3 Non-uniform removal of vertices... 609 // 16.4 Percolation in real-world networks... 615 // 16.5 Computer algorithms for percolation...616 // iii // Contents // 17 Epidemics on networks 627 // 17.1 Models of the spread of disease... 627 // 17.2 The SI model... 628 // 17.3 The SIR model... 631 // 17.4 The SIS model... 636 // 17.5 The SIRS model... 637 // 17.6 Epidemic models on networks...639 // 17.7 Late-time properties of epidemics on networks...640 // 17.8 Late-time properties of the SIR model... 642 // 17.9 Time-dependent properties of epidemics on networks...648 // 17.10 Time-dependent properties of the SI model...648 // 17.11 Time-dependent properties of the SIR model...661 // 17.12 Time-dependent properties of the SIS model ...669 // 18 Dynamical systems on networks 676 // 18.1 Dynamical systems... 677 // 18.2 Dynamics on networks... 686 // 18.3 Dynamics with more than one variable per vertex... 695 // 18.4 Synchronization... 701 // 19 Network search 705 // 19.1 Web search... 705 // 19.2 Searching distributed databases... 709 // 19.3 Message passing... 713 // References 727

// Index 74Q // ix