复旦大学：《网络科学导论 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 02 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)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

ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 P()10 10 0.00 0 020406080100 FIG. 8. The density Pk, defined as the fraction of FIG. 10. Surviving probability P, (n) as a function of time in connectivity k that are infected, in a BA network subcritical spreading experiments in the BA network. Spreading =5x10 and spreading rates A=0.1, 0.08, and 0.06 ate A=0.065. Network sizes ranging from N=6.25x 10 to N top). The plot recovers the form predicted in Eq (8) =5×103( bottom to top) cal results pointing out the existence of a different epidemio- Our numerical study of the spreading dynamical proper- logical framework for SF networks. The absence of an epi ties on the ba network is reported in Figs. 9 and 10 In Fig. demic threshold, a central element in the theory of 9 we plot the growth of the epidemics starting from a single infected node. We observe that the spreading growth in time epidemics, opens a different scenario and rationalization for has an algebraic form, as opposed to the exponential growth of the epidemic threshold, that leaves SF networks com- typical of mean-field continuous phase transitions close to pletely disarmed with respect to epidemic outbreaks, is for- the critical point [16], and the behavior of the SIS model in tunately balanced from a corresponding exponentially low the WS graph(see Fig. 3). The surviving probability P (t) for a fixed value of A and networks of different size N is prevalence at small spreading rates. In addition, the absence of a critical threshold, and the associated diverging response reported in Fig 10. In this case, we recover an exponential function, makes the increase of the endemic prevalence with behavior in time, that has its origin in the finite size of the the spreading rate very slow. This new perspective seems to network. In fact, for any finite system, the epidemic will be particularly relevant in the rationalization of epidemic individuals cure the infection at the same time. Inis prob. data from computer virus infections [27] ability is decreasing with the system size and the lifetime is infinite only in the thermodynamic limit N-o. However V GENERALIZED SCALE-FREE NETWORKS he lifetime becomes virtually infinite(the metastable state Recently there has been a burst of activity in the modell has a lifetime too long for our observation period)for of SF complex network. The recipe of Barabasi and Albert enough large sizes that depend upon the spreading rate A. [14] has been followed by several variations and generaliza- This is a well-known feature of the survival probability in tions [28-31] and the revamping of previous mathematical finite size absorbing-state systems poised above the critical works [32]. All these studies propose methods to generate SF point. In our case, this picture is confirmed by numerical networks with variable exponent y. The analytical treatment simulations that shows that the average lifetime of the sur- presented in the previous section for the SIS model can be vival probability is increasing with the network size for all easily generalized to SF networks with connectivity distribu- the values of A. Given the intrinsic dynamical nature of tion with y>0. Consider a generalized SF network with a scale-free networks, this result could possibly have several normalized connectivity distribution given by practical implications in the study of epidemic spreading in real growing networks P(k)=(1+y)m1+k-2-y, (15) The numerical analysis supports and confirms the analyti where we are approximating the connectivity k as ous variable and assuming m the mum connectivity any node. The average connectivity is thus p( For any connectivity distribution, the relative density of in- fected nodes Pk is given by Eq( 8). Applying then Eq.(9)to compute self-consistently the probability 0, we obtain FIG. 9. Density of nodes p(r)as a function of time in 6(A)=F(1,y,1+y,-[mA(A)]-1),(17 supercritical spreading experiments in the Ba network. Network size N= 106 Spreading rates range from A=0.05 to 0.065(bottom where F is the Gauss hypergeometric function [33]. On the to top) other hand, the expression for the density p, Eq. (10), yields 066117-6

Our numerical study of the spreading dynamical proper￾ties on the BA network is reported in Figs. 9 and 10. In Fig. 9 we plot the growth of the epidemics starting from a single infected node. We observe that the spreading growth in time has an algebraic form, as opposed to the exponential growth typical of mean-field continuous phase transitions close to the critical point @16#, and the behavior of the SIS model in the WS graph ~see Fig. 3!. The surviving probability Ps(t) for a fixed value of l and networks of different size N is reported in Fig 10. In this case, we recover an exponential behavior in time, that has its origin in the finite size of the network. In fact, for any finite system, the epidemic will eventually die out because there is a finite probability that all individuals cure the infection at the same time. This prob￾ability is decreasing with the system size and the lifetime is infinite only in the thermodynamic limit N→`. However, the lifetime becomes virtually infinite ~the metastable state has a lifetime too long for our observation period! for enough large sizes that depend upon the spreading rate l. This is a well-known feature of the survival probability in finite size absorbing-state systems poised above the critical point. In our case, this picture is confirmed by numerical simulations that shows that the average lifetime of the sur￾vival probability is increasing with the network size for all the values of l. Given the intrinsic dynamical nature of scale-free networks, this result could possibly have several practical implications in the study of epidemic spreading in real growing networks. The numerical analysis supports and confirms the analyti￾cal results pointing out the existence of a different epidemio￾logical framework for SF networks. The absence of an epi￾demic threshold, a central element in the theory of epidemics, opens a different scenario and rationalization for epidemic events in these networks. The dangerous absence of the epidemic threshold, that leaves SF networks com￾pletely disarmed with respect to epidemic outbreaks, is for￾tunately balanced from a corresponding exponentially low prevalence at small spreading rates. In addition, the absence of a critical threshold, and the associated diverging response function, makes the increase of the endemic prevalence with the spreading rate very slow. This new perspective seems to be particularly relevant in the rationalization of epidemic data from computer virus infections @27#. V. GENERALIZED SCALE-FREE NETWORKS Recently there has been a burst of activity in the modeling of SF complex network. The recipe of Baraba´si and Albert @14# has been followed by several variations and generaliza￾tions @28–31# and the revamping of previous mathematical works @32#. All these studies propose methods to generate SF networks with variable exponent g. The analytical treatment presented in the previous section for the SIS model can be easily generalized to SF networks with connectivity distribu￾tion with g.0. Consider a generalized SF network with a normalized connectivity distribution given by P~k!5~11g!m11g k222g , ~15! where we are approximating the connectivity k as a continu￾ous variable and assuming m the minimum connectivity of any node. The average connectivity is thus ^k&5 E m ` kP~k!dk511g g m. ~16! For any connectivity distribution, the relative density of in￾fected nodes rk is given by Eq. ~8!. Applying then Eq. ~9! to compute self-consistently the probability Q, we obtain Q~l!5F„1,g,11g,2@mlQ~l!# 21…, ~17! where F is the Gauss hypergeometric function @33#. On the other hand, the expression for the density r, Eq. ~10!, yields FIG. 10. Surviving probability Ps(t) as a function of time in subcritical spreading experiments in the BA network. Spreading rate l50.065. Network sizes ranging from N56.253103 to N 553105 ~bottom to top!. FIG. 8. The density rk , defined as the fraction of nodes with connectivity k that are infected, in a BA network of size N 553105 and spreading rates l50.1, 0.08, and 0.065 ~bottom to top!. The plot recovers the form predicted in Eq. ~8!. FIG. 9. Density of infected nodes r(t) as a function of time in supercritical spreading experiments in the BA network. Network size N5106.Spreading rates range from l50.05 to 0.065 ~bottom to top!. ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 066117-6

EPIDEMIC DYNAMICS AND ENDEMIC STATES IN PHYSICAL REVIEW E 63 066117 =F(1,1+y,2+y,-[mA6(A)) (18) That is, we obtain a power-law behavior with exponent B 1/(y-1)>l, but now we observe the presence of a non- In order to solve eqs.(17)and(18)in the limit p-0 zero threshold (which obviously corresponds also to 0-0, we must per form a Taylor expansion of the hypergeometric function. The expansion for Eq.(17)has the form [33] (27) F(1,y,1+y,-[mA6(A)]) In this case, a critical threshold reappears in the model. How- ever, the epidemic threshold is approached smoothly without (m6)y+y∑( (m入e) any sign of the singular behavior associated with critical point. (iii)y>2: The relevant terms in the e expansion are now where T(x)is the standard gamma function. An analogous 6(A)=-,mA6 (28) expression holds for Eq (18). The expansion(19) is valid for -2(mA6)2 any y*+ 1, 2, 3,... Integer values of y must be analyzed in a case by case basis. (The particular value y=I was consid- and the relevant expression for e is ered in the previous section. For all values of y, the leading behavior of Eq (18)is the same 6(A)= (29) 1+ nO which yields the behavior for The leading behavior in the rhs of Eq. (19), on the other P-x-Ac hand, depends on the particular value of y (01 be considered of general validity. Indeed, for connectivities 1i)12 the usual MF critical behavior is recovered and the SF rk is indistinguishable from an exponential The expression for p is finally VL CONCLUSIONS The emerging picture for disease spreading in complex networks emphasizes the role of topology in epidem 661177

r5F„1,11g,21g,2@mlQ~l!# 21…. ~18! In order to solve Eqs. ~17! and ~18! in the limit r→0 ~which obviously corresponds also to Q→0, we must per￾form a Taylor expansion of the hypergeometric function. The expansion for Eq. ~17! has the form @33# F„1,g,11g,2@mlQ~l!# 21… . gp sin~gp! ~mlQ! g 1g(n51 ` ~21! n ~mlQ! n n2g , ~19! where G(x) is the standard gamma function. An analogous expression holds for Eq. ~18!. The expansion ~19! is valid for any gÞ1,2,3,... . Integer values of g must be analyzed in a case by case basis. ~The particular value g51 was consid￾ered in the previous section.! For all values of g, the leading behavior of Eq. ~18! is the same, r. 11g g mlQ. ~20! The leading behavior in the rhs of Eq. ~19!, on the other hand, depends on the particular value of g. ~i! 0,g,1: In this case, one has Q~l!. gp sin~gp! ~mlQ! g , ~21! from which we obtain Q~l!.F gp sin~gp! G 1/(12g) ~ml! g/(12g) . ~22! Combining this with Eq. ~20!, we obtain r;l1/(12g) . ~23! Here we have again the total absence of any epidemic thresh￾old and the associated critical behavior, as we have already shown for the case g51. In this case, however, the relation between r and l is given by a power law with exponent b 51/(12g), i.e., b.1. ~ii! 1,g,2: In this case, to obtain a nontrivial informa￾tion for Q, we must keep the first two most relevant terms in Eq. ~19!, Q~l!. gp sin~gp! ~mlQ! g 1 g g21 mlQ. ~24! From here we get Q~l!.F 2sin~gp! p~g21! m ~ml! g S l2 g21 mg D G 1/(g21) . ~25! The expression for r is finally r.S l2 g21 mg D 1/(g21) ;~l2lc ! 1/(g21). ~26! That is, we obtain a power-law behavior with exponent b 51/(g21).1, but now we observe the presence of a non￾zero threshold lc5g21 mg . ~27! In this case, a critical threshold reappears in the model. How￾ever, the epidemic threshold is approached smoothly without any sign of the singular behavior associated with critical point. ~iii! g.2: The relevant terms in the Q expansion are now Q~l!. g g21 mlQ2 g g22 ~mlQ! 2, ~28! and the relevant expression for Q is Q~l!. g22 g21 1 l2m S l2 g21 mg D , ~29! which yields the behavior for r r;l2lc ~30! with the same threshold lc as in Eq. ~27! and an exponent b51. In other words, we recover the usual critical frame￾work in networks with connectivity distribution that decays faster than k to the fourth power. Obviously, an exponen￾tially bounded network is included in this last case, recover￾ing the results obtained with the homogeneous approxima￾tion of Sec. III. It is worth remarking that the above results are obtained by neglecting connectivity correlations in the network, i.e., the probability that a link points to an infected node is considered independent of the connectivity of the node from which the link is emanated @see Eq. ~7!#. This approximation appears to be irrelevant in the BA network. In different SF networks with more complex topological prop￾erties, however, connectivity correlations could play a more important role and modify the analytic forms obtained in this section, Eqs. ~23! and ~26!. On the other hand, conclusions concerning the epidemic threshold absence for connectivity distributions decaying more slowly than a cubic power can be considered of general validity. Indeed, for connectivities decaying faster than the cubic power, the connectivity fluc￾tuations are bounded, and one would expect to obtain the same qualitative behavior as in exponential distribution. In summary, for all SF networks with 0,g<1, we re￾cover the absence of an epidemic threshold and critical be￾havior, i.e., r50 only if l50, and r has a vanishing slope when l→0. In the interval 1,g,2, an epidemic threshold reappears (r→0 if l→lc), but it is also approached with vanishing slope, i.e., no singular behavior. Eventually, for g.2 the usual MF critical behavior is recovered and the SF network is indistinguishable from an exponential network. VI. CONCLUSIONS The emerging picture for disease spreading in complex networks emphasizes the role of topology in epidemic mod￾EPIDEMIC DYNAMICS AND ENDEMIC STATES IN . . . PHYSICAL REVIEW E 63 066117 066117-7

ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 eling. In particular, the absence of epidemic threshold and works also open the path to many other questions concerning critical behavior in a wide range of SF networks provides an the effect of immunity and other modifications of epidem unexpected result that changes radically many standard con- models. As well, the critical properties of many nonequilib clusions on epidemic spreading. Our results indicate that in- rium systems could be affected by the topology of SF net fections can proliferate on these networks whatever spread- works. Given the wide context in which SF networks appear, ing rates they may have. This very bad news is, however, the results obtained here could have intriguing implications balanced by the exponentially small prevalence for a wide in many biological and social systems range of spreading rates (A<1). This point appears to be particularly relevant in the case of technological networks ACKNOWLEDGMENTS such as the internet and the world-wide-web that show a se ity with exponents y=2.5 [5, 6]. For instance, the This work was partially supported by the European Net present picture fits perfectly with the observation from real work through Contract No. ERBFMRXCT980183. R.P.-S data of computer virus spreading, and could solve the long- also acknowledges support from Grant No. CICYT PB97 standing problem of the generalized low prevalence of com- 0693. We thank S. Franz, M.-C. Miguel,R. V. Sole, M puter viruses without assuming any global tuning of the Vergassola,S. Visintin,S. Zapperi, and R. Zecchina for spreading rates[17, 27]. The peculiar properties of SF net- comments and discussions [1]G Weng, U.S. Bhalla, and R. lyengar, Science 284, 92(1999): [17JO. Kephart, S.R. White, and D M. Chess, IEEE Spectr. 30, S. Wasserman and K. Faust, Social Nenwwork Analysis(Cam- 20(1993): J.O. Kephart, G B Sorkin, D.M. Chess, and S.R. bridge University Press, Cambridge, 1994) White, Sci. Am. 277, 56(1997 [2]LAN. Amaral, A. Scala, M. Barthelemy, and H.E. Stanley, [18]NTJ. Bailey, The Mathematical Theory of Infectious Dis Proc. Natl. Acad. Sci. U.S.A. 97, 11 149(2000) eases, 2nd ed(Griffin, London, 1975): J D. Murray, Math- 3 H Jeong, B. Tombor, R. Albert, Z N. Oltvar, and A.-L. Bara ematical Biology(Springer Verlag, Berlin, 1993) basi, Nature( London)407, 651(2000) [19]MK. Hill, Understanding Environmental Pollution(Cam- bridge University Press, Cambridge, 1997) 5]M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Com- [20]MEJ. Newman and D.J. Watts, Phys. Rev. E, 5678(1999) mun. Rev. 29, 251(1999); A Medina, I. Matt, and J. Byers ibid. 30, 18(2000); G. Caldarelli, R. Marchetti, and L. Pietron rophys. Lett. 50, 574 (2000) ero, Europhys. Lett. 52, 386(2000) [22]DS. Callaway, M. E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys.Rev.Let.85,5468(2000) [6]R. Albert, H Jeong, and A- L. Barabasi, Nature( London)401,[23]G. Abramson and M. Kuperman, e-print nIn ao/0010012 [7B. H. Huberman and L.A. Adamic, Nature(London)401, 131 [24]On Euclidean lattices the order parameter behavior is p(A Ae), with Bs 1. The linear behavior is recovered above the upper critical dimension(see Ref [16) [8]B. Bollobas, Random Graphs(Academic Press, London, [25] R. Cohen, K Erez, D ben-Avraham, and S Havlin, Phys. Rey 1985) Lett.85,4626(2000 [9]P Erdos and P. Renyi, Publ. Math. Inst. Hung. Acad. Sci 5, 17 [26]One could be tempted to impose 0(p)=p highly inhomog density Pk makes this xImation []DJ. Watts and S.H. Strogatz, Nature(London) 393, 440 too strong. (1998 [27R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett.(to be [11]M. Barthelemy and L.A. N. Amaral, Phys. Rev. Lett. 82, 318 published); R. Pastor-Satorras and A. Vespignani, Phys. Rev (1999); A. Barrat, e-print cond-mat/9903323 Lett86,3200(2001) 12A. Barrat and M. Weigt, Eur. Phys. J B 13, 547(2000) 28]R. Albert and A L. Barabasi, Phys. Rev. Lett. 85, 5234(20 [13]D. J. Watts, Small Worlds: The Dynamics of Networks Be- [29]SN Dorogovtsev, J FF Mendes, and A N Samukhin, e heen Order and Randomness(Princeton University Press, cond-mat/0011115 30P. L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. [14A.-L. Barabasi and R. Albert, Science 286, 509(1999): A.-L 85,4629(2000) Barabasi, R. Albert, and H Jeong, Physica A 272, 173(1999). [31]B Tadic, Physica A 293, 273(2001) []C. Moore and Newman, Phys. Rev. E 61, 5678(2000). [32]S Bornholdt and H. Ebel, e-print cond-mat/0008465; H.A. 116JJ Marro and R Dickman, Nonequilibrium Phase Transitions mon, Biometrika 42, 425(1955 in Lattice Models(Cambridge University Press, Cambridge, [33]M. Abramowitz and 1. A Stegun, Handbook of Mathematical 1999) Functions(Dover, New York, 1972) 66117-8

eling. In particular, the absence of epidemic threshold and critical behavior in a wide range of SF networks provides an unexpected result that changes radically many standard con￾clusions on epidemic spreading. Our results indicate that in￾fections can proliferate on these networks whatever spread￾ing rates they may have. This very bad news is, however, balanced by the exponentially small prevalence for a wide range of spreading rates (l!1). This point appears to be particularly relevant in the case of technological networks such as the Internet and the world-wide-web that show a SF connectivity with exponents g.2.5 @5,6#. For instance, the present picture fits perfectly with the observation from real data of computer virus spreading, and could solve the long￾standing problem of the generalized low prevalence of com￾puter viruses without assuming any global tuning of the spreading rates @17,27#. The peculiar properties of SF net￾works also open the path to many other questions concerning the effect of immunity and other modifications of epidemic models. As well, the critical properties of many nonequilib￾rium systems could be affected by the topology of SF net￾works. Given the wide context in which SF networks appear, the results obtained here could have intriguing implications in many biological and social systems. ACKNOWLEDGMENTS This work was partially supported by the European Net￾work through Contract No. ERBFMRXCT980183. R.P.-S. also acknowledges support from Grant No. CICYT PB97- 0693. We thank S. Franz, M.-C. Miguel, R. V. Sole´, M. Vergassola, S. Visintin, S. Zapperi, and R. Zecchina for comments and discussions. @1# G. Weng, U.S. Bhalla, and R. Iyengar, Science 284, 92 ~1999!; S. Wasserman and K. Faust, Social Network Analysis ~Cam￾bridge University Press, Cambridge, 1994!. @2# L.A.N. Amaral, A. Scala, M. Barthe´le´my, and H.E. Stanley, Proc. Natl. Acad. Sci. U.S.A. 97, 11 149 ~2000!. @3# H. Jeong, B. Tombor, R. Albert, Z.N. Oltvar, and A.-L. Bara￾ba´si, Nature ~London! 407, 651 ~2000!. @4# J.M. Montoya and R.V. Sole´, e-print cond-mat/0011195. @5# M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Com￾mun. Rev. 29, 251 ~1999!; A. Medina, I. Matt, and J. Byers, ibid. 30, 18 ~2000!; G. Caldarelli, R. Marchetti, and L. Pietron￾ero, Europhys. Lett. 52, 386 ~2000!. @6# R. Albert, H. Jeong, and A.-L. Baraba¨si, Nature ~London! 401, 130 ~1999!. @7# B.H. Huberman and L.A. Adamic, Nature ~London! 401, 131 ~1999!. @8# B. Bollobas, Random Graphs ~Academic Press, London, 1985!. @9# P. Erdo¨s and P. Re´nyi, Publ. Math. Inst. Hung. Acad. Sci 5, 17 ~1960!. @10# D.J. Watts and S.H. Strogatz, Nature ~London! 393, 440 ~1998!. @11# M. Barthe´le´my and L.A.N. Amaral, Phys. Rev. Lett. 82, 3180 ~1999!; A. Barrat, e-print cond-mat/9903323. @12# A. Barrat and M. Weigt, Eur. Phys. J. B 13, 547 ~2000!. @13# D. J. Watts, Small Worlds: The Dynamics of Networks Be￾tween Order and Randomness ~Princeton University Press, New Jersey, 1999!. @14# A.-L. Baraba´si and R. Albert, Science 286, 509 ~1999!; A.-L. Baraba´si, R. Albert, and H. Jeong, Physica A 272, 173 ~1999!. @15# C. Moore and M.E.J. Newman, Phys. Rev. E 61, 5678 ~2000!. @16# J. Marro and R. Dickman, Nonequilibrium Phase Transitions in Lattice Models ~Cambridge University Press, Cambridge, 1999!. @17# J.O. Kephart, S.R. White, and D.M. Chess, IEEE Spectr. 30, 20 ~1993!; J.O. Kephart, G.B. Sorkin, D.M. Chess, and S.R. White, Sci. Am. 277, 56 ~1997!. @18# N.T.J. Bailey, The Mathematical Theory of Infectious Dis￾eases, 2nd ed. ~Griffin, London, 1975!; J.D. Murray, Math￾ematical Biology ~Springer Verlag, Berlin, 1993!. @19# M.K. Hill, Understanding Environmental Pollution ~Cam￾bridge University Press, Cambridge, 1997!. @20# M.E.J. Newman and D.J. Watts, Phys. Rev. E 60, 5678 ~1999!. @21# M. Argollo de Menezes, C. Moukarzel, and T.J.P. Penna, Eu￾rophys. Lett. 50, 574 ~2000!. @22# D.S. Callaway, M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. Lett. 85, 5468 ~2000!. @23# G. Abramson and M. Kuperman, e-print nln.ao/0010012. @24# On Euclidean lattices the order parameter behavior is r;(l 2lc)b , with b<1. The linear behavior is recovered above the upper critical dimension ~see Ref. @16#!. @25# R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 85, 4626 ~2000!. @26# One could be tempted to impose Q(r)5r; however, the highly inhomogeneous density rk makes this approximation too strong. @27# R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. ~to be published!; R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 ~2001!. @28# R. Albert and A.L. Barabasi, Phys. Rev. Lett. 85, 5234 ~2000!. @29# S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhin, e-print cond-mat/0011115. @30# P.L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. 85, 4629 ~2000!. @31# B. Tadic, Physica A 293, 273 ~2001!. @32# S. Bornholdt and H. Ebel, e-print cond-mat/0008465; H.A. Si￾mon, Biometrika 42, 425 ~1955!. @33# M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions ~Dover, New York, 1972!. ROMUALDO PASTOR-SATORRAS AND ALESSANDRO VESPIGNANI PHYSICAL REVIEW E 63 066117 066117-8