Second-order mean-field susceptible-infected-susceptible epidemic threshold

Susceptible-infected-susceptible process on Erdős-Rényi graphs: Determining the infected fraction

There are many methods to estimate the quasistationary infected fraction of the SIS process on (random) graphs. A challenge is to adequately incorporate correlations, which is especially important in sparse graphs. Methods typically are either significantly biased in sparse graphs, or computationally very demanding already for small network sizes. The former applies to heterogeneous mean field and to the N-intertwined mean field approximation, the latter to most higher order approximations. In this paper we introduce a method to determine the infected fraction in sparse graphs, which we test on Erdős-Rényi graphs. Our method is based on degree pairs, does take into account correlations, and gives accurate estimates. At the same time, computations are very feasible and can easily be done even for large networks.

The Determining Role of Covariances in Large Networks of Stochastic Neurons

Biological neural networks are notoriously hard to model due to their stochastic behavior and high dimensionality. We tackle this problem by constructing a dynamical model of both the expectations and covariances of the fractions of active and refractory neurons in the network's populations. We do so by describing the evolution of the states of individual neurons with a continuous-time Markov chain, from which we formally derive a low-dimensional dynamical system. This is done by solving a moment closure problem in a way that is compatible with the nonlinearity and boundedness of the activation function. Our dynamical system captures the behavior of the high-dimensional stochastic model even in cases where the mean-field approximation fails to do so. Taking into account the second-order moments modifies the solutions that would be obtained with the mean-field approximation and can lead to the appearance or disappearance of fixed points and limit cycles. We moreover perform numerical experiments where the mean-field approximation leads to periodically oscillating solutions, while the solutions of the second-order model can be interpreted as an average taken over many realizations of the stochastic model. Altogether, our results highlight the importance of including higher moments when studying stochastic networks and deepen our understanding of correlated neuronal activity.

Transition from time-variant to static networks: Timescale separation in N-intertwined mean-field approximation of susceptible-infectious-susceptible epidemics

We extend the N-intertwined mean-field approximation (NIMFA) for the susceptible-infectious-susceptible (SIS) epidemiological process to time-varying networks. Processes on time-varying networks are often analyzed under the assumption that the process and network evolution happen on different timescales. This approximation is called timescale separation. We investigate timescale separation between disease spreading and topology updates of the network. We introduce the transition times [under T]̲(r) and T[over ¯](r) as the boundaries between the intermediate regime and the annealed (fast changing network) and quenched (static network) regimes, respectively, for a fixed accuracy tolerance r. By analyzing the convergence of static NIMFA processes, we analytically derive upper and lower bounds for T[over ¯](r). Our results provide insights and bounds on the time of convergence to the steady state of the static NIMFA SIS process. We show that, under our assumptions, the upper-transition time T[over ¯](r) is almost entirely determined by the basic reproduction number R_{0} of the network. The value of the upper-transition time T[over ¯](r) around the epidemic threshold is large, which agrees with the current understanding that some real-world epidemics cannot be approximated with the aforementioned timescale separation.

Exact solutions and bounds for network SIR and SEIR models using a rooted-tree approximation

In this paper, we develop a new node-based approximate model to describe contagion dynamics on networks. We prove that our approximate model is exact for Markovian SIR (susceptible-infectious-recovered) and SEIR (susceptible-exposed-infectious-recovered) dynamics on tree graphs with a single source of infection, and that the model otherwise gives upper bounds on the probabilities of each node being susceptible. Our analysis of SEIR contagion dynamics is general to SEIR models with arbitrarily many classes of exposed/latent state. In all cases of a tree graph with a single source of infection, our approach yields a system of linear differential equations that exactly describes the evolution of node-state probabilities; we use this to state explicit closed-form solutions for an SIR model on a tree. For more general networks, our approach yields a cooperative system of differential equations that can be used to bound the true solution.

Endemic state equivalence between non-Markovian SEIS and Markovian SIS model in complex networks

In the light of several major epidemic events that emerged in the past two decades, and emphasized by the COVID-19 pandemics, the non-Markovian spreading models occurring on complex networks gained significant attention from the scientific community. Following this interest, in this article, we explore the relations that exist between the mean-field approximated non-Markovian SEIS (Susceptible-Exposed-Infectious-Susceptible) and the classical Markovian SIS, as basic reoccurring virus spreading models in complex networks. We investigate the similarities and seek for equivalences both for the discrete-time and the continuous-time forms. First, we formally introduce the continuous-time non-Markovian SEIS model, and derive the epidemic threshold in a strict mathematical procedure. Then we present the main result of the paper that, providing certain relations between process parameters hold, the stationary-state solutions of the status probabilities in the non-Markovian SEIS may be found from the stationary state probabilities of the Markovian SIS model. This result has a two-fold significance. First, it simplifies the computational complexity of the non-Markovian model in practical applications, where only the stationary distributions of the state probabilities are required. Next, it defines the epidemic threshold of the non-Markovian SEIS model, without the necessity of a thrall mathematical analysis. We present this result both in analytical form, and confirm the result through numerical simulations. Furthermore, as of secondary importance, in an analytical procedure we show that each Markovian SIS may be represented as non-Markovian SEIS model.

