Epidemic extinction paths in complex 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.

Using Symmetry to Enhance the Performance of Agent-Based Epidemic Models

Symmetries express the invariance of a system towards sets of mathematical transformations. In more practical terms, symmetries greatly reduce or simplify the computational efforts required to evaluate relevant properties of a system. In this paper, two methods are proposed to implement spin symmetries which simplify the analysis of the spreading of diseases in an agent-based epidemic model. We perform a set of simulations to measure the efficiency gains compared to traditional methods. Our findings show symmetry-based algorithms improve the performance of the Monte Carlo simulation and the exact Markov process.

Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks

Numerous problems of both theoretical and practical interest are related to finding shortest (or otherwise optimal) paths in networks, frequently in the presence of some obstacles or constraints. A somewhat related class of problems focuses on finding optimal distributions of weights which, for a given connection topology, maximize some kind of flow or minimize a given cost function. We show that both sets of problems can be approached through an analysis of the large-deviation functions of random walks. Specifically, a study of ensembles of trajectories allows us to find optimal paths, or design optimal weighted networks, by means of an auxiliary stochastic process (the generalized Doob transform). The paths are not limited to shortest paths, and the weights must not necessarily optimize a given function. Paths and weights can in fact be tailored to a given statistics of a time-integrated observable, which may be an activity or current, or local functions marking the passing of the random walker through a given node or link. We illustrate this idea with an exploration of optimal paths in the presence of obstacles, and networks that optimize flows under constraints on local observables.

Markovian approach to tackle the interaction of simultaneous diseases

The simultaneous emergence of several abrupt disease outbreaks or the extinction of some serotypes of multistrain diseases are fingerprints of the interaction between pathogens spreading within the same population. Here, we propose a general and versatile benchmark to address the unfolding of both cooperative and competitive interacting diseases. We characterize the explosive transitions between the disease-free and the epidemic regimes arising from the cooperation between pathogens and show the critical degree of cooperation needed for the onset of such abrupt transitions. For the competing diseases, we characterize the mutually exclusive case and derive analytically the transition point between the full-dominance phase, in which only one pathogen propagates, and the coexistence regime. Finally, we use this framework to analyze the behavior of the former transition point as the competition between pathogens is relaxed.

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.

Degree Dispersion Increases the Rate of Rare Events in Population Networks

There is great interest in predicting rare and extreme events in complex systems, and in particular, understanding the role of network topology in facilitating such events. In this Letter, we show that degree dispersion-the fact that the number of local connections in networks varies broadly-increases the probability of large, rare fluctuations in population networks generically. We perform explicit calculations for two canonical and distinct classes of rare events: network extinction and switching. When the distance to threshold is held constant, and hence stochastic effects are fairly compared among networks, we show that there is a universal, exponential increase in the rate of rare events proportional to the variance of a network's degree distribution over its mean squared.

Large deviations of random walks on random graphs

We study the rare fluctuations or large deviations of time-integrated functionals or observables of an unbiased random walk evolving on Erdös-Rényi random graphs, and construct a modified, biased random walk that explains how these fluctuations arise in the long-time limit. Two observables are considered: the sum of the degrees visited by the random walk and the sum of their logarithm, related to the trajectory entropy. The modified random walk is used for both quantities to explain how sudden changes in degree fluctuations, similar to dynamical phase transitions, are related to localization transitions. For the second quantity, we also establish links between the large deviations of the trajectory entropy and the maximum entropy random walk.

Precise Estimates of Persistence Time for SIS Infections in Heterogeneous Populations

For a susceptible-infectious-susceptible infection model in a heterogeneous population, we derive simple and precise estimates of mean persistence time, from a quasi-stationary endemic state to extinction of infection. Heterogeneity may be in either individuals' levels of infectiousness or of susceptibility, as well as in individuals' infectious period distributions. Infectious periods are allowed to follow arbitrary non-negative distributions. We also obtain a new and accurate approximation to the quasi-stationary distribution of the process, as well as demonstrating the use of our estimates to investigate the effects of different forms of heterogeneity. Our model may alternatively be interpreted as describing an infection spreading through a heterogeneous directed network, under the annealed network approximation.

General formulation of long-range degree correlations in complex networks

We provide a general framework for analyzing degree correlations between nodes separated by more than one step (i.e., beyond nearest neighbors) in complex networks. One joint and four conditional probability distributions are introduced to fully describe long-range degree correlations with respect to degrees k and k^{'} of two nodes and shortest path length l between them. We present general relations among these probability distributions and clarify the relevance to nearest-neighbor degree correlations. Unlike nearest-neighbor correlations, some of these probability distributions are meaningful only in finite-size networks. Furthermore, as a baseline to determine the existence of intrinsic long-range degree correlations in a network other than inevitable correlations caused by the finite-size effect, the functional forms of these probability distributions for random networks are analytically evaluated within a mean-field approximation. The utility of our argument is demonstrated by applying it to real-world networks.

Rare slips in fluctuating synchronized oscillator networks

We study rare phase slips due to noise in synchronized Kuramoto oscillator networks. In the small-noise limit, we demonstrate that slips occur via large fluctuations to saddle phase-locked states. For tree topologies, slips appear between subgraphs that become disconnected at a saddle-node bifurcation, where phase-locked states lose stability generically. This pattern is demonstrated for sparse networks with several examples. Scaling laws are derived and compared for different tree topologies. On the other hand, for dense networks slips occur between oscillators on the edges of the frequency distribution. If the distribution is discrete, the probability-exponent for large fluctuations to occur scales linearly with the system size. However, if the distribution is continuous, the probability is a constant in the large network limit, as individual oscillators fluctuate to saddles while all others remain fixed. In the latter case, the network's coherence is approximately preserved.

Enhancement of large fluctuations to extinction in adaptive networks

During an epidemic, individual nodes in a network may adapt their connections to reduce the chance of infection. A common form of adaption is avoidance rewiring, where a noninfected node breaks a connection to an infected neighbor and forms a new connection to another noninfected node. Here we explore the effects of such adaptivity on stochastic fluctuations in the susceptible-infected-susceptible model, focusing on the largest fluctuations that result in extinction of infection. Using techniques from large-deviation theory, combined with a measurement of heterogeneity in the susceptible degree distribution at the endemic state, we are able to predict and analyze large fluctuations and extinction in adaptive networks. We find that in the limit of small rewiring there is a sharp exponential reduction in mean extinction times compared to the case of zero adaption. Furthermore, we find an exponential enhancement in the probability of large fluctuations with increased rewiring rate, even when holding the average number of infected nodes constant.

Large order fluctuations, switching, and control in complex networks

We propose an analytical technique to study large fluctuations and switching from internal noise in complex networks. Using order-disorder kinetics as a generic example, we construct and analyze the most probable, or optimal path of fluctuations from one ordered state to another in real and synthetic networks. The method allows us to compute the distribution of large fluctuations and the time scale associated with switching between ordered states for networks consistent with mean-field assumptions. In general, we quantify how network heterogeneity influences the scaling patterns and probabilities of fluctuations. For instance, we find that the probability of a large fluctuation near an order-disorder transition decreases exponentially with the participation ratio of a network's principle eigenvector - measuring how many nodes effectively contribute to an ordered state. Finally, the proposed theory is used to answer how and where a network should be targeted in order to optimize the time needed to observe a switch.