Reconstructing an Epidemic Outbreak using Steiner connectivity
Abstract:
Only a subset of infections is actually observed in an outbreak, due to multiple reasons such as asymptomatic cases and under-reporting. Therefore, reconstructing an epidemic cascade given some observed cases is an important step in responding to such an outbreak. We first consider the problem of finding a maximum likelihood solution to this problem (referred to as CascadeMLE). This 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 a hospital. Our algorithm has significantly better performance compared to a prior baseline. Next, we consider the problem of generating probable cascades that span the observed infections. This has been shown to correspond to the problem of sampling Steiner trees, given a set of terminal nodes. We sample random Steiner trees according to the correct distribution and use them to estimate the marginal probability of a node being infected.
Committee:
- Jundong Li, Chair, CS, ECE/SEAS, SDS/UVA
- Anil Vullikanti, Co-Advisor, CS/Biocomplexity/SEAS/UVA
- Abhijin Adiga, Co-Advisor, UVA Biocomplexity Institute
- Madhav Marathe, CS/Biocomplexity /SEAS/UVA