Game-Theoretic Frameworks for Epidemic Spreading and Human Decision-Making: A Review

This review presents and reviews various solved and open problems in developing, analyzing, and mitigating epidemic spreading processes under human decision-making. We provide a review of a range of epidemic models and explain the pros and cons of different epidemic models. We exhibit the art of coupling between epidemic models and decision models in the existing literature. More specifically, we provide answers to fundamental questions in human decision-making amid epidemics, including what interventions to take to combat the disease, who are decision-makers, and when and how to take interventions, and how to make interventions. Among many decision models, game-theoretic models have become increasingly crucial in modeling human responses or behavior amid epidemics in the last decade. In this review, we motivate the game-theoretic approach to human decision-making amid epidemics. This review provides an overview of the existing literature by developing a multi-dimensional taxonomy, which categorizes existing literature based on multiple dimensions, including (1) types of games, such as differential games, stochastic games, evolutionary games, and static games; (2) types of interventions, such as social distancing, vaccination, quarantine, and taking antidotes; (3) the types of decision-makers, such as individuals, adversaries, and central authorities at different hierarchical levels. A fine-grained dynamic game framework is proposed to capture the essence of game-theoretic decision-making amid epidemics. We showcase three representative frameworks with unique ways of integrating game-theoretic decision-making into the epidemic models from a vast body of literature. Each of the three frameworks has their unique way of modeling and analyzing and develops results from different angles. In the end, we identify several main open problems and research gaps left to be addressed and filled.

Dynamics of epidemics from cavity master equations: Susceptible-infectious-susceptible models

We apply the recently introduced cavity master equation (CME) to epidemic models and compare it to previously known approaches. We show that CME seems to be the formal way to derive (and correct) dynamic message passing (rDMP) equations that were previously introduced in an intuitive ad hoc manner. CME outperforms rDMP in all cases studied. Both approximations are nonbacktracking and this causes CME and rDMP to fail when the ecochamber mechanism is relevant, as in loopless topologies or scale free networks. However, we studied several random regular graphs and Erdős-Rényi graphs, where CME outperforms individual based mean field and a type of pair based mean field, although it is less precise than pair quenched mean field. We derive analytical results for endemic thresholds and compare them across different approximations.

From random point processes to hierarchical cavity master equations for stochastic dynamics of disordered systems in random graphs: Ising models and epidemics

We start from the theory of random point processes to derive n-point coupled master equations describing the continuous dynamics of discrete variables in random graphs. These equations constitute a hierarchical set of approximations that generalize and improve the cavity master equation (CME), a recently obtained closure for the usual master equation representing the dynamics. Our derivation clarifies some of the hypotheses and approximations that originally led to the CME, considered now as the first order of a more general technique. We tested the scheme in the dynamics of three models defined over diluted graphs: the Ising ferromagnet, the Viana-Bray spin-glass, and the susceptible-infectious-susceptible model for epidemics. In the first two, the equations perform similarly to the best-known approaches in literature. In the latter, they outperform the well-known pair quenched mean-field approximation.

Exact Maximal Reduction Of Stochastic Reaction Networks By Species Lumping

MOTIVATION

Stochastic reaction networks are a widespread model to describe biological systems where the presence of noise is relevant, such as in cell regulatory processes. Unfortunately, in all but simplest models the resulting discrete state-space representation hinders analytical tractability and makes numerical simulations expensive. Reduction methods can lower complexity by computing model projections that preserve dynamics of interest to the user.

RESULTS

We present an exact lumping method for stochastic reaction networks with mass-action kinetics. It hinges on an equivalence relation between the species, resulting in a reduced network where the dynamics of each macro-species is stochastically equivalent to the sum of the original species in each equivalence class, for any choice of the initial state of the system. Furthermore, by an appropriate encoding of kinetic parameters as additional species, the method can establish equivalences that do not depend on specific values of the parameters. The method is supported by an efficient algorithm to compute the largest species equivalence, thus the maximal lumping. The effectiveness and scalability of our lumping technique, as well as the physical interpretability of resulting reductions, is demonstrated in several models of signaling pathways and epidemic processes on complex networks.

AVAILABILITY

The algorithms for species equivalence have been implemented in the software tool ERODE, freely available for download from https://www.erode.eu.

An overview of epidemic models with phase transitions to absorbing states running on top of complex networks

