key: cord-0010869-llw5yhpm
authors: Ferreira, Silvio C.; Sander, Renan S.; Pastor-Satorras, Romualdo
title: Collective versus hub activation of epidemic phases on networks
date: 2016-03-14
journal: Phys Rev E
DOI: 10.1103/physreve.93.032314
sha: 93cd07b029f58a6aead365d6eb70681860a959b3
doc_id: 10869
cord_uid: llw5yhpm

We consider a general criterion to discern the nature of the threshold in epidemic models on scale-free (SF) networks. Comparing the epidemic lifespan of the nodes with largest degrees with the infection time between them, we propose a general dual scenario, in which the epidemic transition is either ruled by a hub activation process, leading to a null threshold in the thermodynamic limit, or given by a collective activation process, corresponding to a standard phase transition with a finite threshold. We validate the proposed criterion applying it to different epidemic models, with waning immunity or heterogeneous infection rates in both synthetic and real SF networks. In particular, a waning immunity, irrespective of its strength, leads to collective activation with finite threshold in scale-free networks with large degree exponent, at odds with canonical theoretical approaches.

The study of epidemic spreading [1] in complex topologies is one of the cornerstones of modern network science [2] , with applications in the spread of influence, opinions, and other social phenomena [3, 4] . Of particular interest is the theoretical understanding of epidemic models in scale-free (SF) networks [5] , in which the probability P (k) (degree distribution) that a node is connected to k others (has degree k) exhibits heavy tails of the form P (k) ∼ k −γ . This interest is motivated by the possible effects that a heterogeneous topology might have on the location of the epidemic threshold λ c , for some control parameter λ, signaling a phase transition separating a healthy, disease-free phase, from an infected phase, in which the epidemics can thrive [1] .

For epidemics leading to a steady (endemic) state, the main object of interest has been the susceptible-infected-susceptible (SIS) model, which is defined as follows [6] : Individuals, represented as nodes in the network, can assume two different states, susceptible (S) or healthy, and infected (I ), and capable of transmitting the disease. Infected individuals recover and become spontaneously susceptible again with a rate β that can be taken equal to 1. Transmission of the disease is effected by a rate to transmit the disease through an edge connecting an infected to a susceptible node equal to a constant λ. After a considerable theoretical effort, it has been shown that the behavior of the SIS model in uncorrelated [2] SF networks is far from trivial [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] . Two competing theories were initially proposed to account for the SIS epidemic threshold. Heterogeneous mean-field (HMF) theories [1] , neglecting both dynamical and topological correlations, provide a threshold λ HMF c = k / k 2 [8, 17] , which tends to zero in the thermodynamic limit for γ 3, and is finite for γ > 3. Quenched mean-field (QMF) theory [9] , including the full network structure through its adjacency matrix A ij [2] , but still neglecting dynamical correlations, predicts instead a threshold λ QMF c 1/ m , where m is the largest eigenvalue of the adjacency matrix. The scaling form of this threshold is given by [11, 18] λ QMF c 1/ √ k max for γ > 5/2, where k max is the maximum degree in the network, while for γ < 5/2 it yields λ QMF c k / k 2 in agreement with HMF theory. Numerical simulations [11, 12, 14] indicate that QMF is qualitatively correct in SF networks, implying that the epidemic threshold vanishes in the thermodynamic limit when k max diverges, irrespective of the degree exponent γ .

The origin of this null threshold has been physically interpreted in Ref. [14] taking explicitly into account the interplay between the lifetime of a hub of degree k, τ rec k , and the time scale τ inf k,k with which an infected hub of degree k infects a susceptible hub of degree k . The fact that the lifetime τ rec k is diverging with degree k faster than τ inf k,k for any value of λ is the ultimate cause of the null epidemic threshold in the SIS model [10, 14, 15] . However, other epidemic and dynamical models on SF networks, in particular the contact process (CP) [19] , defined by an infection rate inversely proportional to the degree of the infected node, λ/k, possess a finite threshold which can be better captured in terms of a HMF theory [20, 21] . This observation claims an understanding of the mechanisms ruling epidemic transitions, regarding in particular the conditions under which the threshold is either constant or vanishing.

