Reconstructing an Epidemic Outbreak using Steiner Connectivity

Only a subset of infections is actually observed in an outbreak, due to multiple reasons such as asymptomatic cases and under-reporting. Therefore, inferring the state of the epidemic, given some observed cases, is an important step in formulating our response. We consider two approaches for reconstructing a cascade and inferring epidemic properties.

First, we consider the problem of finding a maximum likelihood (MLE) solution to the cascade reconstruction problem for the Independent Cascade (IC) model (referred to as CascadeMLE). This is a common approach in many inference problems, and can be shown to be a variation of the classical Steiner subgraph problem, which connects a subset of observed infections. In contrast to prior works on epidemic reconstruction, which consider the standard Steiner tree objective, we show that a solution to CascadeMLE, based on the actual MLE objective, has a very different structure. We design a logarithmic approximation algorithm for CascadeMLE, and evaluate it on multiple synthetic and social contact networks, including a contact network constructed for the University of Virginia (UVA) hospital. Our algorithm has significantly better performance compared to a prior baseline.

The MLE solution might not be very informative in many regimes, as our experiments show. In such settings, it is useful to consider the actual distribution of cascades, which are consistent with the observed infections. This can be shown to correspond to the problem of sampling Steiner trees which contain a set of terminal nodes, with a probability that depends on both the edges in the tree and the edges not in the tree. While there has been a lot of work on random sampling of spanning trees, random sampling of Steiner trees is open. A prior approach considers random generation of spanning trees with probability proportional to the product of probabilities of edges in the tree. We show that this gives a very different distribution on Steiner trees. We discuss partial progress in generating Steiner trees with the correct distribution.