Large scale structure and dynamics of complex networks: from information technology to finance and natural science

Contents......Page 8
Preface......Page 6
Introduction......Page 14
1.2 Basic definitions......Page 18
1.3.1 Weighted, directed and oriented graphs......Page 20
1.3.2 Subgraphs......Page 21
1.4 Paths and cycles......Page 22
1.4.1 Trees......Page 23
1.5.1 Small world properties......Page 24
1.5.3 Degree distribution......Page 25
1.6 Complexity......Page 27
1.7 What is next......Page 28
2.1 Introduction......Page 30
2.2.1 Erdos-Renyi networks......Page 31
2.2.2 Fitness networks......Page 34
2.3 Preferential attachment networks......Page 36
2.3.1 The Barabasi-Albert model......Page 38
2.3.2 Duplication-divergence models......Page 40
2.3.3 Growing weighted networks......Page 43
2.4 The small-world model......Page 45
2.5 Outlook......Page 46
3.1 Introduction......Page 48
3.2 Detailed balance condition......Page 49
3.3 Empirical measurement of correlations......Page 52
3.3.1 Two vertices correlations: ANND......Page 54
3.3.2 Three vertices correlations: Clustering......Page 58
3.4 Networks in the real world......Page 60
3.4.1 Pretty-good-privacy web of trust......Page 64
3.5 Modeling correlations......Page 67
3.5.2 The configuration model......Page 68
3.5.3 Growing models......Page 69
3.5.4 Assortativity generators......Page 70
3.5.5 Modeling clustered networks......Page 72
3.5.6 Random graphs with attributes......Page 73
3.5.7 Hidden colormodels......Page 74
3.5.8 Fitness or hidden variables models......Page 75
3.5.9 Fitness and preferential attachment models......Page 77
3.6 Outlook......Page 78
4.1 Introduction......Page 80
4.2.3 Weighted degree: Strength......Page 81
4.2.4 Weighted clustering......Page 82
4.2.5 Weighted assortativity: Affinity......Page 83
4.2.6 Local heterogeneity......Page 84
4.3 Weighted networks: Empirical results......Page 85
4.3.2 Airport network......Page 86
4.3.3 Urban and inter-urban movement networks......Page 90
4.3.4 Transportation networks: Summary......Page 91
4.3.5 Social network: Example of the scienti.c collaboration network......Page 92
4.4.1 Coupling weight and topology......Page 96
4.4.2 A simple model: Weight perturbation and “busy get busier” effects......Page 97
4.4.3 Local heterogeneities, nonlinearities and space-topology coupling......Page 101
4.4.4 Other models coupling traffic and topology......Page 103
4.5 Outlook......Page 104
Acknowledgments......Page 105
5.1 Introduction......Page 106
5.2 Definitions of communities......Page 107
5.3 Evaluating community identification......Page 109
5.4.1 Shortest path centrality......Page 110
5.5 Current-flow and random walk centrality......Page 111
5.5.1 Information centrality......Page 112
5.6.1 Hierarchical clustering......Page 113
5.6.2 L-shell method......Page 114
5.7.2 Simulated annealing methods......Page 115
5.7.3 Extremal optimisation......Page 116
5.8.1 Spectral bisection......Page 117
5.8.2 Multi dimensional spectral analysis......Page 118
5.8.4 Approximate resistance networks......Page 119
5.9.1 Clustering and curvature......Page 120
5.9.2 Random walk based methods......Page 121
5.9.3 Q-potts model......Page 123
5.10 Comparative evaluation......Page 124
5.11 Conclusion......Page 126
Acknowledgments......Page 127
6.1 Introduction......Page 128
6.2 Global methods for visualizing large graphs......Page 129
6.2.1 Spring embedder based methods......Page 130
6.2.2 Properties......Page 131
6.2.3 Spectral layout......Page 134
6.2.4 Properties......Page 135
6.3 Analytical layouts......Page 137
6.3.1 Centrality and status layouts......Page 138
6.3.2 Clustered layouts......Page 139
6.3.3 Case studies......Page 142
7.1 Introduction......Page 146
7.2 Preliminaries......Page 147
7.3 Web Base......Page 150
7.3.1 In-degree and out-degree......Page 151
7.3.2 Page Rank......Page 153
7.3.3 Bipartite cliques......Page 154
7.4 Stochastic models of the webgraph......Page 155
7.4.1 Models of the webgraph......Page 156
7.4.2 Amulti-layer model......Page 157
7.4.3 Large scale simulation......Page 159
7.5 Algorithmic techniques for generating and measuring webgraphs......Page 162
7.5.1 Data representation and multifiles......Page 164
7.5.2 Generating webgraphs......Page 165
7.5.4 Semi-external breadth first search......Page 167
7.5.6 Computation of the SCCs......Page 168
7.5.7 Computation of the bow-tie regions......Page 169
7.5.8 Disjoint bipartite cliques......Page 170
7.5.9 PageRank......Page 173
7.6 Summary and outlook......Page 174
8.1 Introduction......Page 176
8.2 Internet maps......Page 177
8.3 Heavy tailed distributions......Page 181
8.4 Sampling biases and the scale-free nature of the Internet......Page 184
8.5 Hierarchies and correlations......Page 186
Acknowledgments......Page 196
9.1 Introduction......Page 198
9.2 Graph-theoretical formalism......Page 199
9.2.1 Basic notions......Page 200
9.2.2 Connected subgraphs and minimum spanning trees......Page 201
9.3.1 Spanning trees in food webs......Page 202
9.3.2 Spanning trees in taxonomy......Page 205
9.4.1 Food webs......Page 208
9.4.2 Taxonomic trees......Page 211
9.5 Summary and outlook......Page 215
Acknowledgments......Page 216
10.1 Introduction......Page 218
10.2 Social networks: Examples and general features......Page 219
10.3 Degree distribution......Page 221
10.4 Assortativity......Page 223
10.4.1 Open questions on assortativity......Page 225
10.5 Clustering......Page 226
10.6 Community structure......Page 227
10.6.1 Open questions on community structure......Page 229
10.7 Economical networks: The case-study of the board of directors......Page 231
10.7.1 Board and directors network as bipartite graphs......Page 233
10.8.1 Average quantities......Page 235
10.8.2 Degree distributions and assortativity......Page 237
10.8.3 Lobbies......Page 239
10.9.1 Interlock structure and decision making dynamics......Page 241
10.9.2 Single board decision making model......Page 242
10.9.3 Multiple boards decision making model......Page 245
10.10 Conclusion......Page 246
References......Page 248
Index......Page 262