  In the context of a pandemic like COVID-19, and until most people are
vaccinated, proactive testing and interventions have been proved to be the only
means to contain the disease spread. Recent academic work has offered
significant evidence in this regard, but a critical question is still open: Can
we accurately identify all new infections that happen every day, without this
being forbiddingly expensive, i.e., using only a fraction of the tests needed
to test everyone everyday (complete testing)? Group testing offers a powerful
toolset for minimizing the number of tests, but it does not account for the
time dynamics behind the infections. Moreover, it typically assumes that people
are infected independently, while infections are governed by community spread.
Epidemiology, on the other hand, does explore time dynamics and community
correlations through the well-established continuous-time SIR stochastic
network model, but the standard model does not incorporate discrete-time
testing and interventions. In this paper, we introduce a "discrete-time SIR
stochastic block model" that also allows for group testing and interventions on
a daily basis. Our model can be regarded as a discrete version of the
continuous-time SIR stochastic network model over a specific type of weighted
graph that captures the underlying community structure. We analyze that model
w.r.t. the minimum number of group tests needed everyday to identify all
infections with vanishing error probability. We find that one can leverage the
knowledge of the community and the model to inform nonadaptive group testing
algorithms that are order-optimal, and therefore achieve the same performance
as complete testing using a much smaller number of tests.
