Relevance of backtracking paths in recurrent-state epidemic spreading on networks

Weighted-ensemble network simulations of the susceptible-infected-susceptible model of epidemics

The presence of erratic or unstable paths in standard kinetic Monte Carlo simulations significantly undermines the accurate simulation and sampling of transition pathways. While typically reliable methods, such as the Gillespie algorithm, are employed to simulate such paths, they encounter challenges in efficiently identifying rare events due to their sequential nature and reliance on exact Monte Carlo sampling. In contrast, the weighted-ensemble method effectively samples rare events and accelerates the exploration of complex reaction pathways by distributing computational resources among multiple replicas, where each replica is assigned a weight reflecting its importance, and evolves independently from the others. Here, we implement the highly efficient and robust weighted-ensemble method to model susceptible-infected-susceptible dynamics on large heterogeneous population networks, and explore the interplay between stochasticity and contact heterogeneity, which ultimately gives rise to disease clearance. Studying a wide variety of networks characterized by fat-tailed asymmetric degree distributions, we are able to compute the mean time to extinction and quasistationary distribution around it in previously inaccessible parameter regimes.

Spurious self-feedback of mean-field predictions inflates infection curves

The susceptible-infected-recovered (SIR) model and its variants form the foundation of our understanding of the spread of diseases. Here, each agent can be in one of three states (susceptible, infected, or recovered), and transitions between these states follow a stochastic process. The probability of an agent becoming infected depends on the number of its infected neighbors, hence all agents are correlated. The simplest mean-field theory of the same stochastic process, however, assumes that the agents are statistically independent. This leads to a self-feedback effect in the approximation: when an agent infects its neighbors, this infection may subsequently travel back to the original agent at a later time, leading to a self-infection of the agent which is not present in the underlying stochastic process. We here compute the first-order correction to the mean-field assumption from a systematic expansion, called dynamical TAP theory. This correction, which takes fluctuations up to second order in the interaction strength into account, cancels the self-feedback effect, leading to smaller infection rates. The correction significantly improves predictions compared to mean-field theory. In particular, it captures how sparsity dampens the spread of the disease: this indicates that reducing the number of contacts is more effective than predicted by mean-field models. We further apply the expansion to variants of the SIR model, such as the SIRS model, in which the immunity of an individual to the disease wanes over time. We find that up to the second order, the correction terms in the SIR and SIRS model are equivalent, meaning that fluctuations partially cancel the self-feedback effect even when self-feedback is in principle allowed.

Comparison of theoretical approaches for epidemic processes with waning immunity in complex networks

The role of waning immunity in basic epidemic models on networks has been undervalued while being noticeably fundamental for real epidemic outbreaks. One central question is which mean-field approach is more accurate in describing the epidemic dynamics. We tackled this problem considering the susceptible-infected-recovered-susceptible (SIRS) epidemic model on networks. Two pairwise mean-field theories, one based on recurrent dynamical message-passing (rDMP) theory and the other on the pair quenched mean-field (PQMF) theory, are compared with extensive stochastic simulations on large networks of different levels of heterogeneity. For waning immunity times longer than or comparable with the recovering time, rDMP outperforms PQMF theory on power-law networks with degree distribution P(k)∼k^{-γ}. In particular, for γ>3, the epidemic threshold observed in simulations is finite, in qualitative agreement with rDMP, while PQMF leads to an asymptotically null threshold. The critical epidemic prevalence for γ>3 is localized in a finite set of vertices in the case of the PQMF theory. In contrast, the localization happens in a subextensive fraction of the network in rDMP theory. Simulations, however, indicate that localization patterns of the actual epidemic lay between the two mean-field theories, and improved theoretical approaches are necessary to understanding the SIRS dynamics.

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.

Fundamental limitations on efficiently forecasting certain epidemic measures in network models

The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problems (e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems.

Nonmassive immunization to contain spreading on complex networks

Optimal strategies for epidemic containment are focused on dismantling the contact network through effective immunization with minimal costs. However, network fragmentation is seldom accessible in practice and may present extreme side effects. In this work, we investigate the epidemic containment immunizing population fractions far below the percolation threshold. We report that moderate and weakly supervised immunizations can lead to finite epidemic thresholds of the susceptible-infected-susceptible model on scale-free networks by changing the nature of the transition from a specific motif to a collectively driven process. Both pruning of efficient spreaders and increasing of their mutual separation are necessary for a collective activation. Fractions of immunized vertices needed to eradicate the epidemics which are much smaller than the percolation thresholds were observed for a broad spectrum of real networks considering targeted or acquaintance immunization strategies. Our work contributes for the construction of optimal containment, preserving network functionality through nonmassive and viable immunization strategies.

Suppressing epidemic spreading by optimizing the allocation of resources between prevention and treatment

The rational allocation of resources is crucial to suppress the outbreak of epidemics. Here, we propose an epidemic spreading model in which resources are used simultaneously to prevent and treat disease. Based on the model, we study the impacts of different resource allocation strategies on epidemic spreading. First, we analytically obtain the epidemic threshold of disease using the recurrent dynamical message passing method. Then, we simulate the spreading of epidemics on the Erdős-Rényi (ER) network and the scale-free network and investigate the infection density of disease as a function of the disease infection rate. We find hysteresis loops in the phase transition of the infection density on both types of networks. Intriguingly, when different resource allocation schemes are adopted, the phase transition on the ER network is always a first-order phase transition, while the phase transition on the scale-free network transforms from a hybrid phase transition to a first-order phase transition. Particularly, through extensive numerical simulations, we find that there is an optimal resource allocation scheme, which can best suppress epidemic spreading. In addition, we find that the degree heterogeneity of the network promotes the spreading of disease. Finally, by comparing theoretical and numerical results on a real-world network, we find that our method can accurately predict the spreading of disease on the real-world network.