Dynamical systems running on the top of complex networks have been extensively investigated for decades. But this topic still remains among the most relevant issues in complex network theory due to its range of applicability. The contact process (CP) and the susceptible-infected-susceptible (SIS) model are used quite often to describe epidemic dynamics. Despite their simplicity, these models are robust to predict the kernel of real situations. In this work, we review concisely both processes that are well-known and very applied examples of models that exhibit absorbing-state phase transitions. In the epidemic scenario, individuals can be infected or susceptible. A phase transition between a disease-free (absorbing) state and an active stationary phase (where a fraction of the population is infected) are separated by an epidemic threshold. For the SIS model, the central issue is to determine this epidemic threshold on heterogeneous networks. For the CP model, the main interest is to relate critical exponents with statistical properties of the network.

Information Spread across Social Network Services with Non-Responsiveness of Individual Users

This paper investigates the dynamics of information spread across social network services (SNSs) such as Twitter using the susceptible-infected-recovered (SIR) model. In the analysis, the non-responsiveness of individual users is taken into account; a user probabilistically spreads the received information, where not spreading (not responding) is equivalent to that the received information is not noticed. In most practical applications, an exact analytic solution is not available for the SIR model, so previous studies have largely been based on the assumption that the probability of an SNS user having the target information is independent of whether or not its neighbors have that information. In contrast, we propose a different approach based on a “strong correlation assumption”, in which the probability of an SNS user having the target information is strongly correlated with whether its neighboring users have that information. To account for the non-responsiveness of individual users, we also propose the “representative-response-based analysis”, in which some information spreading patterns are first obtained assuming representative response patterns of each user and then the results are averaged. Through simulation experiments, we show that the combination of this strong correlation assumption and the representative-response-based analysis makes it possible to analyze the spread of information with far greater accuracy than the traditional approach.

Norm violation versus punishment risk in a social model of corruption

We analyze the onset of social-norm-violating behaviors when social punishment is present. To this aim, a compartmental model is introduced to illustrate the flows among the three possible states: honest, corrupt, and ostracism. With this simple model we attempt to capture some essential ingredients such as the contagion of corrupt behaviors to honest agents, the delation of corrupt individuals by honest ones, and the warning to wrongdoers (fear like that triggers the conversion of corrupt people into honesty). In nonequilibrium statistical physics terms, the former dynamics can be viewed as a non-Hamiltonian kinetic spin-1 Ising model. After developing in full detail its mean-field theory and comparing its predictions with simulations made on regular networks, we derive the conditions for the emergence of corrupt behaviors and, more importantly, illustrate the key role of the warning-to-wrongdoers mechanism in the latter.

Hamiltonian dynamics of the SIS epidemic model with stochastic fluctuations

Empirical records of epidemics reveal that fluctuations are important factors for the spread and prevalence of infectious diseases. The exact manner in which fluctuations affect spreading dynamics remains poorly known. Recent analytical and numerical studies have demonstrated that improved differential equations for mean and variance of infected individuals reproduce certain regimes of the SIS epidemic model. Here, we show they form a dynamical system that follows Hamilton’s equations, which allow us to understand the role of fluctuations and their effects on epidemics. Our findings show the Hamiltonian is a constant of motion for large population sizes. For small populations, finite size effects break the temporal symmetry and induce a power-law decay of the Hamiltonian near the outbreak onset, with a parameter-free exponent. Away from the onset, the Hamiltonian decays exponentially according to a constant relaxation time, which we propose as a metric when fluctuations cannot be neglected.

Spectral properties and the accuracy of mean-field approaches for epidemics on correlated power-law networks

We present a comparison between stochastic simulations and mean-field theories for the epidemic threshold of the susceptible-infected-susceptible model on correlated networks (both assortative and disassortative) with a power-law degree distribution P(k)∼k−γ. We confirm the vanishing of the threshold regardless of the correlation pattern and the degree exponent γ. Thresholds determined numerically are compared with quenched mean-field (QMF) and pair quenched mean-field (PQMF) theories. Correlations do not change the overall picture: The QMF and PQMF theories provide estimates that are asymptotically correct for large sizes for γ<5/2, while they only capture the vanishing of the threshold for γ>5/2, failing to reproduce quantitatively how this occurs. For a given size, PQMF theory is more accurate. We relate the variations in the accuracy of QMF and PQMF predictions with changes in the spectral properties (spectral gap and localization) of standard and modified adjacency matrices, which rule the epidemic prevalence near the transition point, depending on the theoretical framework. We also show that, for γ<5/2, while QMF theory provides an estimate of the epidemic threshold that is asymptotically exact, it fails to reproduce the singularity of the prevalence around the transition.

Effective approach to epidemic containment using link equations in complex networks