The results of Ref. [14] , while important, are strictly applied to the SIS process, and thus a general formalism, adapted to more complex and realistic epidemic models with a steady state, is still lacking. Here we determine the recovery τ rec and infection τ inf time scales of hubs for generic epidemic models including waning immunity and arbitrary edge-dependent infection rates and, building on these results, we propose a classification of endemic epidemic transitions on networks: When τ rec τ inf , a scenario of local hub activation with mutual hub reinfection is at work [14] , leading to λ c → 0 when the recovery times diverge in the thermodynamic limit. In such scenario, QMF theories are expected to be qualitatively correct. On the other hand, for τ rec τ inf , mutual hub reinfection cannot take place, and an endemic state is possible only through a collective activation of the whole network in a standard phase transition occurring at a finite threshold. In this second scenario, HMF theories should be correct.

We present evidence for this scenario analyzing the susceptible-infected-removed-susceptible (SIRS) model [6] , an extension of the SIS model allowing for a waning immunity of nodes. While it has be shown that SIRS is equivalent to SIS dynamics in the framework of standard mean-field theories [22] , here we show that the effect of waning immunity is to induce a finite threshold in SF networks for γ > 3, at odds with QMF and qualitatively described by HMF theories. For sake of generality, the theory is also applied to other epidemic models without immunity, namely, the CP [19] and the generalized SIS model proposed by Karsai, Juhász, and Iglói (KJI) [23] with weighted infection rates.

Our paper is organized as follows: We develop the theory for the interplay between of hub lifetime and mutual hub infection time in Sec. II and corroborate the theory with simulations on synthetic and real SF networks in Secs. III and IV, respectively. We briefly summarize our conclusions and prospects in Sec. V. Three appendixes complement the paper: HMF and QMF theories for the investigated models are presented in Appendixes A and B while simulation methods are presented in Appendix C.

To develop our theory we study a generalized epidemic model on a network where each vertex can be either healthy or susceptible (S), infected (I ), and immune or recovered (R). Infected individuals recover spontaneously, I → R, with rate β. Recovered individuals become again spontaneously susceptible (waning immunity), R → S, with a rate α. Infected nodes of degree k transmit the disease to each adjacent susceptible node of degree k with a heterogeneous infection rate λ k,k . See Figs. 1(a) and 1(b) for a graphical description of the model. From this generalized epidemic model, classical ones can be recovered: the SIS model (α → ∞, λ k,k = λ); the CP [19] model (α → ∞, λ k,k = λ/k); the SIRS model recover spontaneously, I → R, with rate β. Recovered individuals become again spontaneously susceptible, R → S, with a rate α. Heterogeneous transmission is implemented by infected nodes of degree k transmitting the disease to adjacent susceptible nodes of degree k with rate λ k,k . (c) Schematic representation of a chain of d vertices of arbitrary degrees k 1 ,k 2 , . . . ,k d , connecting two hubs of degree k and k . The infection starting in the center of the leftmost star (red) aims to reach the rightmost star (blue). Stubs represent edges that can transmit but cannot receive the infection.

(α finite, λ k,k = λ); the KJI [23] model (α → ∞, λ k,k = λ/(kk ) θ ), etc.

To be used later, we define the average infection rate produced, λ out k , and received, λ in k , by a vertex of degree k as

respectively, where P (k |k) is the probability that a vertex of degree k is connected to vertex of degree k [24] .

We focus in the first place on the hub lifetime τ rec k , which is defined as the average time that a hub of degree k, starting from a configuration with a single infected node, takes to reach a configuration in which the hub and its nearest neighbors are all susceptible. To estimate this quantity, we approximate the dynamics of a hub of degree k by that of a star-like graph, composed by a center connected to k nodes (leaves) of arbitrary degree, the red nodes in Fig. 1 (c), where we neglect infection coming from outside the star. For analytical tractability, we consider a simplified generic epidemic process with two states (S, I ) in the leaves and three states (S, I , R) in the center. The rate of infection along an edge from a leaf to the center is approximated by λ in k and from the center to a leaf by λ out k , see Eq. (1); that is, we consider the effect of the leaves as an average over their possible degree values k , weighted with the probability P (k |k). The transitions I → S (leaves), I → R and R → S (center) have constant rates β, β, and α, respectively. The lifespan for this dynamics is larger than in the real model, where leaves can also assume the R state, and so it provides an upper bound for the true τ rec k . We approximate this dynamics in a star as follows: (i) At t = 0 the center is infected and all leaves are susceptible.

