Group Testing on a Network


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



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


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.




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.



AAAI Technical Track on Data Mining and Knowledge Management