Epidemic containment is a major concern when confronting large-scale infections in complex networks. Many studies have been devoted to analytically understand how to restructure the network to minimize the impact of major outbreaks of infections at large scale. In many cases, the strategies are based on isolating certain nodes, while less attention has been paid to interventions on the links. In epidemic spreading, links inform about the probability of carrying the contagion of the disease from infected to susceptible individuals. Note that these states depend on the full structure of the network, and its determination is not straightforward from the knowledge of nodes' states. Here, we confront this challenge and propose a set of discrete-time governing equations that can be closed and analyzed, assessing the contribution of links to spreading processes in complex networks. Our approach allows a scheme for the containment of epidemics based on deactivating the most important links in transmitting the disease. The model is validated in synthetic and real networks, yielding an accurate determination of epidemic incidence and critical thresholds. Epidemic containment based on link deactivation promises to be an effective tool to maintain functionality of networks while controlling the spread of diseases, such as disease spread through air transportation networks.

Lumping of degree-based mean-field and pair-approximation equations for multistate contact processes

Contact processes form a large and highly interesting class of dynamic processes on networks, including epidemic and information-spreading networks. While devising stochastic models of such processes is relatively easy, analyzing them is very challenging from a computational point of view, particularly for large networks appearing in real applications. One strategy to reduce the complexity of their analysis is to rely on approximations, often in terms of a set of differential equations capturing the evolution of a random node, distinguishing nodes with different topological contexts (i.e., different degrees of different neighborhoods), such as degree-based mean-field (DBMF), approximate-master-equation (AME), or pair-approximation (PA) approaches. The number of differential equations so obtained is typically proportional to the maximum degree k_{max} of the network, which is much smaller than the size of the master equation of the underlying stochastic model, yet numerically solving these equations can still be problematic for large k_{max}. In this paper, we consider AME and PA, extended to cope with multiple local states, and we provide an aggregation procedure that clusters together nodes having similar degrees, treating those in the same cluster as indistinguishable, thus reducing the number of equations while preserving an accurate description of global observables of interest. We also provide an automatic way to build such equations and to identify a small number of degree clusters that give accurate results. The method is tested on several case studies, where it shows a high level of compression and a reduction of computational time of several orders of magnitude for large networks, with minimal loss in accuracy.

Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks

We present a degree-based theoretical framework to study the susceptible-infected-susceptible (SIS) dynamics on time-varying (rewired) configuration model networks. Using this framework on a given degree distribution, we provide a detailed analysis of the stationary state using the rewiring rate to explore the whole range of the time variation of the structure relative to that of the SIS process. This analysis is suitable for the characterization of the phase transition and leads to three main contributions: (1) We obtain a self-consistent expression for the absorbing-state threshold, able to capture both collective and hub activation. (2) We recover the predictions of a number of existing approaches as limiting cases of our analysis, providing thereby a unifying point of view for the SIS dynamics on random networks. (3) We obtain bounds for the critical exponents of a number of quantities in the stationary state. This allows us to reinterpret the concept of hub-dominated phase transition. Within our framework, it appears as a heterogeneous critical phenomenon: observables for different degree classes have a different scaling with the infection rate. This phenomenon is followed by the successive activation of the degree classes beyond the epidemic threshold.

Unified mean-field framework for susceptible-infected-susceptible epidemics on networks, based on graph partitioning and the isoperimetric inequality

We propose an approximation framework that unifies and generalizes a number of existing mean-field approximation methods for the susceptible-infected-susceptible (SIS) epidemic model on complex networks. We derive the framework, which we call the unified mean-field framework (UMFF), as a set of approximations of the exact Markovian SIS equations. Our main novelty is that we describe the mean-field approximations from the perspective of the isoperimetric problem, which results in bounds on the UMFF approximation error. These new bounds provide insight in the accuracy of existing mean-field methods, such as the N-intertwined mean-field approximation and heterogeneous mean-field method, which are contained by UMFF. Additionally, the isoperimetric inequality relates the UMFF approximation accuracy to the regularity notions of Szemerédi's regularity lemma.

Optimal allocation of resources for suppressing epidemic spreading on networks

Efficient allocation of limited medical resources is crucial for controlling epidemic spreading on networks. Based on the susceptible-infected-susceptible model, we solve the optimization problem of how best to allocate the limited resources so as to minimize prevalence, providing that the curing rate of each node is positively correlated to its medical resource. By quenched mean-field theory and heterogeneous mean-field (HMF) theory, we prove that an epidemic outbreak will be suppressed to the greatest extent if the curing rate of each node is directly proportional to its degree, under which the effective infection rate λ has a maximal threshold λ_{c}^{opt}=1/〈k〉, where 〈k〉 is the average degree of the underlying network. For a weak infection region (λ≳λ_{c}^{opt}), we combine perturbation theory with the Lagrange multiplier method (LMM) to derive the analytical expression of optimal allocation of the curing rates and the corresponding minimized prevalence. For a general infection region (λ>λ_{c}^{opt}), the high-dimensional optimization problem is converted into numerically solving low-dimensional nonlinear equations by the HMF theory and LMM. Counterintuitively, in the strong infection region the low-degree nodes should be allocated more medical resources than the high-degree nodes to minimize prevalence. Finally, we use simulated annealing to validate the theoretical results.

