复旦大学：《网络科学导论 Introduction to Network Science》教学参考文献_Heterogeneous virus spreading-pastor2001

PHYSICAL REVIEW E, VOLUME 63, 066117 Epidemic dynamics and endemic states in complex networks Romualdo Pastor-Satorras'and Alessandro Vespignan departmento ighe Abdus Salam International Centre for Theoretical Physics(ICTP), P.O. Box 586, 34100 Trieste, Italy de Fisica i Enginyeria Nuclear, Universitat Politecnica de Catalunya, Campus Nord, Modul B4, 08034 Barcelona, spain 001; published 22 May 2001) We study by analytical methods and large scale simulations a dynamical model for the spreading of epi- demics in complex networks. In networks with exponentially bounded connectivity we recover the usual epidemic behavior with a threshold defining a critical point below that the infection prevalence is null. On the associated critical behavior. This implies that scale-free networks are prone to the spreading and the persistence of infections whatever spreading rate the epidemic agents might possess. These results can help understanding computer virus epidemics and other spreading phenomena on communication and social networks DOl: 10.1 103/PhysRevE63. 066117 PACS number(s):89.75.-k,87.23Ge,64.60.Ht,05.70.Ln . INTRODUCTION equilibrium phase transitions that usually characterize these ype of phenomena [16]. It is easy to foresee that the char- Many social, biological, and communication systems can acterization and understanding of epidemic dynamics on be properly described by complex networks whose nodes these networks can find immediate applications to a large epresent individuals or organizations and links mimic the number of problems, ranging from computer virus infections interactions among them [1, 2]. Recently, many authors have [17], epidemiology [18], and the spreading of polluting recognized the importance of local clustering in complex agents [19 networks. This implies that some special nodes of the net In this paper, we shall study the susceptible-infectec work posses a larger probability to develop connections susceptible(SIS) model [18] on complex networks. We pointing to other nodes. Particularly interesting examples of study analytically the prevalence and persistence of infected this kind of behavior are found in metabolic networks [3], individuals in exponential and SF networks by using a food webs [41, and, most importantly, in the Internet and the single-site approximation that takes into account the inhomo- world-wide-web, where the networking properties have been geneity due to the connectivity distribution. We find that extensively studied because of their technological and eco- exponential networks show, as expected, an epidemic thresh nomical relevance [2, 5-7] old (critical point) separating an infected from a healthy Complex networks can be classified in two main groups, phase. The density of infected nodes decreases to zero at the depending on their connectivity properties. The first and threshold with the linear behavior typical of a mean-field most studied one is represented by the exponential networks, (MF)critical point [16]. The SF networks, on the other hand in which the nodes'connectivity distribution(the probability show a very different and surprising behavior. For 0<y P(k)that a node is connected to other k nodes)is exponen- <1 the model does not show an epidemic threshold and the tially bounded [8-10]. A typical example of an exponential infection can always pervade the whole system. In the region network is the random graph model of Erdos and Renyi [9]. 1<ys2, the model shows an epidemic threshold that is ap- A network belonging to this class that has recently attracted proached, however, with a vanishing slope; i.e., in the ab- a great deal of attention is the Watts and Strogatz model sence of critical fluctuations. Only for y>2 we recover (WS)[10-12], which has become the prototypical example again the usual critical behavior at the threshold. In these of a small-world network [13]. A second and very different systems, because of the nonlocal connectivity, single site ap- class of graph is identified by the scale-free(SF)networks proximation predictions are expected to correctly depict the that exhibit a power-law connectivity distribution [14, model's behavior. In order to test our predictions, we per P(k)~k-2-y (1 form large scale numerical simulations on both exponential and SF networks. Numerical results are in perfect agreement with the analytical predictions and confirm the overall pic where the parameter y must be larger than zero to ensure a ture for the SIS model on complex networks given by the finite average connectivity (k). This kind of distribution im- theoretical analysis. The striking absence of an epidemic lies that each node has a statistically significant probability threshold on SF networks, a characteristic element in math- of having a very large number of connections compared to ematical epidemiology, radically changes many of the con- the average connectivity of the network( k). In particular, we clusions drawn in classic epidemic modeling. The present will focus here on the Barabasi and Albert model(BA)[14], results could be relevant also in the field of absorbing-phase hich results in a connectivity distribution P(k)-k transitions and catalytic reactions in which the spatial inter- In view of the wide occurrence of complex networks in action of the reactants can be modeled by a comple ature, it becomes a very interesting issue to inspect the ef- [16] fect of their complex features on the dynamics of epider and disease spreading [15], and more in general on the e The paper is organized as follows. In Sec. I we introduce he SIs model in a general context. Section Ill is devoted to 1063-651X/2001/63(606617(8)/$20.00 63066117-1 C2001 The American Physical Society

Epidemic dynamics and endemic states in complex networks Romualdo Pastor-Satorras1 and Alessandro Vespignani2 1 Departmento de Fı´sica i Enginyeria Nuclear, Universitat Polite`cnica de Catalunya, Campus Nord, Mo`dul B4, 08034 Barcelona, Spain 2 The Abdus Salam International Centre for Theoretical Physics (ICTP), P.O. Box 586, 34100 Trieste, Italy ~Received 1 February 2001; published 22 May 2001! We study by analytical methods and large scale simulations a dynamical model for the spreading of epi￾demics in complex networks. In networks with exponentially bounded connectivity we recover the usual epidemic behavior with a threshold defining a critical point below that the infection prevalence is null. On the contrary, on a wide range of scale-free networks we observe the absence of an epidemic threshold and its associated critical behavior. This implies that scale-free networks are prone to the spreading and the persistence of infections whatever spreading rate the epidemic agents might possess. These results can help understanding computer virus epidemics and other spreading phenomena on communication and social networks. DOI: 10.1103/PhysRevE.63.066117 PACS number~s!: 89.75.2k, 87.23.Ge, 64.60.Ht, 05.70.Ln I. INTRODUCTION Many social, biological, and communication systems can be properly described by complex networks whose nodes represent individuals or organizations and links mimic the interactions among them @1,2#. Recently, many authors have recognized the importance of local clustering in complex networks. This implies that some special nodes of the net￾work posses a larger probability to develop connections pointing to other nodes. Particularly interesting examples of this kind of behavior are found in metabolic networks @3#, food webs @4#, and, most importantly, in the Internet and the world-wide-web, where the networking properties have been extensively studied because of their technological and eco￾nomical relevance @2,5–7#. Complex networks can be classified in two main groups, depending on their connectivity properties. The first and most studied one is represented by the exponential networks, in which the nodes’ connectivity distribution ~the probability P(k) that a node is connected to other k nodes! is exponen￾tially bounded @8–10#. A typical example of an exponential network is the random graph model of Erdo¨s and Re´nyi @9#. A network belonging to this class that has recently attracted a great deal of attention is the Watts and Strogatz model ~WS! @10–12#, which has become the prototypical example of a small-world network @13#. A second and very different class of graph is identified by the scale-free ~SF! networks that exhibit a power-law connectivity distribution @14#, P~k!;k222g , ~1! where the parameter g must be larger than zero to ensure a finite average connectivity ^k&. This kind of distribution im￾plies that each node has a statistically significant probability of having a very large number of connections compared to the average connectivity of the network ^k&. In particular, we will focus here on the Baraba´si and Albert model ~BA! @14#, which results in a connectivity distribution P(k);k23. In view of the wide occurrence of complex networks in nature, it becomes a very interesting issue to inspect the ef￾fect of their complex features on the dynamics of epidemic and disease spreading @15#, and more in general on the non￾equilibrium phase transitions that usually characterize these type of phenomena @16#. It is easy to foresee that the char￾acterization and understanding of epidemic dynamics on these networks can find immediate applications to a large number of problems, ranging from computer virus infections @17#, epidemiology @18#, and the spreading of polluting agents @19#. In this paper, we shall study the susceptible-infected￾susceptible ~SIS! model @18# on complex networks. We study analytically the prevalence and persistence of infected individuals in exponential and SF networks by using a single-site approximation that takes into account the inhomo￾geneity due to the connectivity distribution. We find that exponential networks show, as expected, an epidemic thresh￾old ~critical point! separating an infected from a healthy phase. The density of infected nodes decreases to zero at the threshold with the linear behavior typical of a mean-field ~MF! critical point @16#. The SF networks, on the other hand, show a very different and surprising behavior. For 0,g <1 the model does not show an epidemic threshold and the infection can always pervade the whole system. In the region 1,g<2, the model shows an epidemic threshold that is ap￾proached, however, with a vanishing slope; i.e., in the ab￾sence of critical fluctuations. Only for g.2 we recover again the usual critical behavior at the threshold. In these systems, because of the nonlocal connectivity, single site ap￾proximation predictions are expected to correctly depict the model’s behavior. In order to test our predictions, we per￾form large scale numerical simulations on both exponential and SF networks. Numerical results are in perfect agreement with the analytical predictions and confirm the overall pic￾ture for the SIS model on complex networks given by the theoretical analysis. The striking absence of an epidemic threshold on SF networks, a characteristic element in math￾ematical epidemiology, radically changes many of the con￾clusions drawn in classic epidemic modeling. The present results could be relevant also in the field of absorbing-phase transitions and catalytic reactions in which the spatial inter￾action of the reactants can be modeled by a complex network @16#. The paper is organized as follows. In Sec. II we introduce the SIS model in a general context. Section III is devoted to PHYSICAL REVIEW E, VOLUME 63, 066117 1063-651X/2001/63~6!/066117~8!/$20.00 ©2001 The American Physical Society 63 066117-1

ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 the analysis of exponentially bounded networks, exemplified In order to obtain an analytical understanding of the SIs by the wS model In Sec. IV we analyze the scale-free Ba model behavior on complex networks, we can apply a single model, with connectivity P(k) 3. Section V extends the site dynamical MF approach, that we expect to recover ex- analytical approach applied to the Ba model to generalized actly the model's behavior due to the nonlocal connectivity SF networks, with connectivity distribution P(k),, of these graphs. Let us consider separately the case of the y>0. Finally, in Sec. VI we draw our conclusions and per- exponentially bounded and SF network spectives IlL. EXPONENTIAL NETWORKS: THE IL. THE SIS MODEL WATTS-STROGATZ MO To address the effect of the topology of complex The class of exponential networks refers to random graph works in epidemic spreading we shall study the standard models that produce a connectivity distribution P(k) peaked epidemiological model [18]. Each node of the network rep- at an average value(k) and decaying exponentially fast for resents an individual and each link is a connection along that the random graph model [9] and the small-world model of the infection can spread to other individuals. The SIS model wS [10]. The latter has recently been the object of several relies on a coarse grained description of the individuals in studies as a good candidate for the modeling of many real he population. Within this description, individuals can only istic situations in the context of social and natural networks exist in two discrete states, namely, susceptible, or healthy, and infected. These states completely neglect the In particular, the WS model shows the"small-world prop details of the infection mechanism within each individual erty common in random graphs [13]; i.e., the diameter of the The disease transmission is also described in an effective graph-the shortest chain of links connecting any two way. At each time step, each susceptible node is infected vertices--Increases very slowly, in general logarithmical with probability v if it is connected to one or more infected with the network size [12]. On the other hand, the wS model odes. at the same time. infected nodes are cured and be. has also a local structure (clustering property) that is not come again susceptible with probability 8, defining an effec- found in random graphs with finite connectivity [10, 12].The wS graph is defined as follows [10, 12]: The starting point is set 8=1) Individuals run stochastically through the cycle a ring with N nodes, in which each node is symmetrically susceptible-infected- susceptible, hence the name of the connected with its 2K nearest neighbors. Then, for every model. The updating can be performed with both parallel or node each link connected to a clockwise neighbor is rewired sequential dynamics [16]. The SIS model does not take into to a randomly chosen node with probability p, and preserved account the possibility of individuals removal due to death or with probability 1-p. This procedure generates a random raph with a connectivity distributed exponentially for large acquired immunization [18]. It is mainly used as a paradig- k[io, 121, and an average connectivity(k)=2K. The graphs matic model for the study of infectious disease that leads to have small-world properties and a nontrivial"clustering co- an endemic state with a stationary and constant value for the efficient", i.e., neighboring nodes share many common prevalence of infected individuals, i.e., the degree to which the infection is widespread in the population neighbors [10, 12]. The richness of this model has stimulated The topology of the network that specifies the interactions an intense activity aimed at understanding the network's among individuals is of primary importance in determining 13.20. 211. At the same time, the behavior of physical models most significant result is the general prediction of a nonzero on ws graphs has been investigated, including epidemio- epidemic threshold Ac [18]. If the value of A is above the logical percolation models [15, 20, 22] and models with ep threshold n>Ac the infection spreads and becomes persistent in time. Below it A<Ac, the infection dies out exponentially Here we focus on the WS model with p=l; it is worth noticing that even in this extreme case the network retains laxation to the heal thy state or the stationary endemic state node has at least K neighbors. Since the fluctuations in the In the latter case. if we start from a localized seed we can connectivity are very small in the ws graph, due to its ex- study the epidemic outbreak preceding the endemic stabili- ponential distribution, we can approach the analytical study of the Sis model by considering a single MF reaction equa- zation. From this general picture, it is natural to consider the tion for the density of infected nodes p(t) epidemic threshold as completely equivalent to a critical point in a nonequilibrium phase transition [16]. In this case, a, P(0=-p(0+x(k)P(o[1-p(01+(higher-order terms) the critical point separates an active phase with a stationary density of infected nodes(an endemic state) from an absorb- ing phase with only healthy nodes and null activity. In par- The MF character of this equation stems from the fact that ticular, it is easy to recognize that the SIS model is a gener- we have neglected the density correlations among the differ alization of the contact process model, that has been ent nodes, independently of their respective connectivities In extensively studied in the context of absorbing-state phase Eq (2)we have ignored all higher order corrections in p(t) ansitions [16 since we are interested in the onset of the infection close to 66117-2

the analysis of exponentially bounded networks, exemplified by the WS model. In Sec. IV we analyze the scale-free BA model, with connectivity P(k);k23. Section V extends the analytical approach applied to the BA model to generalized SF networks, with connectivity distribution P(k);k222g , g.0. Finally, in Sec. VI we draw our conclusions and per￾spectives. II. THE SIS MODEL To address the effect of the topology of complex net￾works in epidemic spreading we shall study the standard SIS epidemiological model @18#. Each node of the network rep￾resents an individual and each link is a connection along that the infection can spread to other individuals. The SIS model relies on a coarse grained description of the individuals in the population. Within this description, individuals can only exist in two discrete states, namely, susceptible, or ‘‘healthy,’’ and infected. These states completely neglect the details of the infection mechanism within each individual. The disease transmission is also described in an effective way. At each time step, each susceptible node is infected with probability n if it is connected to one or more infected nodes. At the same time, infected nodes are cured and be￾come again susceptible with probability d, defining an effec￾tive spreading rate l5n/d. ~Without lack of generality, we set d51.! Individuals run stochastically through the cycle susceptible → infected → susceptible, hence the name of the model. The updating can be performed with both parallel or sequential dynamics @16#. The SIS model does not take into account the possibility of individuals removal due to death or acquired immunization @18#. It is mainly used as a paradig￾matic model for the study of infectious disease that leads to an endemic state with a stationary and constant value for the prevalence of infected individuals, i.e., the degree to which the infection is widespread in the population. The topology of the network that specifies the interactions among individuals is of primary importance in determining many of the model’s features. In standard topologies the most significant result is the general prediction of a nonzero epidemic threshold lc @18#. If the value of l is above the threshold l>lc the infection spreads and becomes persistent in time. Below it l,lc , the infection dies out exponentially fast. In both sides of the phase diagram it is possible to study the behavior in time of interesting dynamical magnitudes of epidemics, such as the time survival probability and the re￾laxation to the healthy state or the stationary endemic state. In the latter case, if we start from a localized seed we can study the epidemic outbreak preceding the endemic stabili￾zation. From this general picture, it is natural to consider the epidemic threshold as completely equivalent to a critical point in a nonequilibrium phase transition @16#. In this case, the critical point separates an active phase with a stationary density of infected nodes ~an endemic state! from an absorb￾ing phase with only healthy nodes and null activity. In par￾ticular, it is easy to recognize that the SIS model is a gener￾alization of the contact process model, that has been extensively studied in the context of absorbing-state phase transitions @16#. In order to obtain an analytical understanding of the SIS model behavior on complex networks, we can apply a single site dynamical MF approach, that we expect to recover ex￾actly the model’s behavior due to the nonlocal connectivity of these graphs. Let us consider separately the case of the exponentially bounded and SF networks. III. EXPONENTIAL NETWORKS: THE WATTS-STROGATZ MODEL The class of exponential networks refers to random graph models that produce a connectivity distribution P(k) peaked at an average value ^k& and decaying exponentially fast for k@^k& and k!^k&. Typical examples of such a network are the random graph model @9# and the small-world model of WS @10#. The latter has recently been the object of several studies as a good candidate for the modeling of many real￾istic situations in the context of social and natural networks. In particular, the WS model shows the ‘‘small-world’’ prop￾erty common in random graphs @13#; i.e., the diameter of the graph—the shortest chain of links connecting any two vertices—increases very slowly, in general logarithmically with the network size @12#. On the other hand, the WS model has also a local structure ~clustering property! that is not found in random graphs with finite connectivity @10,12#. The WS graph is defined as follows @10,12#: The starting point is a ring with N nodes, in which each node is symmetrically connected with its 2K nearest neighbors. Then, for every node each link connected to a clockwise neighbor is rewired to a randomly chosen node with probability p, and preserved with probability 12p. This procedure generates a random graph with a connectivity distributed exponentially for large k @10,12#, and an average connectivity ^k&52K. The graphs have small-world properties and a nontrivial ‘‘clustering co￾efficient’’; i.e., neighboring nodes share many common neighbors @10,12#. The richness of this model has stimulated an intense activity aimed at understanding the network’s properties upon changing p and the network size N @10– 13,20,21#. At the same time, the behavior of physical models on WS graphs has been investigated, including epidemio￾logical percolation models @15,20,22# and models with epi￾demic cycles @23#. Here we focus on the WS model with p51; it is worth noticing that even in this extreme case the network retains some memory of the generating procedure. The network, in fact, is not locally equivalent to a random graph in that each node has at least K neighbors. Since the fluctuations in the connectivity are very small in the WS graph, due to its ex￾ponential distribution, we can approach the analytical study of the SIS model by considering a single MF reaction equa￾tion for the density of infected nodes r(t), ] tr~t!52r~t!1l^k&r~t!@12r~t!#1~higher-order terms!. ~2! The MF character of this equation stems from the fact that we have neglected the density correlations among the differ￾ent nodes, independently of their respective connectivities. In Eq. ~2! we have ignored all higher order corrections in r(t), since we are interested in the onset of the infection close to ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 066117-2

EPIDEMIC DYNAMICS AND ENDEMIC STATES IN PHYSICAL REVIEW E 63 066117 0. 03 P 0.2 FIG. 1. Density of infected nodes p as a function of a in the ws 2. Log-log plot of density of infected node p as a function etwork( full line)and the ba network(dashed line) Ae in Ws network, with Ac=0. 1643+0.01. The full line is a fit to the form p(a-A, with an exponent B=0.97+0.04 the phase transition, .e, at p(o)<1. The first term on the simulations we consider the ws network with parameter right-hand side(rhs) in Eq.(2)considers infected nodes be- K=3, which corresponds to an average connectivity come healthy with unit rate. The second term represents the(<)=6 As shown in Figs. I and 2, the SIs model on a wS graph active node. This is proportional to the infection spreading exhibits an epidemic threshold Ac=0.1643+0.01 that is ap- rate A, the number of links emanating from each node, and proached with linear behavior by p. The value of the thresh the probability that a given link points to a healthy node old is in good agreement with the MF predictions A tali.o(n)]. In these models, connectivity has only exponen- =1/2K=0.1666, as well as the density of infected nodes tially small fluctuations ((k2)-(k))and as a first approxi- behavior. In Fig. 2 we plot p as a function of A-Ac in mation we have considered that each node has the same log-log scale. A linear fit to the form p-(A-Ae) provides number of links, k=(k). This is equivalent to an homogene- an exponent B=0.97=0.04, in good agreement with the ana- ity assumption for the system s connectivity. After imposing lytical finding of the Eq. (4b) ne stationarity condition a,p(t)=0, we obtain the equation To complete our study of the sis model in the ws net work, we have also analyzed the epidemic spreading proper p-1+A(k)(1-p)]=0 (3) ties, computed by considering the time evolution of infec- tions starting from a very small concentration of infected nodes In Fig 3 we plot the evolution of the infected nodes for the steady state density p of infected nodes. This equation density as a function of time for epidemics in the supercriti defines an epidemic threshold Ac=(k), and yields cal regime(A>As) that start from a single infected node Each curve represents the average over several spreading p=0ifA<λ (4a) events with the same A. We clearly notice a spreading growth faster than any power law, in agreement with Eq(2) p-A-M (4b) that predicts an exponential saturation to the endemic steady state. In the subcritical regime (A<Ac), by introducing In analogy with critical phenomena, we can consider p as the small perturbation to the stationary state p=0, and keeping order parameter of a phase transition and A as the tuning decays following the exponential relaxation a,p(o) parameter, recovering a MF critical behavior [24]. It is pos- sible to refine the above calculations by introducing connec- tic relaxation time (k)(Ac-A)P(t). This equation introduces a characteris- tivity fluctuations(as it will be done later for SF networks ee Sec. IV). However, the results are qualitatively and quan T-=(k(c-x titatively the same as far as we are only concerned with the nodel,s behavior close to the threshold In order re with the analytical predictic have performed large scale simulations of the Sis model in the ws network with p=1. Simulations were implemented on graphs with number of nodes ranging from N=10 to p(t)10 N=3X 10, analyzing the stationary properties of the density of infected nodes p, i.e., the infection prevalence. Initially we infect half of the nodes in the network, and iterate the rules of the Sis model with parallel updating. In the active phase, after an initial transient regime, the systems stabilize in a steady state with a constant average density of infected FIG. 3. Density of infected nodes p(n) as a function of time in nodes. The prevalence is computed averaging over at least spreading experiments in the Ws network. Network 100 different starting configurations, performed on at least size N=1. 5x 106. Spreading rates range from A-A=0.002 to ten different realization of the random networks. In our 0.0007( top to bottom

the phase transition, i.e., at r(t)!1. The first term on the right-hand side ~rhs! in Eq. ~2! considers infected nodes be￾come healthy with unit rate. The second term represents the average density of newly infected nodes generated by each active node. This is proportional to the infection spreading rate l, the number of links emanating from each node, and the probability that a given link points to a healthy node, @12r(t)#. In these models, connectivity has only exponen￾tially small fluctuations (^k2 &;^k&) and as a first approxi￾mation we have considered that each node has the same number of links, k.^k&. This is equivalent to an homogene￾ity assumption for the system’s connectivity. After imposing the stationarity condition ] tr(t)50, we obtain the equation r@211l^k&~12r!#50 ~3! for the steady state density r of infected nodes. This equation defines an epidemic threshold lc5^k& 21, and yields r50 if l,lc ~4a! r;l2lc if l.lc. ~4b! In analogy with critical phenomena, we can consider r as the order parameter of a phase transition and l as the tuning parameter, recovering a MF critical behavior @24#. It is pos￾sible to refine the above calculations by introducing connec￾tivity fluctuations ~as it will be done later for SF networks, see Sec. IV!. However, the results are qualitatively and quan￾titatively the same as far as we are only concerned with the model’s behavior close to the threshold. In order to compare with the analytical prediction we have performed large scale simulations of the SIS model in the WS network with p51. Simulations were implemented on graphs with number of nodes ranging from N5103 to N533106, analyzing the stationary properties of the density of infected nodes r, i.e., the infection prevalence. Initially we infect half of the nodes in the network, and iterate the rules of the SIS model with parallel updating. In the active phase, after an initial transient regime, the systems stabilize in a steady state with a constant average density of infected nodes. The prevalence is computed averaging over at least 100 different starting configurations, performed on at least ten different realization of the random networks. In our simulations we consider the WS network with parameter K53, which corresponds to an average connectivity ^k&56. As shown in Figs. 1 and 2, the SIS model on a WS graph exhibits an epidemic threshold lc50.164360.01 that is ap￾proached with linear behavior by r. The value of the thresh￾old is in good agreement with the MF predictions lc 51/2K50.1666, as well as the density of infected nodes behavior. In Fig. 2 we plot r as a function of l2lc in log-log scale. A linear fit to the form r;(l2lc)b provides an exponent b50.9760.04, in good agreement with the ana￾lytical finding of the Eq. ~4b!. To complete our study of the SIS model in the WS net￾work, we have also analyzed the epidemic spreading proper￾ties, computed by considering the time evolution of infec￾tions starting from a very small concentration of infected nodes. In Fig. 3 we plot the evolution of the infected nodes density as a function of time for epidemics in the supercriti￾cal regime (l.lc) that start from a single infected node. Each curve represents the average over several spreading events with the same l. We clearly notice a spreading growth faster than any power law, in agreement with Eq. ~2! that predicts an exponential saturation to the endemic steady state. In the subcritical regime (l,lc), by introducing a small perturbation to the stationary state r50, and keeping only first order terms in Eq. ~2!, we obtain that the infection decays following the exponential relaxation ] tr(t) 52^k&(lc2l)r(t). This equation introduces a characteris￾tic relaxation time t215^k&~lc2l! ~5! FIG. 1. Density of infected nodes r as a function of l in the WS network ~full line! and the BA network ~dashed line!. FIG. 2. Log-log plot of density of infected node r as a function of l2lc in WS network, with lc50.164360.01. The full line is a fit to the form r;(l2lc)b , with an exponent b50.9760.04. FIG. 3. Density of infected nodes r(t) as a function of time in supercritical spreading experiments in the WS network. Network size N51.53106. Spreading rates range from l2lc50.002 to 0.0007 ~top to bottom!. EPIDEMIC DYNAMICS AND ENDEMIC STATES IN . . . PHYSICAL REVIEW E 63 066117 066117-3

ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 p()10 0.1400,1450.1500.1550.160 FIG. 4. Density of infected nodes p(r) as a function of time in FIG. 6. Inverse relaxation time for the sis model in the ws aph as a function of the spreading rate A, estimated from the slope subcritical spreading experiments in the ws network. Network size of the exponential decay of the infected nodes density p(o(o) and the survival probability P,(0(o) whereas the intercept yields 1.0, in good agreement with the that diverges at the epidemic threshold Below the threshold, theoretical predictions of Eq (5),(k)=6 and(k)Ac=1,re- the epidemic outbreak dies within a finite time, i.e., it does spectively not reach a stationary endemic state. In Fig. 4 we plot aver- In summary, numerical and analytical results confirms age of p(t) for epidemics starting with an initial concentra- that for WS graphs, the standard epidemiological picture(of- tion Po=0.01 of infected nodes; the figure shows a clear ten called the deterministic approximation) is qualitatively exponential approach to the healthy (absorbing)state as pre- and quantitatively correct. This result, that is well known for dicted by Eq (5). In the subcritical regime, we can compute random graphs, holds also in the wS model despite the dif- also the surviving probability P, (n), defined as the probabil- ferent local structure ity that an epidemic outbreak survives up to the time t [16] In Fig. 5 we plot the survival probability computed from IV SCALE-FREE NETWORKS: THE BARABASLALBERT simulations starting with a single infected node in a ws MODEL raph of size N=3X10%. The survival probability decay is obviously governed by the same exponential behavior and The BA graph was introduced as a model of growing characteristic time of the density of infected nodes as con- network(such as the Internet or the world-wide-web)in firmed by numerical simulations. Indeed, below the epidemic which the successively added nodes establish links with threshold. the relaxation to the absorbing state does not de- higher probability pointing to already highly connected pend on the network size N(see inset in Fig. 5), and the nodes [14]. This is a rather intuitive phenomenon on the average lifetime corresponding to each spreading rate A can Internet and other social networks, in which new individuals be measured by the slope of the exponential tail of P, (r)and tend to develop more easily connections with individuals that P(r). By plotting T-I as a function of Ac-A(see Fig. 6), we are already well known and widely connected. The Ba graph recover the analytic predictions, i. e, the linear behavior and Is constructed using the following algorithm [14 ]: We start the unique characteristic time for both the density and sur- from a small number mo of disconnected nodes; every time vival probability decay. The slope of the graph, measured by step a new vertex is added, with m links that are connected to means of a least squares fitting, provides a value of 6.3, an old node i with probability ∏I(k) where ki is the connectivity of the ith node. After iterating this scheme a sufficient number of times we obtain a net work sed by N nodes with connectivity distribution P(t)10 P(k)-k and average connectivity we will consider the parameters mo=5 and m=3). Despite the well-defined average connectivity, the scale invariant properties of the network turns out to play a the properties of models such as percolation [22, 25], used to mimic the resilience to attacks of a network for this class of 100150200 graphs, in fact, the absence of a characteristic scale for the connectivity makes highly connected nodes statistically sig IG. 5. Surviving probability P, (o as a function of time in nificant, and induces strong fluctuations in the connectivity subcritical ing experiments in the ws network. Network size distribution that cannot be neglected. In order to take into N=3×10 ding rates range from Ac-A=0.005 to 0.03 account these fuctuations, we have to relax the homogeneity (right to let Surviving probability for a fixed spreading rate assumption used for exponential networks, and consider the As-A=0.005 and network sizes N=3X 105, 106, and 3X 106 relative density Pk(n)of infected nodes with given conned 066117-4

that diverges at the epidemic threshold. Below the threshold, the epidemic outbreak dies within a finite time, i.e., it does not reach a stationary endemic state. In Fig. 4 we plot aver￾age of r(t) for epidemics starting with an initial concentra￾tion r050.01 of infected nodes; the figure shows a clear exponential approach to the healthy ~absorbing! state as pre￾dicted by Eq. ~5!. In the subcritical regime, we can compute also the surviving probability Ps(t), defined as the probabil￾ity that an epidemic outbreak survives up to the time t @16#. In Fig. 5 we plot the survival probability computed from simulations starting with a single infected node in a WS graph of size N533106. The survival probability decay is obviously governed by the same exponential behavior and characteristic time of the density of infected nodes as con- firmed by numerical simulations. Indeed, below the epidemic threshold, the relaxation to the absorbing state does not de￾pend on the network size N ~see inset in Fig. 5!, and the average lifetime corresponding to each spreading rate l can be measured by the slope of the exponential tail of Ps(t) and r(t). By plotting t21 as a function of lc2l ~see Fig. 6!, we recover the analytic predictions, i.e., the linear behavior and the unique characteristic time for both the density and sur￾vival probability decay. The slope of the graph, measured by means of a least squares fitting, provides a value of 6.3, whereas the intercept yields 1.0, in good agreement with the theoretical predictions of Eq. ~5!, ^k&56 and ^k&lc51, re￾spectively. In summary, numerical and analytical results confirms that for WS graphs, the standard epidemiological picture ~of￾ten called the deterministic approximation! is qualitatively and quantitatively correct. This result, that is well known for random graphs, holds also in the WS model despite the dif￾ferent local structure. IV. SCALE-FREE NETWORKS: THE BARABA´ SI-ALBERT MODEL The BA graph was introduced as a model of growing network ~such as the Internet or the world-wide-web! in which the successively added nodes establish links with higher probability pointing to already highly connected nodes @14#. This is a rather intuitive phenomenon on the Internet and other social networks, in which new individuals tend to develop more easily connections with individuals that are already well known and widely connected. The BA graph is constructed using the following algorithm @14#: We start from a small number m0 of disconnected nodes; every time step a new vertex is added, with m links that are connected to an old node i with probability P~ki!5 ki (j k j , ~6! where ki is the connectivity of the ith node. After iterating this scheme a sufficient number of times, we obtain a net￾work composed by N nodes with connectivity distribution P(k);k23 and average connectivity ^k&52m ~in this work we will consider the parameters m055 and m53). Despite the well-defined average connectivity, the scale invariant properties of the network turns out to play a major role on the properties of models such as percolation @22,25#, used to mimic the resilience to attacks of a network. For this class of graphs, in fact, the absence of a characteristic scale for the connectivity makes highly connected nodes statistically sig￾nificant, and induces strong fluctuations in the connectivity distribution that cannot be neglected. In order to take into account these fluctuations, we have to relax the homogeneity assumption used for exponential networks, and consider the relative density rk(t) of infected nodes with given connec￾FIG. 4. Density of infected nodes r(t) as a function of time in subcritical spreading experiments in the WS network. Network size N533106. Spreading rates range from lc2l50.005 to 0.03 ~right to left!. FIG. 5. Surviving probability Ps(t) as a function of time in subcritical spreading experiments in the WS network. Network size N533106. Spreading rates range from lc2l50.005 to 0.03 ~right to left!. Inset: Surviving probability for a fixed spreading rate lc2l50.005 and network sizes N533105, 106, and 33106. FIG. 6. Inverse relaxation time for the SIS model in the WS graph as a function of the spreading rate l, estimated from the slope of the exponential decay of the infected nodes density r(t) (s), and the survival probability Ps(t) (L). ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 066117-4

EPIDEMIC DYNAMICS AND ENDEMIC STATES IN PHYSICAL REVIEW E 63 066117 tivity k, i. e, the probability that a node with k links is fected. The dyi I MF reaction rate equations can be written as a,Pk(0=-Pk(0)+Ak[l-P(oJo(p(n), (7) where also in this case we have considered a unitary recov ery rate and neglected higher order terms [p(r)<1]. The creation term considers the probability that a node with k links is healthy [1-PK(n)] and gets the infection via a con- nected node. The probability of this last event is proportional to the infection rate n the number of connections k and the FIG. 7. Persistence p as a function of 1/ for BA networks of probability e(p(n)) that any given link points to an infected different sizes: N=105(+), N=5x105(D), N=106(X),N node. Here we neglect the connectivity corrections,ie.,we=5×10°(O,andN=8.5×10°(◇). The linear behavior on the consider that the probability that a link points to an infected semilogarithmic scale proves the stretched exponential behavior node does not depend on the connectivity of the emanating predicted for the persistence. The full line is a fit to the form p node and is only a function of the total density of infected - exp(-ChA) nodes pointed by the link [26]. In the steady (endemic) state, In order to find the behavior of the density of infected nodes is just a function of A. Thus, the probability e becomes also an implicit function of the spreading rate, and by impos- we have to solve Eq. (10), that reads as ing stationarity [aP(1)=0], we obtain p=2m2A6(A) ke() 1+kA6(A) Pk 1+kλ6(A) By substituting the obtained expression for e(A)and solv This set of equations show that the higher the node connec- ing the integral we find at the lowest order in A tivity, the higher the probability to be in an infected state (14) This inhomogeneity must be taken into account in the com- putation of 0(). Indeed, the probability that a link points to This result shows the surprising absence of any epidemic a node with s links is proportional to sP(s). In other words, threshold or critical point in the model, i.e. A,=0. This can a randomly chosen link is more likely to be connected to an be intuitively understood by noticing that for usual lattices infected node with high connectivity, yielding the relatio smaller is the epidemic threshold. In the ba network the kP(k)pk unbounded fluctuations in the number of links emanating 6(A) ∑xsP(s) (9) from each node((k)=o) plays the role of an infinite con- nectivity, annulling thus the threshold. This implies that in- Since Pk is on its turn a function of o(), we obtain fections can pervade a BA network, whatever the infection self-consistency equation that allows to find 0() and an rate they have explicit form for Eq.( 8). Finally, we can evaluate the order The numerical simulations performed on the BA network arameter(persistence)p using the relation confirm the picture extracted from the analytic treatment. We consider the Sis model on BA networks of size ranging from N=10 to N=85X 106. In Fig. I we have plotted the epi p=∑P(k)p, (10) demic persistence p as a function of A in a linear scale.The function p approaches smoothly the value x=0 with vanish- ng slope. Figure 7, in fact, shows that the infection preva In order to perform an explicit calculation for the BA model, lence in the steady state decays with A as p-exp(-CIA) we use a continuous k approximation that allows the practi- cal substitution of series with integrals [14]. The full connec- where C is a constant. The numerical value obtained C-I tivity distribution is given by P(k)=2m/k-3, where m is 2.5 is also in good agreement with the theoretical predic- he minimum number of connection at each node. By notic- tion C-l=m=3. In order to rule out the presence of finite size effect hiding an abrupt transition(the so-called smooth- ing that the average connectivity is (k)=mkP(k)dk=2 m, ing out of critical points [16], we have inspected the behav- Eq(9)gives ior of the stationary persistence for network sizes varying over three orders of magnitude. The total absence of scaling 6(A)=mA6(A) mk1+kxe() (11) of p and the perfect agreement for any size with the analyti- cally predicted exponential behavior allows us to definitely confirm the absence of any finite epidemic threshold. In Fig ch yields the solution 8, we also provide an illustration of the behavior of the prob- ability Pk that a node with given connectivity k is infected 6(A)= Am(1-o-l/n (12) Also in this case we found a behavior with k in complete agreement with the analytical prediction of Eq. ( 8) 066117-5

tivity k, i.e., the probability that a node with k links is in￾fected. The dynamical MF reaction rate equations can thus be written as ] trk~t!52rk~t!1lk@12rk~t!#Q„r~t!…, ~7! where also in this case we have considered a unitary recov￾ery rate and neglected higher order terms @r(t)!1#. The creation term considers the probability that a node with k links is healthy @12rk(t)# and gets the infection via a con￾nected node. The probability of this last event is proportional to the infection rate l, the number of connections k, and the probability Q„r(t)… that any given link points to an infected node. Here we neglect the connectivity corrections, i.e., we consider that the probability that a link points to an infected node does not depend on the connectivity of the enanating node and is only a function of the total density of infected nodes pointed by the link @26#. In the steady ~endemic! state, r is just a function of l. Thus, the probability Q becomes also an implicit function of the spreading rate, and by impos￾ing stationarity @] trk(t)50#, we obtain rk5 klQ~l! 11klQ~l! . ~8! This set of equations show that the higher the node connec￾tivity, the higher the probability to be in an infected state. This inhomogeneity must be taken into account in the com￾putation of Q(l). Indeed, the probability that a link points to a node with s links is proportional to sP(s). In other words, a randomly chosen link is more likely to be connected to an infected node with high connectivity, yielding the relation Q~l!5( k kP~k!rk (s sP~s! . ~9! Since rk is on its turn a function of Q(l), we obtain a self-consistency equation that allows to find Q(l) and an explicit form for Eq. ~8!. Finally, we can evaluate the order parameter ~persistence! r using the relation r5( k P~k!rk , ~10! In order to perform an explicit calculation for the BA model, we use a continuous k approximation that allows the practi￾cal substitution of series with integrals @14#. The full connec￾tivity distribution is given by P(k)52m2/k23, where m is the minimum number of connection at each node. By notic￾ing that the average connectivity is ^k&5*m `kP(k)dk52m, Eq. ~9! gives Q~l!5mlQ~l!E m ` 1 k3 k2 11klQ~l! , ~11! which yields the solution Q~l!5 e21/ml lm ~12e21/ml! 21. ~12! In order to find the behavior of the density of infected nodes we have to solve Eq. ~10!, that reads as r52m2lQ~l!E m ` 1 k3 k 11klQ~l! . ~13! By substituting the obtained expression for Q(l) and solv￾ing the integral we find at the lowest order in l r;e21/ml. ~14! This result shows the surprising absence of any epidemic threshold or critical point in the model, i.e., lc50. This can be intuitively understood by noticing that for usual lattices and MF models, the higher the node’s connectivity, the smaller is the epidemic threshold. In the BA network the unbounded fluctuations in the number of links emanating from each node (^k2 &5`) plays the role of an infinite con￾nectivity, annulling thus the threshold. This implies that in￾fections can pervade a BA network, whatever the infection rate they have. The numerical simulations performed on the BA network confirm the picture extracted from the analytic treatment. We consider the SIS model on BA networks of size ranging from N5103 to N58.53106. In Fig. 1 we have plotted the epi￾demic persistence r as a function of l in a linear scale. The function r approaches smoothly the value l50 with vanish￾ing slope. Figure 7, in fact, shows that the infection preva￾lence in the steady state decays with l as r;exp(2C/l), where C is a constant. The numerical value obtained C21 52.5 is also in good agreement with the theoretical predic￾tion C215m53. In order to rule out the presence of finite size effect hiding an abrupt transition ~the so-called smooth￾ing out of critical points @16#!, we have inspected the behav￾ior of the stationary persistence for network sizes varying over three orders of magnitude. The total absence of scaling of r and the perfect agreement for any size with the analyti￾cally predicted exponential behavior allows us to definitely confirm the absence of any finite epidemic threshold. In Fig. 8, we also provide an illustration of the behavior of the prob￾ability rk that a node with given connectivity k is infected. Also in this case we found a behavior with k in complete agreement with the analytical prediction of Eq. ~8!. FIG. 7. Persistence r as a function of 1/l for BA networks of different sizes: N5105 (1), N553105 (h), N5106 (3), N 553106 (s), and N58.53106 (L). The linear behavior on the semilogarithmic scale proves the stretched exponential behavior predicted for the persistence. The full line is a fit to the form r ;exp(2C/l). EPIDEMIC DYNAMICS AND ENDEMIC STATES IN . . . PHYSICAL REVIEW E 63 066117 066117-5