(ii) At time t 1 = 1/β the center becomes recovered and n 1 leaves are infected with probability

where p 1 = 1 − exp(−λ out k /β) is the probability that each leaf was infected by the center in the interval t < t 1 .

(iii) At time t = t 1 + t 2 , where t 2 has a distribution ρ 2 (t 2 ) = α exp(−αt 2 ), the center becomes susceptible and n 2 leaves remain infected with probability

where p 2 = exp(−βt 2 ) is the probability that each active leaf remains infected for a time t 2 .

(iv) At time t = t 1 + t 2 + t 3 , where t 3 = 1/β, all n 2 leaves infected at time t 1 + t 2 become (synchronously) susceptible and the center is infected again with probability

where p 3 = 1 − exp(−λ in k /β) is the probability that each leaf sent the infection to the center during a time t 3 .

Steps (ii) and (iv) are essentially a generalization of the approximation for SIS dynamics on stars in Ref. [14] , in which stochasticity of infective time and multiple infections of the leaves are neglected, while step (iii) does not involve approximations. Treating step (iii) stochastically is essential since the rare events in which only a few infected leaves survive cannot be neglected. The probability that the star returns to its initial state in one step with interevent times t 1 , t 2 , and t 3 is

P 2 (n 2 |n 1 )P 3 (n 2 ).

Averaging q k (t 2 ) over ρ 2 (t 2 ) we finally have

. Now, the probability that this dynamics survives for s steps of average duration

We thus obtain the final result,

Considering the absence of waning immunity inserting in Eq. (6) the limit lim α→∞ αe −αt = δ(t), the Dirac δ function, and assuming λ in

In the case of α finite, Eq. (6) becomes, after the change of variable u = Ae −βt ,

We can estimate the behavior of Q k in the limit of large k using

valid for A < 1, and (11) where (z) is the gamma function [25] , and in which the extension of the integral's upper limit to infinity is valid for kA large. Thus, from Eq. (9), we obtain

From here and Eq. (7), it follows that, in the limit of large k,

To estimate the infection time τ inf k,k , we consider two stars of degree k (the source i = 0) and k (the target at i = d + 1), connected through a path of d vertices (i = 1,2, . . . ,d) of arbitrary degree; see Fig. 1 . The following hypotheses are used in the derivation for the case τ rec k 1/λ out k : (i) The vertex with degree k on the left (i = 0) is never recovered and transmits the infection to its nearest neighbor at i = 1 at an average rate λ out k and, in an average, a new epidemic outbreak is started at i = 1 each 1/λ out k time units.

(ii) We assume that both λ kk /β 1 and λ kk /α 1 and consider only the epidemic routes where an infected vertex always transmits the infection to its right neighbor before it becomes recovered or susceptible [14] . Additionally, we assume the average transmission rate for all edges inside the chain (i = 1, . . . ,d − 1)λ = k λ out k P (k) that leads to the average probability of transmission per edge given bȳ q =λ/(λ + β).

(iii) The rate at which an infected vertex at i = d transmits the infection to the rightmost hub of degree k at i = d + 1 is approximated by λ in k . The average probability to transmit

The probability that an infection started at i = 1 reaches the rightmost hub (i = d + 1) under these assumptions is given byq d−2q k and, consequently, the transmission rate is λ out

(v) For small-world networks with N vertices, the average distance between nodes of degrees k and k is [26] 

where κ = k 2 / k − 1, resulting in an upper bound for the infection time (inverse of the rate) given by

For the case τ rec k < 1/λ out k , the leftmost star recovers before producing the first outbreak in i = 1 and thus the infection time becomes infinite.

In this section we present the analysis of different epidemic models on SF networks characterized by a degree distribution P (k) ∼ k −γ , that in a network of finite size N extends up to a maximum degree [27] ,

In these networks, we have

We focus in particular on uncorrelated networks, with P (k |k) = k P (k )/ k [28] , as generated by the uncorrelated configuration (UCM) model [29] .

