Provable Sensor Sets for Epidemic Detection over Networks with Minimum Delay
Provable Sensor Sets for Epidemic Detection over Networks with Minimum Delay
复制标题
DOI：
10.1609/aaai.v36i9.21260
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Jack Heavey;Jiaming Cui;Chen Chen-Chen;B. Prakash;A. Vullikanti
中科院分区：
文献类型：
--
作者：
Jack Heavey;Jiaming Cui;Chen Chen-Chen;B. Prakash;A. Vullikanti
有效检测疾病爆发和其他级联现象是许多领域的基本问题，包括疾病传播、社交网络和基础设施网络。在这种情况下，监测和测试来自易感人群的一小组预选节点（即，传感器组）通常是优选的测试方案。我们研究的问题，选择一个传感器组，最大限度地减少检测延迟-我们称之为MinDelSS问题。用于最小化检测时间的现有方法依赖于使用子模块化的贪婪算法。我们表明，这种方法有时会导致更差的近似最小化检测时间比预期的。我们还表明，MinDelSS是很难近似在一个O（n^（1-1/g））-因子的任何常数g大于或等于2的图与n个节点。这反而促使寻求双准则近似。我们提出了算法RoundSensor，它给出了一个严格的最坏情况下的O（log（n））-因子的检测时间，而违反预算的一个因素O（log^2（n））。我们的算法是基于随机优化的样本平均近似技术，结合线性规划和舍入。我们评估我们的算法在几个网络，包括医院接触网络，这验证了它的有效性，在真实的设置。
The efficient detection of outbreaks and other cascading phenomena is a fundamental problem in a number of domains, including disease spread, social networks, and infrastructure networks. In such settings, monitoring and testing a small group of pre-selected nodes from the susceptible population (i.e., a sensor set) is often the preferred testing regime. We study the problem of selecting a sensor set that minimizes the delay in detection---we refer to this as the MinDelSS problem. Prior methods for minimizing the detection time rely on greedy algorithms using submodularity. We show that this approach can sometimes lead to a worse approximation for minimizing the detection time than desired. We also show that MinDelSS is hard to approximate within an O(n^(1-1/g))-factor for any constant g greater than or equal to 2 for a graph with n nodes. This instead motivates seeking a bicriteria approximations. We present the algorithm RoundSensor, which gives a rigorous worst case O(log(n))-factor for the detection time, while violating the budget by a factor of O(log^2(n)). Our algorithm is based on the sample average approximation technique from stochastic optimization, combined with linear programming and rounding. We evaluate our algorithm on several networks, including hospital contact networks, which validates its effectiveness in real settings.