Computer Science Location: Zoom (contact presenter for link)
Add to Calendar 2022-11-22T12:00:00 2022-11-22T12:00:00 America/New_York MS Thesis Defense Presentation by Ritwick Mishra Reconstructing an Epidemic Outbreak using Steiner connectivity Abstract:   Zoom (contact presenter for link)

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. 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.



  • 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