The SIS model is defined by α = 0 and λ k,k = λ, independent of k and k , yielding λ in k = λ out k = λ. These values imply, from Eq. (8), τ rec,SIS k ∼ exp(λ 2 k/β). On the other hand, from Eq. (15) , and using Eq. (17), we obtain a τ inf,SIS k that is constant for γ < 3 (b → 0), while for γ > 3 (b → const) it shows an algebraic increase that, for the largest hubs with degree k max given by Eq. (16) , takes the form

Both expressions have been confirmed by means of numerical simulations of the SIS model in Ref. [14] . We have thus that, for the SIS model τ rec,SIS k τ inf,SIS , i.e., the hubs survive for much longer times than are needed for hubs to reinfect another, and there is therefore a plausible scenario in which the transition is ruled by a hub activation dynamics. This possibility is substantiated by an analysis of the SIS dynamics within a theory taking into account, at a mean-field level, the dynamics of hub recovery and mutual reinfection, leading to a vanishing epidemic threshold scaling with network size in qualitative agreement with the predictions of QMF theory [14] .

In the case of the CP [19] , we have α = ∞ and λ k,k = λ/k implying λ in k = λ/ k and λ out k = λ/k, and thus, from Eq. (8), τ rec,CP k ∼ const. On the other hand, 1/λ out k , and thus τ inf,CP , diverges implying that, for any value of γ , τ rec,CP τ inf,CP . This result indicates that it is impossible to have a scenario in which the transition is driven by the successive activation and reactivation of hubs, and that the associated epidemic transition must be given by a collective phenomenon, involving the activation of the whole network. This collective transition is consistent with the finite threshold numerically observed in the CP on SF networks [20, 21] , in agreement with HMF predictions [19, 21] . Interestingly in the case of the CP, the QMF prediction [30] coincides with the HMF theory [19] , λ c = 1, indicating a threshold completely independent of the network structure. This theoretical prediction is not fully observed in numerical simulations, which show a constant threshold but that is modulated by network heterogeneity [19] [20] [21] .

The KJI model is defined by α → ∞ and a heterogeneous infection rate λ k,k = λ/(kk ) θ , with 0 θ 1; that is, the infection power decreases with the degree of both the infected and susceptible nodes connected by the corresponding edge.

Simple HMF theory [23] (see Appendix A) predicts a threshold in uncorrelated networks

which takes a finite value for γ > 3 − 2θ , and in particular for γ > 3 and any θ > 0. On the other hand, QMF theory (see Appendix A) predicts

where D m is the largest eigenvalue of the matrix D ij = A ij /(k i k j ) θ , A ij being the adjacency matrix. This largest eigenvalue (see Appendix A) increases with network size for θ < 1/2 irrespective of γ . Therefore the QMF prediction is a vanishing threshold for θ < 1/2, and a finite one otherwise.

Applying Eq. (1) to the present model leads to λ in k = λ out k = λ k 1−θ /( k k θ ), which translates, from Eq. (8), to a hub recovery time τ rec,KJI k ∼ exp(const k 1−2θ ) that is finite for θ > 1/2 and diverges as a stretched exponential for θ < 1/2. These results are backed up by numerical simulations of the KJI model on star graphs; see Fig. 2(a) . The mutual infection time of hubs for θ < 1/2 scales similarly as in the SIS dynamics τ inf,KJI ∼ N [(γ −3)/(γ −1)]b(λ) for γ > 3 and τ inf,KJI ∼ const for γ < 3, the only difference being in the factorλ = λ k −θ k 1−θ / k . For θ 1/2, we have 1/λ out k and thus τ inf,KJI diverging as in the CP case. Thus, in the case γ > 3, where HMF and QMF predictions disagree markedly for θ < 1/2, we obtain that, for θ < 1/2, the transition should be driven by a hub activation mechanism, since in this region τ rec τ inf , and thus should correspond to a vanishing threshold, qualitatively in agreement with QMF, which indeed predicts a threshold λ QMF,KJI c ∼ k θ−1/2 max ; see Appendix A. For θ > 1/2, on the other hand, the hub lifetime is finite, compatible with a collectively activated transition, and corresponding to a finite threshold, in agreement with both HMF and QMF theories. These predictions are verified in Fig. 2(b) by means of numerical simulations of the KJI model on SF networks using the quasistationary (QS) method [20, 31] , estimating the effective threshold for each network size as the position of the main peak shown by the susceptibility χ = N ( ρ 2 − ρ )/ ρ (see Appendix C for simulation details). For values of θ close to 1/2, however, long crossovers are found in the threshold, in analogy with the behavior observed in the lifespan of stars. Indeed, after a crossover that can be very long as θ approaches 1/2, the epidemic lifetime of the KJI model on star graphs of increasing size reaches the asymptotic regime of a stretched exponential; see Fig. 2 . These crossovers, also observed in the numerical estimate of the QMF threshold (see Appendix A), explain the apparently constant threshold observed in Fig. 2 for θ = 0.4. Equivalent scenarios can be drawn for γ < 3 with critical values of θ smaller than 1/2.

