| Paper ID | D3-S4-T3.2 |
| Paper Title |
Adaptive Group Testing on Networks with Community Structure |
| Authors |
Surin Ahn, Wei-Ning Chen, Ayfer Ozgur, Stanford University, United States |
| Session |
D3-S4-T3: Group Testing on Graphs |
| Chaired Session: |
Wednesday, 14 July, 23:00 - 23:20 |
| Engagement Session: |
Wednesday, 14 July, 23:20 - 23:40 |
| Abstract |
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.
|
