Adaptive Group Testing on Networks with Community Structure

Ahn, S.; Chen, W. N.; Ozgur, A.

Since the inception of the group testing problem in World War II, one of the prevailing assumptions in the probabilistic variant of the problem has been that individuals in the population are infected by a disease independently. However, this assumption rarely holds in practice, as diseases typically spread through interactions between individuals and therefore cause infections to be correlated. Inspired by characteristics of COVID-19 and similar diseases, we consider an infection model over networks which generalizes the traditional i.i.d. model from probabilistic group testing. Under this infection model, we ask whether knowledge of the network structure can be leveraged to perform group testing more efficiently, focusing specifically on community-structured graphs drawn from the stochastic block model. We prove that when the network and infection parameters are conducive to 'strong community structure;' our proposed adaptive, graph-aware algorithm outperforms the baseline binary splitting algorithm, and is even order-optimal in certain parameter regimes. A full version of this paper is accessible at http://arxiv.org/abs/2101.0240S. Omitted proofs and numerical experiments are provided in the full version © 2021 IEEE.