Part I Theory .................................................. 1
1 Introduction ................................................. 3
1.1 What are networks? ...................................... 3
1.2 When did the story begin? ............................... 4
1.3 A formal definition ..................................... 6
1.4 Why do we study their structure? ........................ 9
1.5 How can we speak their 'language'? ..................... 14
2 Adjacency relations in networks ............................. 25
2.1 Node adjacency relationship ............................ 25
2.2 Degree distributions ................................... 27
2.3 Degree-degree correlations ............................. 31
2.4 Link adjacency and beyond .............................. 36
2.5 Discrete Laplacian operator ............................ 37
2.6 Spectral properties of networks ........................ 39
3 Metric and topological structure of networks ................ 47
3.1 Shortest path distance ................................. 47
3.2 Resistance distance .................................... 50
3.3 Generalized network distances .......................... 55
3.4 Topological structure of networks ...................... 57
4 Fragments (subgraphs) in complex networks ................... 73
4.1 Network 'graphlets' .................................... 74
4.2 Network motifs ......................................... 76
4.3 Closed walks and subgraphs ............................. 78
4.4 Counting small undirected subgraphs analytically ....... 79
4.5 Fragment ratios ........................................ 82
5 Accounting for all parts (subgraphs) ........................ 89
5.1 The Estrada index ...................................... 90
5.2 Parameterised Estrada index ............................ 95
5.3 Network entropy and free energy ........................ 97
5.4 Network returnability ................................. 103
5.5 A brief on matrix functions ........................... 106
6 Communicability functions in networks ...................... 109
6.1 Network communicability ............................... 109
6.2 Communicability in directed and weighted networks ..... 113
6.3 Generalised communicability functions ................. 114
6.4 Communicability based on network vibrations ........... 115
7 Centrality measures ........................................ 121
7.1 Degree centrality ..................................... 121
7.2 Centrality beyond nearest-neighbours .................. 125
7.3 Closeness Centrality .................................. 140
7.4 Betweenness Centrality ................................ 142
7.5 Information Centrality ................................ 146
8 Global network invariants .................................. 149
8.1 Adjacency-based invariants ............................ 149
8.2 Distance-based invariants ............................. 159
8.3 Clumpiness of central nodes ........................... 161
8.4 Self-similarity of complex networks ................... 166
9 Expansion and network classes .............................. 171
9.1 Network expansion ..................................... 171
9.2 Universal topological classes of network .............. 173
9.3 Topological classification of real-world networks ..... 181
10 Community structure of networks ............................ 187
10.1 Network partition methods ............................. 190
10.2 Methods based on link Centrality ...................... 198
10.3 Methods based on modularity ........................... 203
10.4 Clustering based on similarity ........................ 206
10.5 Communities based on communicability .................. 209
11 Network bipartivity ........................................ 215
11.1 Bipartivity measures .................................. 216
11.2 How do we find bipartitions in networks? .............. 220
11.3 Bipartitions in undirected networks ................... 224
11.4 Bipartitions in directed networks ..................... 227
12 Random models of networks .................................. 233
12.1 'Classical' random networks ........................... 233
12.2 Small-world random networks ........................... 238
12.3 'Scale-free' networks ................................. 243
12.4 Random geometric networks ............................. 250
12.5 Other random models ................................... 252
Part II Applications ......................................... 257
13 Genetic networks ........................................... 259
13.1 A primer on gene networks ............................. 259
13.2 Topological properties of gene coexpression networks .. 263
13.3 Topological properties of gene regulatory networks .... 267
13.4 Other gene networks ................................... 274
14 Protein residue networks ................................... 277
14.1 A primer on protein structure ......................... 277
14.2 Protein residue networks .............................. 280
14.3 Small-worldness of residue networks ................... 282
14.4 Degree distributions of residue networks .............. 285
14.5 Centrality in residue networks ........................ 287
14.6 Global topological properties ......................... 295
15 Protein-protein interaction networks ....................... 301
15.1 A primer on protein-protein interactions .............. 301
15.2 Global structure of PPI networks ...................... 304
15.3 Subgraph-based techniques in PPI networks ............. 311
15.4 Bipartite structures in PPI networks .................. 316
15.5 Local structure of PPI networks ....................... 319
16 The structure of reaction networks ......................... 325
16.1 Organic chemical reaction networks .................... 326
16.2 Reaction networks in the atmospheres of astronomical
bodies ................................................ 330
16.3 Metabolic networks .................................... 333
17 Anatomical networks ........................................ 345
17.1 Intercellular networks ................................ 345
17.2 Vascular networks ..................................... 353
17.3 Brain networks ........................................ 355
18 Ecological networks ........................................ 373
18.1 Global topological properties ......................... 374
18.2 Searching for keystone species ........................ 383
18.3 Landscape networks .................................... 389
18.4 Other network-based ecological studies ................ 395
19 Social and economic networks ............................... 399
19.1 Brief on socioeconomic network data ................... 400
19.2 Global topology of social networks .................... 401
19.3 Social network communities ............................ 408
19.4 Centrality in social networks ......................... 412
19.5 Economic networks ..................................... 415
Appendix
A.l Brain networks ........................................ 423
A.2 Ecological networks ................................... 423
A.3 Informational networks ................................ 424
A.4 PPI networks .......................................... 424
A.5 Protein residue networks .............................. 425
A.6 Social and economic networks .......................... 425
A.7 Technological networks ................................ 426
A.8 Transcription networks ................................ 426
A.9 Software .............................................. 426
References .................................................... 429
Index ......................................................... 457
| 