We finally consider the SIRS model, an extension of the SIS model, with the same λ k,k constant, but with a finite waning immunity. Application of standard mean field theories (see Appendix B) leads to exactly the same result as the SIS model, independently of the waning immunity α, i.e., λ HMF,SIRS c = k / k 2 and λ QMF,SIRS c = 1/ m . So, we face the same situation of the SIS and KJI models, with two contradictory predictions in SF networks for γ > 3.

In the SIS model, from Eq. (13) , and given that λ in

that is, an algebraic increase of the hub recovery time with degree, modulated by the exponents α and β. This analytic prediction is confirmed in numerical simulations of the SIRS model using the QS method (see Appendix C for details) in Fig. 3(a) . The agreement observed is expected for small λ, since only a few leaves are infected in each step and thus neglecting the recovered leaves at the end of each step becomes a good approximation.

Application of Eq. (15) turns out the same result as in the SIS model, i.e., a finite infection time for γ < 3 and an algebraic increase for γ > 3. This result, which is independent of α, is numerically confirmed in Fig. 3(b) . At this respect, it is interesting to notice that the basic hypothesis used in our analysis, see Sec. II B, considering only the epidemic routes where the infected vertices always transmit the infection to its right neighbor before it becomes recovered or susceptible [14] , is more precise for longer immunization periods (small α) since the multiple infections of a vertex in this path occurs rarely, implying the bound is an estimate of τ inf k,k for SIRS as good as or better than that for SIS.

Combining the previous results, we observe that for γ < 3, the hub recovery time is always larger than the hub infection time, the same situation observed in the SIS model, with the only difference of the sharper (exponential) increase of τ rec k in the SIS case. The scenario that we expect in this range of γ values is thus a SIS-like transition, with the hub reinfection mechanism at work and a vanishing epidemic threshold, in qualitative agreement with QMF. In order to check the prediction, we have performed numerical simulations of the SIRS model on SF networks using the QS method (see Appendix C for details). In Fig. 3 (c) we show that, for γ < 3, even a very small value of α/β leads to a scaling of the epidemic threshold against network sizes, in very good agreement with the QMF prediction.

For γ > 3, on the other hand, the situation is more complex and the threshold finite-size behavior depends on α. From the divergence of the maximum degree in Eq. (16), we obtain τ inf,SIRS ∼ N [(γ −3)/(γ −1)]b(λ) and τ rec,SIRS ∼ N (α/β)/(γ −1) , that is, algebraic increases with network size in both cases. A SIS-like regime (hub reinfection triggering epidemics where the threshold decreases with N ) is expected whenever 1/β τ inf,SIRS τ rec,SIRS , which corresponds to b(λ) < α β(γ −3) ln κ or, equivalently,

Unless α is sufficiently small and/or γ is sufficiently large, this inequality is violated, and the hub lifetime is smaller than the hub infection time. This indicates that the hub activation scenario is not viable, and in analogy with the contact process, it hints towards a finite threshold. However, for sufficiently small ϑ(α,γ ), we can observe a region of λ values for which the hub activation mechanism is at work, leading to an effective threshold decreasing with N . A sufficient condition to observe this effective SIS-like behavior is βϑ(α,γ ) < λ SIS c (N ), the effective SIS threshold in the network of size N [12, 14, 32] , since if the SIS dynamics cannot activate hubs in a network, SIRS dynamics cannot either, due to the suppressing effect of immunity. Assuming a scaling λ SIS c (N ) ∼ k −μ max where μ = 1/2 for the QMF theory [11] , this SIS-like behavior should be observed for network sizes N N c ≡ [βϑ(α,γ )] (γ −2)/μ , crossing over to a constant threshold for N N c . Numeric thresholds for γ > 3 are shown in Fig. 4 . As we can see, for sufficiently small α (up to 1 for γ = 4), we can observe a constant threshold for large N . For larger α values, the trend is still decreasing, being the constant plateau located on system sizes larger than those available to our computer resources.

