Group Testing on a Network

Authors

  • Arlei Silva UC, Santa Barbara
  • Ambuj Singh UC, Santa Barbara

Keywords:

Graph Mining, Social Network Analysis & Community, AI Responses to the COVID-19 Pandemic (Covid19), Healthcare, Medicine & Wellness, Applications

Abstract

Group testing---where multiple samples are tested together using a single test kit and individual tests are performed only for samples in positive groups---is a popular strategy to optimize the use of testing resources. We investigate how to effectively group samples for testing based on a transmission network. We formalize the group assembling problem as a graph partitioning problem, where the goal is to minimize the expected number of tests needed to screen the entire network. The problem is shown to be computationally hard and thus we focus on designing effective heuristics for it. Using realistic epidemic models on real contact networks, we show that our approaches save up to 33\% of resources---compared to the best baseline---at 4\% prevalence, are still effective at higher prevalence, and are robust to missing transmission data.

Downloads

Published

2021-05-18

How to Cite

Silva, A., & Singh, A. (2021). Group Testing on a Network. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 4348-4356. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16560

Issue

Section

AAAI Technical Track on Data Mining and Knowledge Management