Project topics and materials
Get Complete Project Material File(s) Now! »
Random networks: Erdos¬-R«enyi (ER) model
The main contribution to the study of random graphs are due to Paul Erdos¬ and Alfr«ed R«enyi (58; 59; 60). In their Þrst work they deÞned a random graph of N vertices and m links selected 10 N(N−1)/2 m Theoretical Framework: Networks and Graphs p=0.05 p=0.2 p=0.5 Figure 2.1: Schematic illustration of ER model with different connectivity probability. The larger is p, the denser is the network. When p = 0 the graph is composed by isolated nodes and when p = 1 the graph is fully connected. at random among the N(N − 1)/2 pairs of nodes. There are in total possible graphs. They can appear with the same probability and they form the ensemble of graphs characterized by this rule. Another deÞnition of random graph is given by the binomial model that is equivalent to the ER model for large N. Starting from N vertices for each pair of nodes a link is formed with probability p as illustrated in Þgure 2.1. The number of links is then a random variable with average value m = pN(N − 1)/2. In a random graph characterized by a probability of connection p, in the limit of N → ∞, the degree distribution can be approximated by a Poisson distribution: P rand (k) e k k k (2.6) k! The most characteristic trait of the degree distribution of random graphs is that it decays ex-ponentially for large values of k allowing only very small degree ßuctuations. The degree of the different nodes can thus be considered as uniform and equal to the average degree k k pN. In general, random graphs are characterized by very small diameters showing a small-world be-havior that is observed in many real world networks. It is easy to show that the diameter D is proportional to ln(n)/ln( k ) (61). Moreover, random graphs are characterized by very small clustering coefficients. Given a node i, the probability that two of its neighbors are connected is equal to the probability that any other two nodes will be connected, so that: k Crand = p = N . (2.7)
This implies that the ratio Crand/ k at Þxed k decrease with the size of the system like N−1. 11 ln(n) ln(k) Theoretical Framework: Networks and Graphs A B 1 Regular Small-world Random 0.8 C(p) / C(0) p = 0 Increasing randomness p = 1 0 0.001 0.01 0.1 1 0.0001 p. Figure 2.2: (A) The Watts-Strogatz model interpolates between a regular ring lattice and a random network with the random rewiring procedure. (B) Average shortest path length L and average clustering coefficient as a function of p. The quantities have been normalized by their value for the regular lattice topology. The rapid drop of L triggers the onset of small-world effects and it occurs when the clustering coefficient is still high.
Small world networks: Watts-Strogatz (WS) model
It has been observed that many real networks exhibit many closed triads leading to large cluster-ing coefficients (like some regular graphs but in contrast with random graphs), but also very short paths (like random networks but in contrast with regular graphs). From this simple observation we can conclude that real networks are neither regular lattice nor random graphs, and following this inspiration, in 1998, Watts and Strogatz put forward a model to interpolate between these two limits (7). The model states that starting from N nodes in a ring, each connected to k/2 to the left and k/2 nodes to the right, every link is randomly rewired with a probability p as shown in Figure 2.2A. With this process pN k/2 links will be reshuffled on average. Nodes that before were far away from each other by construction are now closer thanks to the presence of shortcuts. It is extremely interesting to study the behavior of the average path length L of the graph and of the clustering coefficient C as a function of p. For p = 0 we have a complete regular ring with L(0) 2nk and C(0) 34 while for p = 1 the network becomes completely random with L(1) and C(1) nk . For intermediate values of p we will have a situation in between these two limits. As shown in Figure 2.2B as p increases the distance gets reduced a lot while the average clustering is almost constant. The two quantities change with a complete different slope with p and there is thus a broad region in which we see a small-world effect and a value of clustering bigger than the random case. It has been shown in Ref. (62) that the shape of the degree distribution for p > 0 is similar to the distribution of a random graph with a well deÞned peak around the mean value and an exponential decay for large value of k. This model is able to create small-world networks highly clustered but it still has a homogeneous topology and the degree distribution is far from being heavy-tailed as observed in real networks.
Scale free networks: Barab«asi-Albert (BA) model
In the last ten years many models have been proposed to explain the abundance in many natural systems of networks with high heterogeneity in the degree distribution. In the following we will recall the Þrst, a very elegant, simple and most cited model, proposed in 1999 by Barab«asi and Albert able to produce scale-free graphs with small-world phenomena (8; 63). In contrast with the previous models where the number of nodes N were Þxed a priori and the edges were drawn (or rewired) with a certain probability, the BA model suggests a reasonable mechanism of networks formation. Here the nodes are progressively added to the system con-necting with new edges the most popular links. Starting from a small number of core nodes n0 the graph is thus build following these rules:
1. growth: at each time step a new vertex is added to the graph and it is linked with m < n0 other nodes already present
2. preferential attachment: the new node is connected to the node i with probability π de-pending on the degree ki ki π(ki) = j kj . (2.8).
Dynamical networks
As brießy enumerated in the previous section, many real systems can be treated as networks by coupling the constituent elements, namely the vertices, through some functional connections, namely the links. Nevertheless, in some cases, edges are active only for a certain period of time: e.g., a sexual contact between two individuals occurring at given time holds for a limited period (68). Similarly, a social interactions of people attending a conference can be represented by a graph where an edge between two individuals is on throughout the time they are chatting or at least in a close proximity (69). Like network topology, the temporal structure of edge activa-tions can affect dynamics of systems interacting through the network, from disease contagion to information diffusion. The emergent Þeld of temporal networks is exponentially growing and it is still lacking a uniÞed theoretical framework to analyze the temporal datasets. In the light of traditional network theory, one can see this framework as moving the information of when things happen from the dynamic system on the network, to the network itself. Since fundamental prop-erties, such as the transitivity of edges, do not necessarily hold in temporal networks, many of these methods need to be quite different from those for static networks (70).
Table of contents :
1 Introduction
2 Theoretical Framework: Networks and Graphs
2.1 Basic definitions
2.2 Real networks
2.2.1 Social networks
2.2.2 Technological networks
2.2.3 Biological networks
2.3 Network models
2.3.1 Random networks: Erd¨os-R´enyi (ER) model
2.3.2 Small world networks: Watts-Strogatz (WS) model
2.3.3 Scale free networks: Barab´asi-Albert (BA) model
2.4 Dynamical networks
2.5 Conclusions
3 Theoretical Framework: Epidemic Models
3.1 Compartmental models
3.2 Epidemic spreading on graphs
3.3 Metapopulation models
3.4 Conclusion
4 GLobal Epidemic and Mobility model
4.1 Global Population and subpopulations definition
4.2 World Airport Network
4.3 Commuting Networks
4.4 Epidemic model
4.5 Stochastic and discrete integration of the disease dynamics
4.6 The integration of the transport operator
4.7 Time-scale separation and the integration of the commuting flows
4.8 Effective force of infection
5 Global spread of H1N1 pandemic influenza
5.1 Background
5.2 Disease parameters estimation
5.3 Real time predictions
5.4 Estimating the early number of cases in Mexico
5.5 Intervention strategies
5.5.1 Vaccination campaign
5.5.2 Modeling the critical care demand
5.5.3 Travel restrictions
5.6 Assessment of model predictions and discussion
6 Dynamical network analysis and spreading simulations
6.1 Background
6.2 Data description
6.3 Daily and aggregated networks
6.4 Network microscopic dynamics
6.4.1 Activity timescales
6.4.2 Fluctuations of nodes and links properties
6.4.3 Evolution of the network backbone
6.4.4 Dynamical motifs
6.5 Spreading processes on dynamical networks
6.5.1 Percolation analysis
6.5.2 Epidemic spreading simulations
6.5.3 Invasion paths and seeds’ cluster detection
6.5.4 Longitudinal stability of the seeds’ clusters
6.5.5 Disease sentinels
6.5.6 Generalization to the stochastic case
6.6 Conclusions
7 Conclusions and perspectives
References
