Bayesian Inference of Epidemics on Networks via Belief Propagation

We study several Bayesian inference problems for irreversible stochastic epidemic models on networks from a statistical physics viewpoint. We derive equations which allow us to accurately compute the posterior distribution of the time evolution of the state of each node given some observations. At difference with most existing methods, we allow very general observation models, including unobserved nodes, state observations made at different or unknown times, and observations of infection times, possibly mixed together. Our method, which is based on the belief propagation algorithm, is efficient, naturally distributed, and exact on trees. As a particular case, we consider the problem of finding the “zero patient” of a susceptible-infected-recovered or susceptible-infected epidemic given a snapshot of the state of the network at a later unknown time. Numerical simulations show that our method outperforms previous ones on both synthetic and real networks, often by a very large margin.

Figure 1

Factor graph representations for irreversible dynamics: full squares represent the factors of a generalized Boltzman distribution and ellipses the variables on which they depend. (a) Original graph. (b) Loopy, naive factor graph for a deterministic dynamics. (c) Disentangled dual tree factor graph. (d) Factor graph for the SIR model given in (3), with known epidemic age. (e) Factor graph representation with unknown epidemic age.

Figure 2

Comparison between BP and DMP, DMPr, and Jordan methods. Each point is an average over 1000 epidemics in random graphs with $N=1000$. Panels (a)–(b) are for SFG with average degree $⟨k⟩=4$, recovery probability $\mu =0.5$ and observation time $T=5$. Panels (c)–(f) are for RRG with $k=4$, $\mu =0.5$, and $T=10$. (a) and (c) Probability of finding the true origin $i_0$ of the epidemics as a function of the average epidemics size $N_{\mathrm{IR}}$. (b) and (d) Normalized rank of the true origin $(\text{rank}{i}_0)/N_{\mathrm{IR}}$ as a function of the transmission probability $\lambda$. The normalized epidemics size $N_{\mathrm{IR}}/N$ is also plotted (purple, right axis) vs $\lambda$. For very large epidemics BP may fail to converge in (a) and (b) within the specified number of iterations [the convergence probability is plotted in green in (a)], but relevant information is still present in the (unconverged) marginals. (e) Probability of finding the true origin of the epidemic as a function of the fraction of unobserved sites $\xi$ for transmission probability $\lambda =0.5$ and recovery probability $\mu =1$. (f) Absolute rank given by each algorithm to the true origin as a function of $\xi$.

Figure 3

Examples of inference with incomplete information on a RRG with $N=1000$, $k=4$. Left: inference with $\lambda =0.7$, $\mu =0.6$, $\gamma ={10}^{-6}$, from observations fraction $1-\xi =0.6$ at time $T=0$ for an epidemic with $T_0=-8$ (unknown to BP). Each colored block ($R$: recovered, $I$: infected and $X$: unknown) corresponds to a vertex, ordered in the horizontal axis by its real infection time given in the vertical axis. The mean and standard deviation of their BP posterior marginal distribution of infection time is plotted (black dots and error bars) along with the marginal posterior probability of spontaneous infection (orange, circles, right axis). Right: Inference of epidemic parameters. Heat-plot of the likelihood density of the parameters for two virtual epidemics. The first one with $\lambda =0.7$, $\mu =0.6$, $\mathrm{\Delta }T=8$ (size $N_{\mathrm{IR}}=653$) shows a maximum of the estimated likelihood at $\widehat{\lambda }=0.695$ and $\widehat{\mu }=0.605$, and the second with $\lambda =0.5$, $\mu =0.5$, $\mathrm{\Delta }T=10$ (size $N_{\mathrm{IR}}=462$) shows a maximum at $\widehat{\lambda }=0.5$ and $\widehat{\mu }=0.52$.

Figure 4

BP inference of multiple seeds for virtual epidemics on a RRG with $N=1000$, $k=4$, and $\mu =1$, $\lambda =0.5$, $\gamma =0.002$, and different epidemic ages $\mathrm{\Delta }T$ (unknown to BP). Left: an example receiver operating characteristics (ROC) curve for a sample with 5 origins and $\mathrm{\Delta }T=8$, $N_{\mathrm{IR}}=379$. The first three ranked nodes are true seeds, and the average normalized area below the curve is 0.975. Right: the average normalized area below the ROC curve vs the number of true origins on 1000 samples. Each ROC curve was computed restricted to the epidemic subgraph.