Efficient method for comprehensive computation of agent-level epidemic dissemination in networks

Susceptible-infected (SI) and susceptible-infected-susceptible (SIS) are simple agent-based models often employed in epidemic studies. Both models describe the time evolution of infectious diseases in networks whose vertices are either susceptible (S) or infected (I) agents. Precise estimation for disease spreading is one of the major goals in epidemic studies but often restricted to heavy numerical simulations. Analytic methods using operatorial content are subject to the asymmetric eigenvalue problem, limiting the use of perturbative methods. Numerical methods are limited to small populations, since the vector space increases exponentially with population size N. Here, we propose the use of the squared norm of the probability vector to obtain an algebraic equation, which permits the evaluation of stationary states in Markov processes. The equation requires the eigenvalues of symmetrized time generators and takes full advantage of symmetries, reducing the time evolution to an O(N) sparse problem. The calculation of eigenvalues employs quantum many-body techniques, while the standard perturbation theory accounts for small modifications to the network topology.

Approximate formula and bounds for the time-varying susceptible-infected-susceptible prevalence in networks

Based on a recent exact differential equation, the time dependence of the SIS prevalence, the average fraction of infected nodes, in any graph is first studied and then upper and lower bounded by an explicit analytic function of time. That new approximate "tanh formula" obeys a Riccati differential equation and bears resemblance to the classical expression in epidemiology of Kermack and McKendrick [Proc. R. Soc. London A 115, 700 (1927)1364-502110.1098/rspa.1927.0118] but enhanced with graph specific properties, such as the algebraic connectivity, the second smallest eigenvalue of the Laplacian of the graph. We further revisit the challenge of finding tight upper bounds for the SIS (and SIR) epidemic threshold for all graphs. We propose two new upper bounds and show the importance of the variance of the number of infected nodes. Finally, a formula for the epidemic threshold in the cycle (or ring graph) is presented.

On the Adjacency Matrix of RyR2 Cluster Structures

In the heart, electrical stimulation of cardiac myocytes increases the open probability of sarcolemmal voltage-sensitive Ca2+ channels and flux of Ca2+ into the cells. This increases Ca2+ binding to ligand-gated channels known as ryanodine receptors (RyR2). Their openings cause cell-wide release of Ca2+, which in turn causes muscle contraction and the generation of the mechanical force required to pump blood. In resting myocytes, RyR2s can also open spontaneously giving rise to spatially-confined Ca2+ release events known as "sparks." RyR2s are organized in a lattice to form clusters in the junctional sarcoplasmic reticulum membrane. Our recent work has shown that the spatial arrangement of RyR2s within clusters strongly influences the frequency of Ca2+ sparks. We showed that the probability of a Ca2+ spark occurring when a single RyR2 in the cluster opens spontaneously can be predicted from the precise spatial arrangements of the RyR2s. Thus, "function" follows from "structure." This probability is related to the maximum eigenvalue (λ1) of the adjacency matrix of the RyR2 cluster lattice. In this work, we develop a theoretical framework for understanding this relationship. We present a stochastic contact network model of the Ca2+ spark initiation process. We show that λ1 determines a stability threshold for the formation of Ca2+ sparks in terms of the RyR2 gating transition rates. We recapitulate these results by applying the model to realistic RyR2 cluster structures informed by super-resolution stimulated emission depletion (STED) microscopy. Eigendecomposition of the linearized mean-field contact network model reveals functional subdomains within RyR2 clusters with distinct sensitivities to Ca2+. This work provides novel perspectives on the cardiac Ca2+ release process and a general method for inferring the functional properties of transmembrane receptor clusters from their structure.

Survival time of the susceptible-infected-susceptible infection process on a graph

