New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Trafficdriven epidemic spreading in finitesize scalefree networks

Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved August 17, 2009 (received for review June 25, 2009)
Abstract
The study of complex networks sheds light on the relation between the structure and function of complex systems. One remarkable result is the absence of an epidemic threshold in infinitesize, scalefree networks, which implies that any infection will perpetually propagate regardless of the spreading rate. The vast majority of current theoretical approaches assumes that infections are transmitted as a reaction process from nodes to all neighbors. Here we adopt a different perspective and show that the epidemic incidence is shaped by trafficflow conditions. Specifically, we consider the scenario in which epidemic pathways are defined and driven by flows. Through extensive numerical simulations and theoretical predictions, it is shown that the value of the epidemic threshold in scalefree networks depends directly on flow conditions, in particular on the first and second moments of the betweenness distribution given a routing protocol. We consider the scenarios in which the delivery capability of the nodes is bounded or unbounded. In both cases, the threshold values depend on the traffic and decrease as flow increases. Bounded delivery provokes the emergence of congestion, slowing down the spreading of the disease and setting a limit for the epidemic incidence. Our results provide a general conceptual framework for the understanding of spreading processes on complex networks.
Scalefree (SF) networks (1–3) are characterized by the presence of hubs, which are responsible for several striking properties for the propagation of information, rumors, or infections (4–9). Theoretical modeling of how diseases spread in complex networks is largely based on the assumption that the propagation is driven by reaction processes, in the sense that the transmission occurs from every infected entity through all its neighbors at each time step, producing a diffusion of the epidemics on the network. However, this approach overlooks the notion that the network substrate is a fixed snapshot of all the possible connections between nodes, which does not imply that all nodes are concurrently active. Many networks observed in nature (1, 2), including those in society, biology, and technology, have nodes that temporally interact only with a subset of its neighbors (10, 11). For instance, hub proteins do not always interact with all their neighbor proteins at the same time (12), just as individuals in a social network (13) do not interact simultaneously with all of their acquaintances. Likewise, Internet connections being utilized at a given time depend on the specific traffic and routing protocols. Given that transport is one of the most common functions of networked systems, a proper consideration of this issue will irreparably affect how a given dynamical process evolves.
Our knowledge of the mechanisms involved in disease propagation has improved in the last several years (14–16). Recent works have to some extent surmounted the problem of link concurrency through agentbased modeling approaches (14) or by explicitly implementing datadriven simulation tools (17). These very detailed computer models have not been yet analyzed in a general theoretical framework. Here we introduce a theoretical approach by which to investigate the outcome of an epidemic spreading process driven by transport instead of reaction events. To this end, we analyze a paradigmatic abstraction of epidemic contagion, the socalled susceptible–infected–susceptible (SIS) model (18) (see Methods), which assumes that contagion occurs through the eventual contact or transmission between connected partners that are using their connections at the time of propagation. This analysis is achieved by considering a quantized interaction at each time step. Mathematically, we set up the model in a flow scenario where contagion is carried by interaction packets traveling across the network.
We consider two possible scenarios that encompass most of real traffic situations: (i) unbounded delivery rate, and (ii) bounded delivery rate, of packets per unit of time. We derive the equation governing the critical threshold for epidemic spreading in SF networks, which embeds, as a particular case, previous theoretical findings. For unbounded delivery rate, it is shown that the epidemic threshold decreases in finite SF networks when traffic flow increases. In the bounded case, nodes accumulate packets at their queues when traffic flow overcomes the maximal delivery rate, i.e. when congestion arises. From this moment on, the results show that both the epidemic threshold and the infection prevalence are bounded because of congestion.
Results and Discussion
We first generate two different types of SF networks. On one hand, we construct random SF networks where no correlations are present by using the configuration model (1, 2). On the other hand, we also generate smallworld, SF, and highly clustered networks − all properties found in many realworld networks (1, 2) such as the Internet – by using a class of recently developed network models (19, 20) in which nearby nodes in a hidden metric space are connected. This metric space can represent social, geographical, or any other relevant distance between the nodes of the simulated networks. Specifically, in the model we use, nodes are uniformly distributed in a onedimensional circle and assigned an expected degree k from a powerlaw distribution P(k) ∼ k^{−γ}. Pairs of nodes separated by a distance d are linked with a probability r(d;k;k′) = (1 + d/d_{c})^{−α}, where α > 1 and d_{c} ∼ kk′ (see Methods for further details). In most of our simulations, we fixed 〈k〉 = 3 and α = 2. After the networks are built up, the traffic process is implemented in the following way. At each time step, p = λN new packets are created with randomly chosen origins and destinations. The routing of information is modeled through either a shortestpath delivery strategy or a greedy algorithm (20, 21). In the latter, we make use of the second class of SF networks, and a node i forwards a packet to node j in its neighborhood, which is the closest node (in the hidden metric space) to the final packet destination.
To account for link concurrency, we consider that two nodes do not interact at all times t, but only when they exchange at least a single packet. Therefore, we assume that the epidemic can spread between nodes every time an interaction takes place. This situation is reminiscent of disease transmission on airtransportation networks; if an infected individual did not travel between two cities, then, regardless of whether or not those cities are connected by a direct flight, the epidemic will not spread from one place to the other. In this way, although a node can potentially interact with as many contacts as it has and as many times as packets it exchanges with its neighbors, the effective interactions are driven by a second dynamics (traffic). The more packets travel through a link, the more likely the disease will spread through it. On the other hand, after an interaction is at work, the epidemic spreads from infected to susceptible nodes with probability β. For example, if at time t node i is infected and a packet is traveling from node i to one of its neighbors node j, then at the next time step, node j will be infected with probability β. Therefore, susceptible and infected states are associated with the nodes, whereas the transport of packets is the mechanism responsible for the propagation of the disease at each time step.
Unbounded Delivery Rate.
In this situation, congestion can not arise in the system. Fig. 1 shows the results for the stationary density of infected nodes ρ as a function of β and the traffic generation rate λ for SF networks.
The traffic level determines the value of both the epidemic incidence and the critical thresholds. We observe the emergence of an epidemic threshold under lowtraffic conditions. This finding implies that for a fixed value of λ, the epidemic dies out if the spreading rate is below a certain critical value β_{c}(λ). Moreintense packet flows yield lower epidemic thresholds. The reason for the dependence of the critical spreading rates on λ is rooted in the effective topological paths induced by the flow of packets through the network. At low values of λ, there are only a few packets traveling throughout the system, so the epidemic simply dies out because many nodes do not participate in the interaction via packets exchanges. As λ grows, more paths appear between communicating nodes, thus spreading the infection to a larger portion of the network. Therefore, in trafficdriven epidemic processes the infection is constrained to propagate only through links that transmit a packet, and thus the number of attempts to transmit the infection depends on the flow conditions at a local level, namely, on the number of active communication channels at each time step. As a consequence, the effective network that spreads the infection is no longer equivalent to the complete underlying topology. Instead, it is a map of the dynamical process associated with packet traffic flow. The conclusion is that the diseasepropagation process has two dynamical components: one intrinsic to the disease itself (β) and the other to the underlying traffic dynamics (the flow).
To theorize about these effects, we next formulate the analytical expression for the dependence of the epidemic threshold on the amount of traffic injected into the system, following a meanfield approach akin to the conventional analysis of the reaction driven case. Mathematically, the fraction of paths traversing a node given a certain routing protocol (22), the socalled algorithmic betweenness, b_{alg}^{k}, defines the flow pathways. Let us consider the evolution of the relative density, ρ_{k}(t), of infected nodes with degree k. Following the heterogeneous meanfield approximation (4), the dynamical rate equations for the SIS model are The first term in Eq. 1 is the recovery rate of infected individuals (we set, henceforth, μ = 1). The second term takes into account the probability that a node with k links belongs to the susceptible class, [1 − ρ_{k}(t)], and gets the infection via packets traveling from infected nodes. The latter process is proportional to the spreading probability β, the probability Θ(t) that a packet travels through a link pointing to an infected node and the number of packets received by a node of degree k. This probability, in turn, is proportional to the total number of packets in the system, ∼λN, and the algorithmic betweenness of the node, b_{alg}^{k}. Note that the difference with the standard epidemic spreading model is given by these factors, as now the number of contacts per unit of time of a node is not proportional to its connectivity but to the number of packets that travel through it. Finally, Θ(t) takes the form Eq. 1 has been obtained assuming (i) that the network is uncorrelated P(k′k) = k′P(k′)/〈k〉, and (ii) that the algorithmic flow between the classes of nodes of degree k and k′ factorizes b_{alg}^{kk′} ∼ b_{alg}^{k}b_{alg}^{k′}. Although no uncorrelated networks exist, this approximation allows us to identify the governing parameters of the proposed dynamics. The second approximation is an upper bound to the actual value of the b_{alg}^{kk′}, whose mathematical expression is, in general, unknown. The validity of the theory, even with these approximations, is notable as confirmed by the numerical simulations.
By imposing stationarity [∂_{t}ρ_{k}(t) = 0], Eq. 1 yields from which a selfconsistent equation for Θ is obtained as The value Θ = 0 is always a solution. In order to have a nonzero solution, the condition must be fulfilled, from which the epidemic threshold is obtained as below which the epidemic dies out, and above which there is an endemic state. In Fig. 2, a comparison between the theoretical prediction and the numerical observations is presented. Here, we have explicitly calculated the algorithmic betweenness for the greedy routing as it only coincides with the topological betweenness for shortestpaths routing. The obtained curve separates two regions: an absorbing phase in which the epidemic disappears and an active phase where the infection is endemic.
Eq. 6 is notably simple but has profound implications: The epidemic threshold decreases with traffic and eventually vanishes in the limit of very large traffic flow in finite systems, in contrast to the expected result of a finitesizereminiscent threshold in the classical reactive–diffusive framework. Admittedly, this is a new feature with respect to previous results on epidemic spreading in SF networks. It is rooted in the increase of the effective epidemic spreading rate caused by the flow of packets. This is a genuine effect of trafficdriven epidemic processes and generalizes the hypothesis put forward in the framework of a reaction–diffusion process (15) on SF networks. It implies that an epidemic will pervade the (finite) network, whatever the spreading rate, if the load on it is high enough. Moreover, Eq. 6 reveals a new dependence. The critical threshold depends on the topological features of the graph—but at variance with the standard case—through the first two moments of the algorithmicbetweenness distribution. As noted above, the algorithmic betweenness of a node is given by the number of packets traversing that node given a routing protocol. In other words, it has two components: a topological one, which is given by the degree of the node, and a dynamical component defined by the routing protocol.
Within our formulation, the classical result (4),
can be obtained for a particular protocol and set of traffic conditions, although we note that the microscopic dynamics of our model is different from the classical SIS. To recover Eq. 7, assume a random protocol. If packets of information are represented as w random walkers traveling in a network with average degree 〈k〉, then under the assumption that the packets are not interacting, it follows that the average number of walkers at a node i in the stationary regime (the algorithmic betweenness) is given by
Our results are robust for other network models and different routing algorithms. We have also made numerical simulations of the trafficdriven epidemic process on top of Barabási–Albert and random SF networks, implementing a shortestpaths delivery scheme. In this case, packets are diverted following the shortest path (in the actual topological space) from the packets' origins to their destinations. The rest of model parameters and rules for epidemic spreading remain the same. Fig. 3 shows the results obtained for random SF networks. As can be seen, the phenomenology is the same: The epidemic threshold depends on the amount of traffic in the network such that the higher the flow, the smaller the epidemic threshold separating the absorbing and active phases. On the other hand, for processes in which the delivery of packets follows a shortest path algorithm, Eq. 6 looks like where b_{top} is the topological betweenness.
Bounded Delivery Rate.
Eq. 8 allows us to also investigate the equivalent scenario in the presence of congestion. Let us consider the same traffic process above but with nodes having queues that can not only store as many packets as needed but also deliver, on average, only a finite number of them at each time step. It is known that there is a critical value of λ above which the system starts to congest (22), Eq. 9 gives the traffic threshold that defines the onset of congestion, which is governed by the node with maximum algorithmic betweenness b_{alg}^{*}. Substituting Eq. 9 in Eq. 6 we obtain a critical threshold for an epidemic spreading process bounded by congestion. Increasing the traffic above λ_{c} will gradually congest all the nodes in the network up to a limit in which the traffic is stationary and the lengths of queues grow without limit.
To illustrate this point, let us assume that the capacities for processing and delivering information are heterogeneously distributed (25–27) so that the larger the number of paths traversing a node, the larger its capability to deliver the packets. Specifically, each node i of the network delivers at each time step a maximum of ⌈c_{i} = 1 + k_{i}^{η}⌉ packets, where η is a parameter of the model. In this case, the critical value of λ in Eq. 9 is multiplied by the maximum delivery capacity (25). Moreover, without loss of generality, we will explore the behavior of the model in random SF networks where the routing is implemented by shortest paths b_{alg} = b_{top} ∼ k^{ν}, ν being usually between 1.1 and 1.3 (28). The previous assumption for the delivery capability thus allows us to explore, as a function of η, the situations in which the delivery rate is smaller or larger than the arrival rate (defined by the algorithmic betweenness). Phenomenologically, these two scenarios correspond to the cases in which the traffic is in a freeflow regime (if η > ν) or when the network will congest (if η < ν). We also note that the adopted approach is equivalent to assume a finite length for the queues at the nodes.
Fig. 4 shows the results for the stationary average density of infected nodes, ρ, as a function of the spreading rate β and the rate at which packets are generated λ for two different values of η by using a shortestpath delivery scheme on top of random SF networks. For η = 0.8, the epidemic incidence is significantly small for all values of the parameters λ and β as compared with the results obtained when the rate of packets delivery is unbounded. On the contrary, when η = 1.7 the phase diagram is qualitatively the same as for the unbounded case, including the result that the epidemic incidence vanishes when λ is large enough. A closer look at the dynamical evolution unveils an interesting, previously unreported, feature—when the rate at which packets are delivered is smaller than the rate at which they arrive, the average value of infected nodes saturates beyond a certain value of the trafficflow rate λ. This effect is due to the emergence of traffic congestion. When the flow of packets into the system is such that nodes are not able to deliver at least as many packets as they receive, their queues start growing and packets pile up. This observation in turn implies that the spreading of the disease becomes less efficient; in other words, the spreading process slows down. The consequence is that regardless of whether more packets are injected into the system, the average level of packets able to move from nodes to nodes throughout the network is roughly constant and so is the average level of infected individuals.
Fig. 5 illustrates the phenomenological picture described above. It shows the epidemic incidence ρ for a fixed value of β = 0.15 as a function of λ for different values of η. The figure clearly evidences that congestion is the ultimate reason for the behavior described above. Therefore, the conclusion is that in systems where a traffic process with finite delivery capacity is coupled to the spreading of the disease, the epidemic incidence is bounded. This is good news, as most of the spreading processes in realworld networks involves different trafficflow conditions. Further evidence of this phenomenology is given in Fig. 6, where we have depicted the epidemic threshold as a function of λ for two different values of η, less than and greater than ν. When η < ν, congestion arises, and the contrary holds for η > ν where the diagram is equivalent to that of unbounded traffic. The onset of congestion determines the value of β above which congestion starts. It is clearly visualized as the point beyond which the powerlaw dependence in Eq. 6 breaks down. The plateau of β_{c} corresponds to the stationary situation of global congestion.
Conclusions
In our study, we have computed both analytically and numerically the conditions for the emergence of an epidemic outbreak in SF networks when disease contagion is driven by traffic or interaction flow. We demonstrate that epidemic thresholds are determined by contact flows and that the epidemic incidence is strongly correlated to the emergence of epidemic propagation pathways that are defined and driven by traffic flow. Two general phenomenological scenarios are identified. When the rate at which packets are delivered is large enough or is not bounded, the epidemic threshold is inversely proportional to the traffic flow in the system. This simple law, which also encompasses a dependency with the topological properties of the graph as given by the algorithmic betweenness, has remarkable consequences. One of them is that the epidemic threshold vanishes in the limit of hightraffic conditions, even for finite SF networks and for any routing algorithm. Moreover, within this scenario, the new approach recovers previous results as a particular case of reaction–diffusion spreading. New phenomenological properties appear in the unified framework when the system has a finite capability to deliver packets and congestion is possible. In this case, what determines the epidemic incidence is the capability of the network to avoid congestion. If congestion arises, the number of contacts between the system elements decreases, leading to a lessefficient spreading of the disease and therefore to a significant reduction of the average number of infected individuals. Additionally, the value of the epidemic threshold depends on the delivery rate—the smaller the delivery rate, the larger the epidemic threshold. Interestingly, our study points out that congestion appears to have a positive effect in reducing the critical spreading rate required for an epidemic outbreak to occur as well as its size.
Finally, we point out that the new approach presented here constitutes an interesting framework with which to address related problems. For instance, in the context of airtransportation networks (17, 29), trafficdriven mechanisms of disease propagation could explain the observed differences in the impact of a disease during the course of a year (30). One might even expect that, due to seasonal fluctuations in flows, the same disease could not provoke a systemwide outbreak if the flow were not high enough during the initial states of the disease contagion. The same reasoning implies that airtraffic flow restriction is an efficient way to contain a spreading pandemic. Incorporating the trafficdriven character of the spreading process into current models has profound consequences for the way the system functions. Also, the theory could help in designing new immunization algorithms or robust protocols, including the quarantining of highly sensitive traffic nodes or equivalently controlling the onset of congestion in networks (control of airtraffic flow). Obviously, our approximation lacks the level of detail required to assess more realistic epidemiological models, but it provides a simple framework for anticipating most of the general features to be observed in detailed computational agentbased models.
Methods
Structure.
SF networks are generated by assigning all nodes a random polar angle θ distributed uniformly in the interval [0,2π). The expected degrees of the nodes are then drawn from some distribution x(k), and the network is completed by connecting two nodes with hidden coordinates (θ,k) and (θ′,k′) with probability
Routing Dynamics.
At each time step, p = λN new packets are created with randomly chosen origins and destinations. For the sake of simplicity, packets are considered noninteracting so that no queues are used. The greedy routing delivers packets such that node i, holding a packet whose destination is l, dispatches it through node j, which is the closest to l in the hidden metric space. Alternatively, one can implement a shortestpath algorithm in which packets are delivered through nodes that are closer to their destinations in the network (i.e., not in the hidden metric space). Our results are insensitive to the two routing protocols implemented.
Epidemic Dynamics.
We have implemented the SIS model, in which each node can be in two possible states: healthy (S) or infected (I). Starting from an initial fraction of infected individuals ρ_{0} = I_{0}/N, the infection spreads in the system through packet exchanges. A susceptible node has a probability β of becoming infected every time it receives a packet from an infected neighbor. We also assume that infected nodes are recovered at a rate μ, which we fix to 1 for most of the simulations. After a transient time, we compute the average density of infected individuals, ρ, which is the prevalence of disease in the system.
Acknowledgments
S. M. thanks M. Meloni for useful discussions. Y. M. was supported by the Ministerio de Ciencia e Innovacin of Spain through the Ramn y Cajal Program. This work has been partially supported by Ministerio de Ciencia e Innovacin Grants FIS200612781C0201, and FIS200801240. A.A. acknowledges support from the Director, Office of Science, Computational and Technology Research, U.S. Department of Energy Contract No. DEAC0205CH11231.
Footnotes
 ^{1}To whom correspondence should be addressed. Email: yamir{at}unizar.es