These results presented so far have been checked on synthetic uncorrelated networks. They can however be extended to real correlated networks, characterized by conditional probability P (k |k) with a nontrivial dependence on k [28] . Focusing on the SIRS model, in Figs. 5(a) and 5(b) we present numerical simulations on two SF real networks. We consider in particular the location-based social network Gowalla [33] and the product copurchasing network in the Amazon website [34] , possessing degree exponents smaller and larger than 3, respectively; Fig. 5 (c). According to QMF theory, the thresholds for these networks are equal to the inverse of the largest eigenvalue of their adjacency matrix. By means of a numerical diagonalization, we obtain the values λ QMF,Gowalla c = 0.0059 and λ QMF,Amazon c = 0.042. Our simulations show, in the case of the Gowalla network, with a degree exponent γ 2.4 < 3, that numerically estimated thresholds are essentially independent of α and very close to the QMF prediction. This behavior is consistent with the theoretical expectation of a hub activated dynamics, to be observed in the regime γ < 3; see Fig. 5(a) . On the other hand, for the Amazon network, with degree exponent γ ≈ 3.5 > 3, we observe effective thresholds that diminish with increasing α, approaching the QMF prediction for α → ∞. This behavior is again in agreement with the prediction for the SIRS model in SF networks with γ > 3, that indicates a finite threshold for small α values, opposite to the QMF prediction of threshold independence.

The determination of the properties of the epidemic transition in models of disease propagation in highly heterogeneous networks is a crucial topic in network science, to which a large research effort has been recently devoted. Among others, one of the main questions that remains to be answered in this field is what are the conditions under which a given epidemic model leads to a vanishing or a finite threshold, and how the properties of the epidemic transition can be best described from a theoretical point of view.

In the present paper, building on an extension of the theory of Ref. [14] , we have proposed a general criterion to discern the nature of thresholds in epidemic models. The criterion is based on the comparison of the time scales of hub recovery (lifespan) and hub reinfection. When the lifespan is larger than the infection time, dynamics is triggered by a hub activation process, akin to the SIS dynamics: Hubs survive for very long times, and are able to reinfect each other, in such a way as to establish a long-lived endemic state. This hub activation scenario leads to a vanishing threshold when the lifespan is diverging faster than the reinfection time in the thermodynamic limit. In this case, QMF theories are expected to be qualitatively correct. The reason underlying the effectiveness of QMF theories lies in the fact that they take into account the full topological structure of the network, and are dominated by the effects of the largest hubs. On the other hand, for a lifespan smaller than the infection time scale, hub activation cannot be sustained and possible epidemic phase transitions should be the result of a collective activation process, leading to a standard phase transition at a finite threshold, as in the case of the CP. In this second scenario, HMF theories should be qualitatively correct, due to the fact that they work on the annealed network approximation, in which every node can interact with every other with a degree dependent probability [35] . To check the validity of the criterion, we have investigated a generic epidemic model with spontaneous recovering, waning immunity, and edge degree dependent infection rates on scalefree networks, for which we can compute analytic expressions for the hub recovery and infection time scales. The model has as particular cases the fundamental epidemic models, as the SIS, SIRS, and CP as well as more complex ones as the generalized SIS model of Ref. [23] , which we have considered. After exemplifying our framework with the known cases of the SIS and CP models, we present an extended discussion of the SIRS model, an extension of the SIS model with waning immunity. While previous analytic approaches (HMF and QMF theories) predict for the SIRS model the same behavior as the SIS model, the main result from our criterion is that we are able to show that, instead, the effect of even a small amount of waning immunity is able to restore a finite threshold (albeit affected by possible strong finite-size effects) in scale-free networks with degree exponent γ > 3, at odds with the QMF theory valid for SIS in this regime, and in agreement with HMF theory. Our predictions are corroborated by means of numerical simulation on synthetic uncorrelated scale-free networks, as well as on real correlated networks.

