Optimization of stochastic virus detection in contact networks

We develop network models to represent the dynamics of a virus spreading in a contact network. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus. We consider two goals, maximizing the probability of detecting a virus by a time threshold...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2015-01, Vol.43 (1), p.59-64
Main Authors: Lee, Jinho, Hasenbein, John J., Morton, David P.
Format: Article
Language:English
Subjects:
Contact
Dynamics
Mathematical models
Networks
Operations research
Optimization
Spreading
Spreads
Stochastic integer programming
Stochastic spread model
Submodular optimization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We develop network models to represent the dynamics of a virus spreading in a contact network. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection. We establish submodularity results for these objective functions and, using data from a mobile service provider, we show that a greedy heuristic performs surprisingly well.
ISSN:0167-6377
1872-7468
DOI:10.1016/j.orl.2014.11.006