Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A **network** is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of **network structure**: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists…

*Contents*

1 Introduction

1.1 Network science

1.2 Form follows function (and vice versa)

1.3 Complexity and the other buzz words

1.4 Graph theoretical preliminaries

1.5 Types of networks

1.5.1 **Social networks** of individuals

1.5.2 Other social networks

1.5.3 **Economical networks**

1.5.4 Infrastructural networks

1.5.5 Biochemical networks

1.5.6 Other network of biology

1.5.7 Ecological networks

1.5.8 Technological networks

1.5.9 Information networks

1.5.10 Other network

2 Measuring network structure

2.1 Vertex and edge quantities

2.1.1 Degree

2.1.2 Closeness centrality

2.1.3 Betweenness centrality

2.1.4 Eigenvector and information centralities

2.1.5 Local clustering coefﬁcient

2.2 Vertex-pair relations, hierarchies and clustering schemes

2.2.1 Connection strength weights

2.2.2 Structural equivalence

2.2.3 Regular equivalence

2.2.4 Hierarchical clustering schemes

2.2.5 Girvan and Newman’s algorithm

Summary of paper I

2.3 Graph quantities

2.3.1 Average geodesic length

2.3.2 Density of short circuits

2.3.3 Degree-degree correlations

Summary of paper II

Summary of paper III

Summary of paper IV

2.4 Conditional uniform graph tests

3 Network models

3.1 Random graphs

3.2 Analytical tools for network models

3.2.1 Generating functions

3.2.2 Master equations

3.3 Static models

3.3.1 The conﬁguration model

3.3.2 Exponential random graphs

3.3.3 Hidden variable models

3.3.4 Small-world network models

3.4 Dynamic models

3.4.1 The de Solla Price and Barabási-Albert models

Summary of paper V

Summary of paper VI

3.4.2 The FKP model

3.4.3 Vertex copying models

3.5 Models of structure-changing events

3.5.1 Percolation, random failures and network attacks

Summary of paper VII

Summary of paper VIII

3.5.2 Overload breakdown cascades

Summary of paper IX

Summary of paper X

4 Dynamical systems on networks

4.1 Epidemiological models

4.2 Spin models of statistical mechanics

Summary of paper XI

Summary of paper XII

4.3 Trafﬁc ﬂow

Summary of paper XIII

4.4 Search processes

4.5 Spatial games

Summary of paper XIV

Summary of paper XV

Author: Holme, Petter

Source: Umea University

Download URL 2: Visit Now