The survival time T is the longest time that a virus, a meme, or a failure can propagate in a network. Using the hitting time of the absorbing state in an uniformized embedded Markov chain of the continuous-time susceptible-infected-susceptible (SIS) Markov process, we derive an exact expression for the average survival time E[T] of a virus in the complete graph K_{N} and the star graph K_{1,N-1}. By using the survival time, instead of the average fraction of infected nodes, we propose a new method to approximate the SIS epidemic threshold τ_{c} that, at least for K_{N} and K_{1,N-1}, correctly scales with the number of nodes N and that is superior to the epidemic threshold τ_{c}^{(1)}=1/λ_{1} of the N-intertwined mean-field approximation, where λ_{1} is the spectral radius of the adjacency matrix of the graph G. Although this new approximation of the epidemic threshold offers a more intuitive understanding of the SIS process, it remains difficult to compare outbreaks in different graph types. For example, the survival in an arbitrary graph seems upper bounded by the complete graph and lower bounded by the star graph as a function of the normalized effective infection rate τ/τ_{c}^{(1)}. However, when the average fraction of infected nodes is used as a basis for comparison, the virus will survive in the star graph longer than in any other graph, making the star graph the worst-case graph instead of the complete graph. Finally, in non-Markovian SIS, the distribution of the spreading attempts over the infectious period of a node influences the survival time, even if the expected number of spreading attempts during an infectious period (the non-Markovian equivalent of the effective infection rate) is kept constant. Both early and late infection attempts lead to shorter survival times. Interestingly, just as in Markovian SIS, the survival times appear to be exponentially distributed, regardless of the infection and curing time distributions.

Metapopulation persistence in random fragmented landscapes

Habitat destruction and land use change are making the world in which natural populations live increasingly fragmented, often leading to local extinctions. Although local populations might undergo extinction, a metapopulation may still be viable as long as patches of suitable habitat are connected by dispersal, so that empty patches can be recolonized. Thus far, metapopulations models have either taken a mean-field approach, or have modeled empirically-based, realistic landscapes. Here we show that an intermediate level of complexity between these two extremes is to consider random landscapes, in which the patches of suitable habitat are randomly arranged in an area (or volume). Using methods borrowed from the mathematics of Random Geometric Graphs and Euclidean Random Matrices, we derive a simple, analytic criterion for the persistence of the metapopulation in random fragmented landscapes. Our results show how the density of patches, the variability in their value, the shape of the dispersal kernel, and the dimensionality of the landscape all contribute to determining the fate of the metapopulation. Using this framework, we derive sufficient conditions for the population to be spatially localized, such that spatially confined clusters of patches act as a source of dispersal for the whole landscape. Finally, we show that a regular arrangement of the patches is always detrimental for persistence, compared to the random arrangement of the patches. Given the strong parallel between metapopulation models and contact processes, our results are also applicable to models of disease spread on spatial networks.

Like the hundreds of paintings of water lilies by Monet, any two landscapes in which a metapopulation dwells are different, as the size, shape and location of the patches of suitable habitat (the lilies), distributed over a inhospitable background (the water) vary among landscapes. Yet, as all the paintings depict the same pond in Giverny, different fragmented landscapes could have the same value to a metapopulation. Here we ask what are the key features we should measure to predict persistence of metapopulations inhabiting fragmented landscapes, and show that few quantities determine the fate of metapopulations—so that two very different-looking landscapes could lead to the same likelihood of persistence. We also show that regular arrangements of the patches in space are detrimental for persistence, and that the typical behavior of metapopulations close to extinction is to be mostly localized in a confined region of the landscape.

Accuracy criterion for the mean-field approximation in susceptible-infected-susceptible epidemics on networks

Mean-field approximations (MFAs) are frequently used in physics. When a process (such as an epidemic or a synchronization) on a network is approximated by MFA, a major hurdle is the determination of those graphs for which MFA is reasonably accurate. Here, we present an accuracy criterion for Markovian susceptible-infected-susceptible (SIS) epidemics on any network, based on the spectrum of the adjacency and SIS covariance matrix. We evaluate the MFA criterion for the complete and star graphs analytically, and numerically for connected Erdős-Rényi random graphs for small size N≤14. The accuracy of MFA increases with average degree and with N. Precise simulations (up to network sizes N=100) of the MFA accuracy criterion versus N for the complete graph, star, square lattice, and path graphs lead us to conjecture that the worst MFA accuracy decreases, for large N, proportionally to the inverse of the spectral radius of the adjacency matrix of the graph.

Multiple transitions of the susceptible-infected-susceptible epidemic model on complex networks

The epidemic threshold of the susceptible-infected-susceptible (SIS) dynamics on random networks having a power law degree distribution with exponent γ>3 has been investigated using different mean-field approaches, which predict different outcomes. We performed extensive simulations in the quasistationary state for a comparison with these mean-field theories. We observed concomitant multiple transitions in individual networks presenting large gaps in the degree distribution and the obtained multiple epidemic thresholds are well described by different mean-field theories. We observed that the transitions involving thresholds which vanish at the thermodynamic limit involve localized states, in which a vanishing fraction of the network effectively contributes to epidemic activity, whereas an endemic state, with a finite density of infected vertices, occurs at a finite threshold. The multiple transitions are related to the activations of distinct subdomains of the network, which are not directly connected.

Responsive immunization and intervention for infectious diseases in social networks

