Adaptive test allocation for outbreak detection and tracking in social contact networks

DOI10.1137/20M1377874MaRDI QIDQ5073508zbMATH OpenOpenAlexFDO

Authors Pau Batlle, Joan Bruna, Carlos Fernandez-Granda, Victor M. Preciado

Publication date 3 May 2022

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.01998

zbMATH Keywords

social networksepidemiologyMarkov chainssubmodular optimizationentropy-based sampling

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Epidemiology (92D30) Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30)

Abstract: 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.

Recommendations

• Optimization of stochastic virus detection in contact networks
• Adaptive group testing in a compartmental model of COVID-19
• Optimal test allocation
• How optimal allocation of limited testing capacity changes epidemic dynamics
• Optimising SARS-CoV-2 pooled testing strategies on social networks for low-resource settings

Cites work

• scientific article; zbMATH DE number 196128 (Why is no real title available?)
• An analysis of approximations for maximizing submodular set functions—I
• An analysis of the greedy algorithm for the submodular set covering problem
• Analysis and Control of Epidemics: A Survey of Spreading Processes on Complex Networks
• Bayesian experimental design: A review
• Generalized Submodular Information Measures: Theoretical Properties, Examples, Optimization Algorithms, and Applications
• Mathematics of epidemics on networks. From exact to approximate models
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Rumors in a Network: Who's the Culprit?
• Submodular functions and optimization.
• What's in a crowd? Analysis of face-to-face behavioral networks

Cited in

(4)

• Optimal adaptive testing for epidemic control: combining molecular and serology tests
• Parameter estimation in epidemic spread networks using limited measurements
• Optimising SARS-CoV-2 pooled testing strategies on social networks for low-resource settings
• Optimization of stochastic virus detection in contact networks

This page was built for publication: Adaptive test allocation for outbreak detection and tracking in social contact networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5073508)