Adaptive Group Testing on Networks With Community Structure: The Stochastic Block Model
- 22 February 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (7) , 4758-4776
Abstract
Group testing was conceived during World War II to identify soldiers infected with syphilis using as few tests as possible, and it has attracted renewed interest during the COVID-19 pandemic. A long-standing assumption in the probabilistic variant of the group testing problem is that individuals are infected by the disease independently . However, this assumption rarely holds in practice, as diseases often spread through interactions between individuals and therefore cause infections to be correlated. Inspired by characteristics of COVID-19 and other infectious diseases, we introduce an infection model over networks which generalizes the traditional i.i.d. model from probabilistic group testing. Under this 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 a simple community-aware algorithm outperforms the baseline binary splitting algorithm when the model parameters are conducive to “strong community structure.” Moreover, our novel lower bounds imply that the community-aware algorithm is order-optimal in certain parameter regimes. We extend our bounds to the noisy setting and support our results with numerical experiments.Keywords
Funding Information
- NSF (1817205)
- Center for Science of Information (CSoI), an NSF Science and Technology Center (CCF-0939370)
- Cisco Systems Stanford Graduate Fellowship
- National Semiconductor Corporation Stanford Graduate Fellowship
This publication has 63 references indexed in Scilit:
- What's hot and what's not: tracking most frequent items dynamicallyACM Transactions on Database Systems, 2005
- Asymptotic efficiency of two-stage disjunctive testingIEEE Transactions on Information Theory, 2002
- Born again group testing: Multiaccess communicationsIEEE Transactions on Information Theory, 1985
- Stochastic blockmodels: First stepsSocial Networks, 1983
- Hypergeometric and Generalized Hypergeometric Group TestingSIAM Journal on Algebraic Discrete Methods, 1981
- A Boundary Problem for Group TestingSIAM Journal on Algebraic Discrete Methods, 1981
- A Method for Detecting all Defective Members in a Population by Group TestingJournal of the American Statistical Association, 1972
- Binomial Group-Testing with an Unknown Proportion of DefectivesTechnometrics, 1966
- On the Detection of Defective Members of Large PopulationsThe Annals of Mathematical Statistics, 1957
- The Detection of Defective Members of Large PopulationsThe Annals of Mathematical Statistics, 1943