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

DOI10.1137/20M1377874zbMATH Open1490.92072arXiv2011.01998OpenAlexW3097532460MaRDI QIDQ5073508FDOQ5073508

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)

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.

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

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

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)

Cites Work

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

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)