Technological networks are human-built networks designed to accomplish the distribution of some resource: water, electricity, gas etc.. Classical examples are: the networks of power grids both high or low voltage (7; 13), the networks of inter-urban streets (14), internet (27; 54; 55) and the airport networks (15; 16). This last system can be represented as a weighted graph where nodes are the airports, links the air connections and weights the ßow of passengers. For more details we refer the reader to the Chapter 4 were a complete description of such network is presented. Another important technological network often classiÞed as an information network is the WolrdWideWeb. It is the most famous virtual network where nodes are web pages and links are the hyper-links (direct links) between them. The extremely rapid and unregulated growth of the Web has led to a huge complex network. Its structure is very diﬃcult to study and for many years experiments have been done in order to get information about it (28; 56).
Biological networks completely pervade the biological world spanning from the microscopic realm of biological chemistry, genetics, proteomics to the large scale of food webs. An important example is the protein interaction network (PIN) of various organisms where nodes represent proteins and edges connect pairs of interacting proteins (1; 2). Three diﬀerent scales of processes are usually considered. The microscopic scale such as PIN networks in which the main point is to understand the biological signiÞcance of the topology of these networks (3). At a larger scale biological networks can describe interactions between animals and even humans (57). At the very large scale we Þnd the networks describing the food webs of entire ecosystems (4).
The study of networked systems can be tackled with two complementary approaches. The char-acterization of real datasets and the analysis of diﬀerent case studies has to be integrated with the development of models aimed at investigating the aggregation mechanism behind the ob-served patterns. In this perspective, many models have been formulated to explain and recover the main characteristics of the observed empirical networks. In this section we will recall just three of them, that for historical reasons and for the importance of their results are probably the most cited works in the Þeld of complex networks.
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 selected10 N(N−1)/2 m Theoretical Framework: Networks and Graphs p=0.05 p=0.2 p=0.5 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 diﬀerent 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 coeﬃcients. 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 .
Small world networks: Watts-Strogatz (WS) model
It has been observed that many real networks exhibit many closed triads leading to large cluster-ing coeﬃcients (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 reshuﬄed 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 coeﬃcient 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 diﬀerent slope with p and there is thus a broad region in which we see a small-world eﬀect 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).
Epidemic spreading on graphs
In the previous section we have presented the simple compartmental epidemic models to inves-tigate an infectious disease spreading in a homogeneous population disregarding every possible substructure (gender, age, risk groups, etc…). As already mention, the parameter β governs in an eﬀective way the transmission rate of the disease between infectious and susceptible individuals. In particular, the approximation adopted so far where the β value has been rescaled in order to disregard the usually unknown average number of contacts k through which the disease can be transmitted, is equivalent to consider the spreading on a random graph. Nevertheless, many real social and technological networks of epidemiological relevance (mobility networks, the web of sexual contacts, internet, etc…) are far for being homogeneous and the hypothesis that each individual in the system has the same number of connections k k might not be a good approximation.
In this section, by describing the epidemic spreading on a networked system, we show that the ßuctuations play a main role in determining the epidemic properties and the spreading may be favored in heterogeneous networks (27; 71; 77; 78). Let us consider an uncorrelated graph com-pletely deÞned by the degree distribution P (k), and let us divide the nodes according to their health status. The disease can be transmitted from one node to the other only if the nodes are connected through an edge. In order to take into account the heterogeneity induced by the presence of nodes with diﬀerent connectivity, here we will use a degree block approximation (77; 79; 80): all nodes with the same degree are statistically equivalent. Thus our results will not apply to structured networks in which a distance or a time ordering can be deÞned; for instance, when the small-world property is not present (79; 81). Here, we have to relax the homogeneous mixing hypothesis made in the previous section and leading to equation 3.4 and work instead with the relative density of infected and susceptible vertices with given degree k:
ik = Ik , sk = Sk .
Table of contents :
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
3 Theoretical Framework: Epidemic Models
3.1 Compartmental models
3.2 Epidemic spreading on graphs
3.3 Metapopulation models
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.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.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
7 Conclusions and perspectives