The proposed criterion represents a step forward in our understanding of the properties of the epidemic transition in epidemic modeling, and thus opens the path to study more general and realistic models. In this sense, its application to more complex models is straightforward In the Karsai, Juhász, and Iglói (KJI) model [23] , an edge transmits the infection from a vertex j to vertex i at a weighted rate λ ij = λA ij /(k i k j ) θ , where θ is a control parameter. 1 The HMF theory for the KJI model is set in terms of the probability I k that a node of degree k is infected, while it is susceptible with probability 1 − I k . The rate equation for this quantity can be simply written as [23, 35, 36] dI k dt 1 A constant factor in the original definition was absorbed in λ.

where P (k |k) is the probability that an edge from a node of degree k points to a node of degree k [24] . The threshold is obtained by linearizing Eq. (A1) around the fixed point I k = 0, which yields for uncorrelated networks with P (k |k) = k P (k )/ k [28] 

with a Jacobian

The absorbing state I k = 0 loses stability when the largest eigenvalue of L kk is null. We thus obtain a threshold for the active state with the form

As we see from this equation, θ = 0 leads to the epidemic threshold of the SIS model, depending on γ , while θ = 1/2 leads to the threshold of the CP model, independent of the network structure. For general values of θ , a finite HMF threshold is expected for γ > 3 − 2θ , while it is null for γ < 3 − 2θ .

From the point of view of QMF theory, based on the microscopic probability I i that node i is infected, the relevant rate equation can be written as [2] dI i dt

where A ij is the adjacency matrix [2] with value A ij = 1 if nodes i and j are connected, and zero otherwise. After linearization, stability analysis leads to a threshold inversely proportional to the largest eigenvalue D m of the matrix

No general analytical expression is available for the largest eigenvalue of this matrix, so we have proceeded to determine it numerically in SF networks generated using the uncorrelated configuration model (UCM) [29] ; see Fig. 6 . We find that D m ∼ m /k θ max for θ < 1/2, where m is the largest eigenvalue of the adjacency matrix A ij , and a constant for θ > 1/2. For γ > 3, since m ∼ √ k max [18] , we have

for θ < 1/2 and D m ∼ const for θ 1/2. The behavior of the largest eigenvalue in this case has strong finite-size effects close to θ = 1/2. These size effects can be observed in the crossover from a flat region to the scaling regime k 1/2−θ max for θ < 1/2, a crossover that takes place at larger values of k max when θ approaches 1/2.

These observations indicate that, for θ < 1/2, a zero threshold is obtained in the thermodynamic limit, independently of γ , while a finite threshold should occur for θ > 1/2.

In the HMF theory, the densities of infected, recovered, and susceptible vertices of degree k are represented by I k , R k , and S k , respectively, and obey the normalization condition [29] . The results were computed for five independent networks for γ = 3.5 and 1 for γ = 2.7 (largest degree fluctuates little). Sizes of N = 10 3 , 3 × 10 3 , 10 4 , 3 × 10 4 , 10 5 , 3 × 10 5 , 10 6 , 3 × 10 6 , 10 7 , 3 × 10 7 , and 10 8 were used. In the bottom panel, solid lines are power laws k 1/2−θ max . In the top panel, solid lines are proportional to m /k θ max , with m being the numerically estimated largest eigenvalue of the adjacency matrix A ij for θ < 1/2. I k + R k + S k = 1. The HMF dynamic equations, setting β = 1, are given by [22, 35, 36] 

and

To determine the threshold where an active state becomes stable, we perform a linear stability analysis around the fixed point I k = R k = 0, corresponding to the absorbing state. Since we are interested in long times, a quasistatic approximation [37] dR k dt ≈ 0 is used to obtain I k = αR k , which is inserted in Eq. (B1) to result in a linearized equation with Jacobian

The absorbing state loses stability when the largest eigenvalue of L kk is null. Thus, for uncorrelated networks with P (k |k) = k P (k )/ k , we easily obtain that the infected state is stable for [22] λ > λ HMF

