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, reconstructing an epidemic cascade given some observed cases is an important step in responding to such an outbreak. A maximum likelihood solution to this problem ( referred to as CascadeMLE ) 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.

Authors

• Ritwick Mishra Biocomplexity Institute and Dept of Computer Science, University of Virginia
• Jack Heavey Biocomplexity Institute and Dept of Computer Science, University of Virginia
• Gursharn Kaur Biocomplexity Institute & Initiative, University of Virginia
• Abhijin Adiga University of Virginia
• Anil Vullikanti Computer Science Dept., University of Virginia Biocomplexity Institute, University of Virginia

Keywords

• DMKM: Graph Mining, Social Network Analysis & Community Mining
• MAS: Agent-Based Simulation and Emergent Behavior