Source-linked AI summary
A message passing approach for general epidemic models
Brian Karrer, M. E. J. Newman
TL;DR
Standard epidemic models assume constant transmission and recovery probabilities, implying exponential time intervals that often differ from real disease distributions. The paper reformulates generalized SIR dynamics as time-dependent message passing, obtaining exact results on trees and locally tree-like networks and rigorous outbreak bounds on networks with loops.
Problem
Conventional SIR calculations assume constant infection and recovery probabilities, although real disease-time distributions are often nonexponential.
Method
The paper reformulates generalized SIR dynamics with arbitrary infection and recovery-time distributions as a time-dependent message passing calculation on contact networks.
Results
The calculation is exact on trees and locally tree-like networks and provides rigorous bounds on disease-state probabilities and outbreak size on non-tree-like networks.
Takeaways & Limitations
Message passing extends epidemic analysis beyond exponential transition times while retaining network structure and producing rigorous outbreak-size bounds on loopy networks.
Abstract
from arXiv · showhide
In most models of the spread of disease over contact networks it is assumed that the probabilities per unit time of disease transmission and recovery from disease are constant, implying exponential distributions of the time intervals for transmission and recovery. Time intervals for real diseases, however, have distributions that in most cases are far from exponential, which leads to disagreements, both qualitative and quantitative, with the models. In this paper, we study a generalized version of the SIR (susceptible-infected-recovered) model of epidemic disease that allows for arbitrary distributions of transmission and recovery times. Standard differential equation approaches cannot be used for this generalized model, but we show that the problem can be reformulated as a time-dependent message passing calculation on the appropriate contact network. The calculation is exact on trees (i.e., loopless networks) or locally tree-like networks (such as random graphs) in the large system size limit. On non-tree-like networks we show that the calculation gives a rigorous bound on the size of disease outbreaks. We demonstrate the method with applications to two specific models and the results compare favorably with numerical simulations.
I. INTRODUCTION
Compartmental epidemic models commonly assume random mixing and constant transition rates, but real contact patterns and disease-time distributions often violate these assumptions. The paper addresses the latter shortcoming by reformulating generalized epidemic calculations as message passing on contact networks.
- Compartmental models divide populations into disease-status classes and use differential equations to describe flows between them.
- Random mixing assumes that disease-causing contact is equally likely with any member of a compartment, unlike most real-world contact patterns.Network epidemiology models contacts explicitly because network structure can profoundly affect disease spread.
- Constant transition rates imply exponential distributions for infection and recovery times, which are far from the behavior of most real diseases.
- Nonexponential disease-time behavior can be modeled with integro-differential equations under mass-action, but that approach does not retain nonrandom contact networks.
- The paper reformulates generalized epidemic calculations as message passing, yielding exact solutions on broad network classes and additional results for network epidemiology.The formulation also gives a rigorous outbreak-size upper bound and results for late-time and random-ensemble behavior.
II. A MESSAGE PASSING FORMULATION OF EPIDEMICS
The generalized SIR model represents transmission and recovery with arbitrary time distributions on a contact network. Its central message is the probability that one vertex has not transmitted to a neighboring vertex, which yields complete disease-state probabilities on trees.
- The model is an SIR process on a contact network with independent initial susceptibility probability z and arbitrary infection and recovery-time distributions.
- The transmission-time density f(τ) combines contact timing with the probability that an infected individual remains unrecovered at time τ.Unlike the separate contact and recovery distributions, f(τ) integrates to transmissibility, the probability of transmitting before recovery.
- The message H_i←j(t) is the probability that vertex j has not passed disease to neighboring vertex i by absolute time t.
- On a tree, failure of transmission from j to i occurs either because j does not transmit soon enough or because j becomes infected too late to transmit by time t.The latter case accounts for delayed or absent infection of j from neighbors other than i.
- For tree networks, the message-passing equation solves H_i←j(t) for all times and arbitrary f(τ).
- Equations (2)–(5) determine the susceptible, infected, and recovered probabilities for arbitrary, including nonexponential, infection and recovery-time distributions.P(I_i) is obtained by integrating its rate equation, and P(R_i) follows because the three state probabilities sum to one.
III. MESSAGE PASSING ON NON-TREE NETWORKS
The paper extends message passing to generalized SIR dynamics on networks with loops, where nonexponential transmission and recovery times are represented through time-dependent edge messages. The resulting calculation is exact on trees and provides rigorous outbreak bounds on loopy networks, though an efficient scalar approximation is limited during intermediate epidemic times.
- Bounds on loopy networks: On networks with loops, message passing is not exact but yields a rigorous upper bound on the number of infected individuals.The corresponding susceptibility calculation provides a lower bound on P(Si) and upper bounds on infection and recovery probabilities.
- Model construction: The generalized SIR process assigns arbitrary transmission and recovery-time distributions to a fixed contact network rather than assuming exponential transitions.Transmission events are represented by directed edges with delays wij, with wij set to ∞ when recovery precedes transmission.
- Message construction: Cavity-based messages exclude infection paths that pass through the target vertex, enabling a recursive approximation based on neighbor-specific transmission routes.The construction restricts paths according to their penultimate neighbor and forbids paths that pass through the target more than once.
- Message construction: The figure illustrates loop-induced overcounting: summing reachable vertices through immediate neighbors counts four vertices although only three red vertices exist.The top red vertex is counted twice because it has two paths to the black vertex.
- Computation: A scalar decoupling approximation avoids integrals but is generally reliable only at early and late times, not during the intermediate interval of greatest interest.Its accuracy depends on F_i←j(t) remaining relatively constant over the disease timescales represented by f(τ).
IV. LATE-TIME BEHAVIOR
The late-time generalized SIR calculation reduces the message-passing quantities to scalar messages governed by total edge transmissibility. It yields an upper bound on the probability that each individual ever contracts the disease and therefore on outbreak size, while connecting the limit to correlated bond percolation.
- Late-time calculation: At late times, the message-passing calculation uses scalar messages and can be performed quickly even on networks that are not trees.The scalar edge quantity is based on p, the total probability of transmission between connected vertices.
- Late-time outcomes: The late-time calculation gives an upper bound on the probability that any individual ever contracts the disease and on total outbreak size.Because no individuals remain infected at late times, P(Ri)=1−P(Si).
- Interpretation: The late-time SIR process is related to correlated bond percolation on the directed transmission network.Correlations arise because an individual’s recovery time affects transmission probabilities to all of its neighbors.
V. EPIDEMICS ON CONFIGURATION MODEL NETWORKS
The message-passing formalism computes average epidemic behavior on configuration-model networks by exploiting their locally tree-like structure in large systems.
- Configuration-model averaging: The formalism calculates average epidemic behavior over configuration-model network ensembles, averaging both disease dynamics and graph randomness.Configuration models fix the degree distribution while connecting vertices randomly.
- Configuration-model averaging: All configuration-model edges share the same ensemble-averaged message H1(t), reducing the calculation to one representative message.H1(t) is the average probability that infection has not yet crossed an edge by time t.
- Configuration-model averaging: In large configuration-model networks, local tree-likeness allows the averaged product of neighboring messages to become a power of H1(t).The exponent follows the excess-degree distribution qk.
- Epidemic observables: The resulting generating-function equations determine susceptible probabilities and, subsequently, infected and recovered probabilities.Late-time equations also expose the connection between generalized SIR dynamics and bond percolation.
VI. EXAMPLES
The examples compare exponential and top-hat transition-time distributions, showing that matching long-term transmission can still produce different epidemic dynamics over time.
- Exponential distributions: For exponential infection and recovery times, the analytic solution agrees well with simulations and produces a familiar SIR outbreak curve.The infected fraction briefly peaks, then declines as the recovered fraction rises.
- Top-hat distributions: The top-hat model introduces a latent period before infectiousness and a fixed recovery time after infection.Its parameters specify when transmission begins, when recovery occurs, and the total transmission probability.
- Top-hat distributions: Matching mean transmission time and total transmission probability preserves the long-time behavior between exponential and top-hat models.The comparison uses the same Poisson degree distribution as the exponential example.
- Dynamic differences: The two models still differ substantially in time-dependent dynamics: the top-hat case produces infection waves, while the exponential case infects more people at any time and lasts longer.Both epidemics peak at about t = 6 in the plots.
- Dynamic differences: Infection waves become blurred as τr and τs separate and become more pronounced when those times are closer together.Predictions remain qualitatively similar and agree similarly well with simulations across several degree distributions.
VII. CONCLUSIONS
The paper generalizes SIR network modeling to non-constant infection and recovery times using message passing, with exactness on tree-like networks and rigorous bounds on loopy networks.
- Conclusions: The generalized SIR model allows arbitrary, non-constant distributions of infection and recovery times on contact networks.This abandons the conventional constant-rate assumption and its differential-equation treatment.
- Conclusions: Message passing provides an exact calculation on trees and locally tree-like networks, while giving rigorous bounds on non-tree-like networks.The paper applies the approach to late-time behavior and configuration-model network averages.
- Conclusions: The framework can extend to SI, SEIR, and potentially threshold models, but a corresponding message-passing solution for SIS remains unavailable.The SIS case remains an open problem because vertices can return to previous states.
Appendix: Chebyshev Integral Inequality
The appendix establishes a Chebyshev integral inequality for products of monotone non-negative functions by averaging over independent variables and using induction.
- Inequality setup: The appendix considers non-negative functions that are monotone in each argument, allowing different monotonic directions across arguments.A function may increase in one argument and decrease in another.
- Proof strategy: Averaging over independent variables reduces the multivariate inequality to repeated partial averages.The partial average is a function of the remaining arguments.
- Proof strategy: The proof compares function differences at independent values and uses monotonicity to show the resulting product is non-negative.The argument begins with arbitrary x and y sharing the same distribution as the averaged variable.
- Proof strategy: Induction applies the one-variable inequality successively until the full multivariate result is established.The base case is Eq. (A.5).