By using the microscopic Markov-chain approximation approach, we investigate the epidemic spreading and the responsive immunization in social networks. It is assumed that individual vaccination behavior depends on the local information of an epidemic. Our results suggest that the responsive immunization has negligible impact on the epidemic threshold and the critical value of initial epidemic outbreak, but it can effectively inhibit the outbreak of epidemic. We also analyze the influence of the intervention on the disease dynamics, where the vaccination is available only to those individuals whose number of neighbors is greater than a certain value. Simulation analysis implies that the intervention strategy can effectively reduce the vaccine use under the epidemic control.

Nodal infection in Markovian susceptible-infected-susceptible and susceptible-infected-removed epidemics on networks are non-negatively correlated

By invoking the famous Fortuin, Kasteleyn, and Ginibre (FKG) inequality, we prove the conjecture that the correlation of infection at the same time between any pair of nodes in a network cannot be negative for (exact) Markovian susceptible-infected-susceptible (SIS) and susceptible-infected-removed (SIR) epidemics on networks. The truth of the conjecture establishes that the N-intertwined mean-field approximation (NIMFA) upper bounds the infection probability in any graph so that network design based on NIMFA always leads to safe protections against malware spread. However, when the infection or/and curing are not Poisson processes, the infection correlation between two nodes can be negative.

Epidemic threshold and topological structure of susceptible-infectious-susceptible epidemics in adaptive networks

The interplay between disease dynamics on a network and the dynamics of the structure of that network characterizes many real-world systems of contacts. A continuous-time adaptive susceptible-infectious-susceptible (ASIS) model is introduced in order to investigate this interaction, where a susceptible node avoids infections by breaking its links to its infected neighbors while it enhances the connections with other susceptible nodes by creating links to them. When the initial topology of the network is a complete graph, an exact solution to the average metastable-state fraction of infected nodes is derived without resorting to any mean-field approximation. A linear scaling law of the epidemic threshold τ(c) as a function of the effective link-breaking rate ω is found. Furthermore, the bifurcation nature of the metastable fraction of infected nodes of the ASIS model is explained. The metastable-state topology shows high connectivity and low modularity in two regions of the τ,ω plane for any effective infection rate τ>τ(c): (i) a "strongly adaptive" region with very high ω and (ii) a "weakly adaptive" region with very low ω. These two regions are separated from the other half-open elliptical-like regions of low connectivity and high modularity in a contour-line-like way. Our results indicate that the adaptation of the topology in response to disease dynamics suppresses the infection, while it promotes the network evolution towards a topology that exhibits assortative mixing, modularity, and a binomial-like degree distribution.

Effect of the interconnected network structure on the epidemic threshold

Most real-world networks are not isolated. In order to function fully, they are interconnected with other networks, and this interconnection influences their dynamic processes. For example, when the spread of a disease involves two species, the dynamics of the spread within each species (the contact network) differs from that of the spread between the two species (the interconnected network). We model two generic interconnected networks using two adjacency matrices, A and B, in which A is a 2N×2N matrix that depicts the connectivity within each of two networks of size N, and B a 2N×2N matrix that depicts the interconnections between the two. Using an N-intertwined mean-field approximation, we determine that a critical susceptible-infected-susceptible (SIS) epidemic threshold in two interconnected networks is 1/λ(1)(A+αB), where the infection rate is β within each of the two individual networks and αβ in the interconnected links between the two networks and λ(1)(A+αB) is the largest eigenvalue of the matrix A+αB. In order to determine how the epidemic threshold is dependent upon the structure of interconnected networks, we analytically derive λ(1)(A+αB) using a perturbation approximation for small and large α, the lower and upper bound for any α as a function of the adjacency matrix of the two individual networks, and the interconnections between the two and their largest eigenvalues and eigenvectors. We verify these approximation and boundary values for λ(1)(A+αB) using numerical simulations, and determine how component network features affect λ(1)(A+αB). We note that, given two isolated networks G(1) and G(2) with principal eigenvectors x and y, respectively, λ(1)(A+αB) tends to be higher when nodes i and j with a higher eigenvector component product x(i)y(j) are interconnected. This finding suggests essential insights into ways of designing interconnected networks to be robust against epidemics.

Susceptible-infected-susceptible epidemics on networks with general infection and cure times

The classical, continuous-time susceptible-infected-susceptible (SIS) Markov epidemic model on an arbitrary network is extended to incorporate infection and curing or recovery times each characterized by a general distribution (rather than an exponential distribution as in Markov processes). This extension, called the generalized SIS (GSIS) model, is believed to have a much larger applicability to real-world epidemics (such as information spread in online social networks, real diseases, malware spread in computer networks, etc.) that likely do not feature exponential times. While the exact governing equations for the GSIS model are difficult to deduce due to their non-Markovian nature, accurate mean-field equations are derived that resemble our previous N-intertwined mean-field approximation (NIMFA) and so allow us to transfer the whole analytic machinery of the NIMFA to the GSIS model. In particular, we establish the criterion to compute the epidemic threshold in the GSIS model. Moreover, we show that the average number of infection attempts during a recovery time is the more natural key parameter, instead of the effective infection rate in the classical, continuous-time SIS Markov model. The relative simplicity of our mean-field results enables us to treat more general types of SIS epidemics, while offering an easier key parameter to measure the average activity of those general viral agents.