In the QMF theory, the process is defined in terms of the probabilities that a vertex i is infected, I i , recovered, R i , or susceptible, S i , which fulfill the equations

and

where A ij is the adjacency matrix [2] , and we consider the normalization condition

Applying a quasistatic approximation to Eqs. (B5) and (B6), we obtain the linearized equation

with the Jacobian L ij = −δ ij + λA ij , implying that the threshold is given by [38] λ QMF

where m is the largest eigenvalue of the adjacency matrix.

SIRS simulations were implemented for β = 1 adapting the simulation scheme of Refs. [12, 32] : At each time step, the number of infected nodes N i , the number of edges emanating from them N k , and the number of recovered vertices N r , are computed and time is incremented by dt = 1/(N i + λN k + αN r ). With probability N i /(N i + λN k + αN r ) one infected node is selected at random and becomes recovered. With probability αN r /(N i + λN k + αN r ), a recovered vertex is selected and turned to susceptible. Finally, with probability λN k /(N i + λN k + αN r ), an infection attempt is performed in two steps: (i) An infected vertex j is selected with probability proportional to its degree. (ii) A nearest neighbor of j is selected with equal chance and, if susceptible, is infected. If the chosen neighbor is infected or recovered nothing happens and the simulation runs to the next time step. The numbers of infected and recovered nodes and links emanating from the former are updated accordingly, and the whole process is iterated.

KJI simulations were performed generalizing the previous algorithm as follows. For each node of the network we calculate the weight

proportional to the total infection rate transmitted by all edges of i. Then, at each time step, the number of infected nodes N i and the sum of the weights w i over all infected nodes S w are computed and time is incremented by dt = 1/(N i + λS w ). With probability N i /(N i + λS w ) one infected node is selected at random and becomes susceptible. With probability λS w /(N i + λS w ), an infection attempt is performed in two steps: (i) An infected vertex i is selected with probability proportional to its weight w i . (ii) A nearest neighbor of i, namely j , is selected with probability proportional to k −θ j and, if susceptible, it is infected.

The simulations were performed using the quasistationary (QS) method [31, 39] which permits one to overcome the difficulties intrinsic in the simulations of finite systems with absorbing states. In the QS method, every time the system visits an absorbing state it jumps to an active configuration previously visited during the simulation. This task is achieved building and constantly updating a list containing M = 70 configurations. The update is done by randomly picking up a stored configuration and replacing it by the current one with probability p r t. We fixed p r 10 −2 since no dependence on this parameter was detected for a wide range of simulation parameters. After a relaxation time t r , averages are computed over a time t av . Typically, a QS state is reached at times t 10 4 for QS simulations of dynamical processes on complex networks. Therefore, t r = 10 5 was used in all simulations. On the other hand, averaging times from 10 6 to 10 8 were used, the larger the average time the smaller the infection rate.

During the averaging time, the QS probabilityP (n) that the system has n infected vertices is computed. All stationary quantities of interest can be derived fromP (n). Here, we will investigate the density of infected vertices ρ = n nP (n)/N, the lifespan τ = 1/P (1), and the susceptibility defined as χ = N ( ρ 2 − ρ 2 )/ ρ [12] . This susceptibility has a diverging peak at the transition to an absorbing state on complex networks [12, 21, 40] and has been successfully used to determine the thresholds for epidemic models [12, 38, 41, 42] .

Simulations were done on SF networks with N vertices and degree distribution P (k) ∼ k −γ generated with the uncorrelated configuration model (UCM) [29] with minimum degree k 0 = 3 and structural upper cutoff k max = N 1/2 , which guarantees absence of degree correlations in the networks generated, that are, therefore, suitable for comparisons with the HMF theory where this simplification was adopted. Averages were computed using more than 20 different network samples.

The determination of the threshold, estimated as the peak of susceptibility, is shown in Fig. 7 .

Networks: An Introduction

Networks, Crowds, and Markets: Reasoning About a Highly Connected World

Infectious Diseases in Humans

Stochastic Processes and their Applications

Proc. Natl. Acad. Sci. USA

Handbook of Mathematical Functions

Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Dynamical Processes on Complex Networks