From Biological Nets to the Internet and WWW

SN Dorogovtsev | JFF Mendes

** TABLE OF CONTENTS
**

Preface | |||

0 Modern architecture of random graphs | |||

1 What are networks? | |||

1.1 Basic notions | |||

1.2 Adjacency matrix | |||

1.3 Degree distribution | |||

1.4 Clustering | |||

1.5 Small worlds | |||

1.6 Giant components | |||

1.7 List of basic constructions | |||

1.8 List of main characteristics | |||

2 Popularity is attractive | |||

2.1 Attachment of edges without preference | |||

2.2 Preferential linking | |||

3 Real networks | |||

3.1 Networks of citations of scientific papers | |||

3.2 Communication networks: the WWW and the Internet | |||

3.2.1 Structure of the WWW | |||

3.2.2 Search in the WWW | |||

3.2.3 Structure of the Internet | |||

3.3 Networks of collaborations | |||

3.4 Biological networks | |||

3.4.1 Neural networks | |||

3.4.2 Networks of metabolic reactions | |||

3.4.3 Genome and protein networks | |||

3.4.4 Ecological and food webs | |||

3.4.5 Word Web of human language | |||

3.5 Telephone call graph | |||

3.6 Mail networks | |||

3.7 Power grids and industrial networks | |||

3.8 Electronic circuits | |||

3.9 Nets of software components | |||

3.10 Energy landscape networks | |||

3.11 Overview | |||

4 Equilibrium networks | |||

4.1 Statistical ensembles of random networks | |||

4.2 Classical random graphs | |||

4.3 How to build an equilibrium net | |||

4.4 Econophysics: condensation of wealth | |||

4.5 Condensation of edges in equilibrium networks | |||

4.6 Correlations in equilibrium networks | |||

4.7 Small-world networks | |||

4.7.1 The Watts--Strogatz model and its variations | |||

4.7.2 The smallest-world network | |||

5 Non-equilibrium networks | |||

5.1 Growing exponential networks | |||

5.2 The Barab'asi--Albert model | |||

5.3 Linear preference | |||

5.4 How the preferential linking emerges | |||

5.5 Scaling | |||

5.6 Generic scale of `scale-free' networks | |||

5.7 More realistic models | |||

5.8 Estimations for the WWW | |||

5.9 Non-linear preference | |||

5.10 Types of preference providing scale-free networks | |||

5.11 Condensation of edges in inhomogeneous nets | |||

5.12 Correlations in growing networks | |||

5.13 How to obtain a strong clustering | |||

5.14 Deterministic graphs | |||

5.15 Accelerated growth of networks | |||

5.16 Evolution of language | |||

5.17 Partial copying and duplication | |||

5.18 Non-equilibrium non-growing networks | |||

6 Global topology of networks | |||

6.1 Topology of undirected equilibrium networks | |||

6.2 Topology of directed equilibrium networks | |||

6.3 Failures and attacks | |||

6.4 Resilience against random breakdowns | |||

6.5 How viruses spread within networks | |||

6.6 The Ising model on a net | |||

6.7 Mesoscopics in networks | |||

6.8 How to destroy a network | |||

6.9 How to stop an epidemic | |||

6.10 BKTpercolation transition in growing networks | |||

6.11 When loops and correlations are important | |||

7 Growth of networks and self-organized criticality | |||

7.1 Preferential linking and the Simon model | |||

7.2 Econophysics: wealth distribution in evolving societies | |||

7.3 Multiplicative stochastic processes | |||

8 Philosophy of a small world | |||

Appendix | |||

A Relations for an adjacency matrix | |||

B How to measure a distribution | |||

C Statistics of cliques | |||

D Power-law preference | |||

E Inhomogeneous growing net | |||

F Z-transform | |||

G Critical phenomena in networks | |||

H A guide to the network literature | |||

References | |||

Index |