  We present a general framework for adaptive allocation of viral tests in
social contact networks. We pose and solve several complementary problems.
First, we consider the design of a social sensing system whose objective is the
early detection of a novel epidemic outbreak. In particular, we propose an
algorithm to select a subset of individuals to be tested in order to detect the
onset of an epidemic outbreak as fast as possible. We pose this problem as a
hitting time probability maximization problem and use submodularity
optimization techniques to derive explicit quality guarantees for the proposed
solution. Second, once an epidemic outbreak has been detected, we consider the
problem of adaptively distributing viral tests over time in order to maximize
the information gained about the current state of the epidemic. We formalize
this problem in terms of information entropy and mutual information and propose
an adaptive allocation strategy with quality guarantees. For these problems, we
derive analytical solutions for any stochastic compartmental epidemic model
with Markovian dynamics, as well as efficient Monte-Carlo-based algorithms for
non-Markovian dynamics. Finally, we illustrate the performance of the proposed
framework in numerical experiments involving a model of Covid-19 applied to a
real human contact network.
