Reconstructing an Epidemic Outbreak Using Steiner Connectivity
Reconstructing an Epidemic Outbreak Using Steiner Connectivity
复制标题
DOI：
10.1609/aaai.v37i10.26372
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Ritwick Mishra;Jack Heavey;Gursharn Kaur;Abhijin Adiga;A. Vullikanti
中科院分区：
文献类型：
--
作者：
Ritwick Mishra;Jack Heavey;Gursharn Kaur;Abhijin Adiga;A. Vullikanti
由于无症状病例和漏报等多种原因，在疫情中实际上只观察到一部分感染。因此，根据一些观察到的病例重新构建流行病级联是应对此类疫情的重要步骤。这个问题的最大似然解决方案（称为级联MLE）可以被证明是经典Steiner子图问题的变体，它连接了观察到的感染的子集。在以前的作品流行病重建，考虑标准的施泰纳树目标，我们表明，解决方案CascadeMLE，实际的MLE目标的基础上，有一个非常不同的结构。我们为CascadeMLE设计了一个对数近似算法，并在多个合成和社交联系网络上对其进行了评估，其中包括为医院构建的联系网络。我们的算法有显着更好的性能相比，以前的基线。
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.