Models for virus detection in contact networks

Agrawal, Sudesh K.
Journal Title
Journal ISSN
Volume Title

We develop and analyze optimization models for rapid detection of viruses in large contact networks. In the model, a virus spreads in a stochastic manner over an undirected connected graph, under various assumptions on the spread dynamics. A decision maker must place a limited number of detectors on a subset of the nodes in the graph in order to rapidly detect infection of the nodes by the virus. The objective is to determine the placement of these detectors so as to either maximize the probability of detection within a given time period or minimize the expected time to detection. Previous work in this area assumed that the detectors are perfectly reliable. In this work, it is assumed that the detectors may produce false-negative results. In computational studies, the sample average approximation method is applied to solving the problem using a mixed-integer program and a greedy heuristic. The heuristic is shown to be highly efficient and to produce high-quality solutions. In addition, it is shown that the false-negative effect can sometimes be ignored, without significant loss of solution quality, in the original optimization formulation.

We also develop an agent-based disease spread model on a contact network, motivated by COVID-19, to proactively test staff to detect an outbreak of an epidemic in facilities of small to moderate size. In our computational experiments we compare the effect of network structure and testing protocols on the probability of detection.

Additionally, we extend our agent-based disease spread model to immunize staff in moderate-size facilities. We develop an immunization protocol and through computational studies show that it performs better than some existing protocols in the literature for static networks.