Author contributions: S.M., A.A., and Y.M. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.
References
 ↵
 ↵
 ↵
 Barabási AL,
 Albert R
 ↵
 ↵
 LLoyd AL,
 May RM
 ↵
 ↵
 ↵
 ↵
 Gardeñes JG,
 Latora V,
 Moreno Y,
 Profumo E
 ↵
 Amaral LAN,
 Scala A,
 Barthélemy M,
 Stanley HE
 ↵
 ↵
 ↵
 ↵
 Eubank S,
 et al.
 ↵
 ↵
 ↵
 ↵
 Murray JD
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 PastorSatorras R,
 Vespignani A
 ↵
 Guimerà R,
 Mossa S,
 Turtschi A,
 Amaral LAN
 ↵
Citation Manager Formats
More Articles of This Classification
Physical Sciences
Related Content
 No related articles found.
Cited by...
 Local structure can identify and quantify influential global spreaders in large scale social networks
 Networks of conforming or nonconforming individuals tend to reach satisfactory decisions
 Percolation transition in dynamical traffic network with evolving critical bottlenecks
 The price of anarchy in mobilitydriven contagion dynamics
 Evolution of the most common English words and phrases over the centuries
 Culturomics meets random fractal theory: insights into longrange correlations of social and natural phenomena over the past two centuries