Source-linked AI summary
SIRS Epidemics on Complex Networks: Concurrence of Exact Markov Chain and Approximated Models
Navid Azizan Ruhi, Babak Hassibi
TL;DR
The paper examines how network SIRS epidemic dynamics relate across exact and approximate models. It analyzes the exact Markov chain alongside nonlinear and linear approximations, finding a shared eradication threshold and a unique endemic fixed point when that threshold is violated.
Problem
The exact network epidemic chain is difficult to analyze, while common low-dimensional approximations require a connection to the chain’s behavior to interpret their stability results.
Source: §I · p. 1Method
The paper provides a global analysis of the SIRS nonlinear mean-field model and relates its stability to fast mixing of the exact network Markov chain.
Source: §I · p. 1Results
The fast-mixing threshold of the exact Markov chain coincides with disease-free stability of the mean-field approximation, and above threshold the nonlinear model has a unique endemic fixed point.
Source: §I · p. 1, §VII · p. 10Takeaways & Limitations
Simulations suggest that above threshold the exact Markov chain mixes exponentially slowly, motivating the conjecture that the shared threshold is tight.
Source: §VII · p. 10
Abstract
from arXiv · showhide
We study the SIRS (Susceptible-Infected-Recovered-Susceptible) spreading processes over complex networks, by considering its exact $3^n$-state Markov chain model. The Markov chain model exhibits an interesting connection with its $2n$-state nonlinear "mean-field" approximation and the latter's corresponding linear approximation. We show that under the specific threshold where the disease-free state is a globally stable fixed point of both the linear and nonlinear models, the exact underlying Markov chain has an $O(\log n)$ mixing time, which means the epidemic dies out quickly. In fact, the epidemic eradication condition coincides for all the three models. Furthermore, when the threshold condition is violated, which indicates that the linear model is not stable, we show that there exists a unique second fixed point for the nonlinear model, which corresponds to the endemic state. We also investigate the effect of adding immunization to the SIRS epidemics by introducing two different models, depending on the efficacy of the vaccine. Our results indicate that immunization improves the threshold of epidemic eradication. Furthermore, the common threshold for fast-mixing of the Markov chain and global stability of the disease-free fixed point improves by the same factor for the vaccination-dominant model.
I. INTRODUCTION
The paper analyzes SIRS epidemics on networks, relating the global dynamics of a nonlinear mean-field approximation to the mixing behavior of the exact Markov chain. It also sets out the node-level transitions and the approximations used in that analysis.
I. INTRODUCTION
- In the network SIRS model, susceptible nodes can be infected by infected neighbors with probability β, infected nodes recover with probability δ, and recovered nodes return to susceptibility with probability γ.The model also considers random vaccination, with probability θ, that moves susceptible nodes directly to the recovered state.Source: §I · p. 1
- Depending on the graph’s largest adjacency eigenvalue and the infection-to-recovery rate ratio, the nonlinear model either dies out or converges to a unique endemic fixed point.The paper connects global stability of the approximate models to whether the underlying Markov chain is fast-mixing, extending analysis of SIS models, to SIRS.Source: §I · p. 1
A. Exact Markov Chain Model
- The exact model assigns each node one of three states—susceptible, infected, or recovered—and uses a Markov chain to represent network transitions.A node’s infection probability depends on its infected neighbors; the transition matrix uses independence of next-node states given the current state.Source: A. Exact Markov Chain Model · pp. 1–2
B. Nonlinear Model
- The nonlinear mean-field approximation is a 2n-state mapping that approximates the exact model’s marginal probabilities.The paper distinguishes its approximate probabilities P from the exact Markov-chain probabilities p.Source: B. Nonlinear Model · p. 2
C. Linear Model
The linear model is obtained by linearizing the nonlinear mean-field mapping at the origin. Under the eradication threshold, both approximations are globally stable at the disease-free state, and the exact Markov chain mixes in O(log n).
C. Linear Model
- Linearizing the nonlinear mean-field equations around the origin yields the linear mapping.The linear model is introduced as a further approximation of the nonlinear mapping.Source: C. Linear Model · p. 2
A. The Trivial Fixed Point of the Map and Steady State of the MC
- The Markov chain’s unique stationary distribution is concentrated on the all-susceptible state, which is also the mappings’ disease-free fixed point.The paper distinguishes this stationary state from the question of how quickly the chain reaches it.Source: A. The Trivial Fixed Point of the Map… · p. 3
B. Stability of the Trivial Fixed Point
- When ∥M∥ < 1, the origin is globally stable for the linear model and locally stable for the nonlinear model; the nonlinear map is bounded above by the linear one.The eigenvalues of (1 − γ)I_n are below one, so the threshold depends on the largest eigenvalue of (1 − δ)I_n + βA.Source: B. Stability of the Trivial Fixed Point · p. 3
C. Mixing Time of the MC
- O(log n) mixing under the eradication threshold means the exact Markov chain converges quickly and the epidemic dies out.The stated mixing-time bound is O(log n).Source: C. Mixing Time of the MC · pp. 3, 5
A. Existence and Uniqueness of Nontrivial Fixed Point
Above the threshold where the origin is unstable, the nonlinear SIRS mean-field map has a unique nontrivial fixed point. The proof establishes existence and uniqueness of this point.
A. Existence and Uniqueness of Nontrivial Fixed Point
- Above the threshold where the origin is unstable, the nonlinear map has a unique nontrivial fixed point.The origin is unstable when (1 − δ) + βλmax(A) > 1.Source: A. Existence and Uniqueness of… · p. 5
- The proof first establishes a maximal point in the set of infection situations that become more infected or remain there.The set is closed under coordinatewise maxima, yielding a unique maximal point with all coordinates positive.Source: A. Existence and Uniqueness of… · p. 5
- The maximal point yields a nontrivial zero of Ψ, and zeros of Ψ correspond to fixed points of the nonlinear map.The proof concludes that the resulting point is the unique nontrivial fixed point.Source: A. Existence and Uniqueness of… · pp. 5–6
B. Stability of the Nontrivial Fixed Point
The unique nontrivial fixed point is not necessarily stable: the paper gives examples where the system converges to a cycle instead.
B. Stability of the Nontrivial Fixed Point
- Examples show that the system can converge to a cycle rather than the unique second fixed point, so that point is not stable in general.The paper relates this behavior to examples for the immune-admitting SIS model in.Source: B. Stability of the Nontrivial Fixed… · p. 6
V. VACCINATION
The vaccination extension adds direct immunization to the SIRS process. Depending on γ, immunization can be temporary or permanent.
V. VACCINATION
- The vaccination model permits a direct transition from susceptible to recovered, in addition to the transitions in the preceding model.Fig. 2 depicts a single node and its transition rates; θ is the probability of direct immunization.Source: §V · p. 6, Figure 2 · p. 6
- Immunization is temporary when γ ≠ 0 and permanent when γ = 0.Source: §V · p. 6
A. Infection-Dominant Model
The infection-dominant vaccination model specifies transitions when infection and vaccination reach a susceptible node simultaneously. Once infection is absent, the Markov chain reduces to independent susceptible–recovered dynamics for each node.
A. Infection-Dominant Model
- When a susceptible node receives infection and vaccine simultaneously, the infection-dominant model assigns the node to infection.For θ = 0, the transition model reduces to the non-vaccinating one.Source: A. Infection-Dominant Model · p. 7
- Once no nodes are infected, each node has independent transitions between susceptible and recovered states, with a stationary distribution for that single-node chain.The chain's convergence requires γθ ≠ 1.Source: A. Infection-Dominant Model · p. 7
- The nonlinear map has a fixed point consistent with the steady state of the Markov chain.Source: A. Infection-Dominant Model · p. 7
1) Stability of the Fixed Point:
The disease-free fixed point is locally stable under the stated eigenvalue condition, and the exact Markov chain has O(log n) mixing under the threshold conditions. The analysis also distinguishes this global-stability result from prior work that established only local stability.
1) Stability of the Fixed Point:
- The disease-free fixed point is locally stable when the largest eigenvalue of the stated linearized matrix is less than 1.The proof identifies this matrix as the Jacobian of the nonlinear map.Source: 1) Stability of the Fixed Point · p. 8
- Unlike the cited result, this analysis addresses global stability rather than only local stability.The cited work established the same local-stability condition but did not provide a global-stability result.Source: 1) Stability of the Fixed Point · p. 8
2) Mixing Time of MC:
- O(log n) mixing follows for the Markov chain under the stated threshold conditions.The passages state δλmax(A) < 1 and δ < 1.Source: 2) Mixing Time of MC · p. 8
B. Vaccination-Dominant Model
In the vaccination-dominant model, vaccination takes precedence when a susceptible node receives infection and vaccine simultaneously. Its steady state and main fixed point match those of the infection-dominant model, while the model is more stable.
B. Vaccination-Dominant Model
- When a susceptible node receives infection and vaccine simultaneously, it becomes vaccinated.The model specifies the transition probabilities for this variation.Source: B. Vaccination-Dominant Model · pp. 8–9
- The vaccination-dominant model has the same Markov-chain steady state and main fixed point as the infection-dominant model, but is more stable.Source: B. Vaccination-Dominant Model · p. 9
1) Stability of The Fixed Point:
Vaccination relaxes the disease-free stability condition by a factor of (1−θ), and the fast-mixing condition for the Markov chain improves by the same factor. Under the stated conditions, the vaccination-dominant chain mixes in O(log n).
1) Stability of The Fixed Point:
- The disease-free stability condition and the fast-mixing condition improve by the same factor, (1−θ), in the vaccination-dominant model.Source: 2) Mixing Time of MC · p. 9
2) Mixing Time of MC:
- O(log n) mixing holds for the vaccination-dominant Markov chain under the stated condition.The proof bounds infection probabilities using an infection term scaled by (1−θ).Source: 2) Mixing Time of MC · p. 9
- For δ > 1, the epidemic spreads around a nontrivial fixed point, with convergence not observed.Source: 2) Mixing Time of MC · p. 10
VI. EXPERIMENTAL RESULTS
The simulations support the threshold behavior: epidemics decay below the relevant threshold and persist around a nontrivial fixed point above it. They also indicate greater stability for vaccination, especially in the vaccination-dominant model.
VI. EXPERIMENTAL RESULTS
- Below the threshold, the SIRS epidemic decays exponentially and dies out quickly; above it, the epidemic does not converge to the disease-free state in observable time.For the above-threshold case, simulations show spread around the nontrivial fixed point.Source: §VI · p. 10
- Vaccination-dominant simulations show fast convergence under a threshold relaxed by the factor (1−θ), while above-threshold cases show no eradication in reasonable time.Source: §VI · p. 10
VII. CONCLUSIONS
- The paper concludes that fast mixing of the exact Markov chain and disease-free stability of the mean-field approximation share the eradication threshold; above it, the nonlinear model has a unique endemic fixed point.The simulations suggest exponentially slow Markov-chain mixing above threshold, leading the authors to conjecture that the threshold is tight.Source: §VII · p. 10