Reconstructing an Epidemic Outbreak Using Steiner Connectivity
Ritwick Mishra, Jack Heavey, Gursharn Kaur, Abhijin Adiga, Anil Vullikanti
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. 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.
BibTeX
@article{Mishra_Heavey_Kaur_Adiga_Vullikanti_2023, title={Reconstructing an Epidemic Outbreak Using Steiner Connectivity}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26372}, DOI={10.1609/aaai.v37i10.26372}, abstractNote={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.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Mishra, Ritwick and Heavey, Jack and Kaur, Gursharn and Adiga, Abhijin and Vullikanti, Anil}, year={2023}, month={Jun.}, pages={11613-11620} }