Non-Markovian infection spread dramatically alters the susceptible-infected-susceptible epidemic threshold in networks

Most studies on susceptible-infected-susceptible epidemics in networks implicitly assume Markovian behavior: the time to infect a direct neighbor is exponentially distributed. Much effort so far has been devoted to characterize and precisely compute the epidemic threshold in susceptible-infected-susceptible Markovian epidemics on networks. Here, we report the rather dramatic effect of a nonexponential infection time (while still assuming an exponential curing time) on the epidemic threshold by considering Weibullean infection times with the same mean, but different power exponent α. For three basic classes of graphs, the Erdős-Rényi random graph, scale-free graphs and lattices, the average steady-state fraction of infected nodes is simulated from which the epidemic threshold is deduced. For all graph classes, the epidemic threshold significantly increases with the power exponents α. Hence, real epidemics that violate the exponential or Markovian assumption can behave seriously differently than anticipated based on Markov theory.

Susceptible-infected-susceptible epidemics on the complete graph and the star graph: exact analysis

Since mean-field approximations for susceptible-infected-susceptible (SIS) epidemics do not always predict the correct scaling of the epidemic threshold of the SIS metastable regime, we propose two novel approaches: (a) an ε-SIS generalized model and (b) a modified SIS model that prevents the epidemic from dying out (i.e., without the complicating absorbing SIS state). Both adaptations of the SIS model feature a precisely defined steady state (that corresponds to the SIS metastable state) and allow an exact analysis in the complete and star graph consisting of a central node and N leaves. The N-intertwined mean-field approximation (NIMFA) is shown to be nearly exact for the complete graph but less accurate to predict the correct scaling of the epidemic threshold τ(c) in the star graph, which is found as τ(c)=ατ(c)((1)), where α=√[1/2 logN + 3/2 log logN] and where τ(c)((1))=1/√[N]<τ(c) is the first-order epidemic threshold for the star in NIMFA and equal to the inverse of the spectral radius of the star's adjacency matrix.

Epidemic thresholds of the susceptible-infected-susceptible model on networks: a comparison of numerical and theoretical results

Recent work has shown that different theoretical approaches to the dynamics of the susceptible-infected-susceptible (SIS) model for epidemics lead to qualitatively different estimates for the position of the epidemic threshold in networks. Here we present large-scale numerical simulations of the SIS dynamics on various types of networks, allowing the precise determination of the effective threshold for systems of finite size N. We compare quantitatively the numerical thresholds with theoretical predictions of the heterogeneous mean-field theory and of the quenched mean-field theory. We show that the latter is in general more accurate, scaling with N with the correct exponent, but often failing to capture the correct prefactor.

Susceptible-infected-susceptible model: a comparison of N-intertwined and heterogeneous mean-field approximations

We introduce the ε-susceptible-infected-susceptible (SIS) spreading model, which is taken as a benchmark for the comparison between the N-intertwined approximation and the Pastor-Satorras and Vespignani heterogeneous mean-field (HMF) approximation of the SIS model. The N-intertwined approximation, the HMF approximation, and the ε-SIS spreading model are compared for different graph types. We focus on the epidemic threshold and the steady-state fraction of infected nodes in networks with different degree distributions. Overall, the N-intertwined approximation is superior to the HMF approximation. The N-intertwined approximation is exactly the same as the HMF approximation in regular graphs. However, for some special graph types, such as the square lattice graph and the path graph, the two mean-field approximations are both very different from the ε-SIS spreading model.

Epidemics in networks with nodal self-infection and the epidemic threshold

Since the Susceptible-Infected-Susceptible (SIS) epidemic threshold is not precisely defined in spite of its practical importance, the classical SIS epidemic process has been generalized to the ε-SIS model, where a node possesses a self-infection rate ε, in addition to a link infection rate β and a curing rate δ. The exact Markov equations are derived, from which the steady state can be computed. The major advantage of the ε-SIS model is that its steady state is different from the absorbing (or overall-healthy state) and approximates, for a certain range of small ε > 0, the in reality observed phase transition, also called the "metastable" state, that is characterized by the epidemic threshold. The exact steady-state analysis for the complete graph illustrates the effect of small ε and the quality of the first-order mean-field approximation, the N-intertwined model, proposed earlier. Apart from duality principles, often used in the mathematical literature, we present an exact recursion relation for the Markov infinitesimal generator.