Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks


J. Lee, Hasenbein, J. J., and Morton, D. P., “Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks,” 2011.


We develop a class of models to represent the dynamics of a virus spreading in a cellphone network, employing a taxonomy that includes five key characteristics. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus, subject to resource limitations. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection, which can be applied to all spread models we consider. We establish a submodularity result for these two objective functions that ensures that a greedy algorithm yields a well-known constant-factor (63%) approximation. We relate the latter optimization problem, under a specific virus-spread mechanism from our class of models, to a classic facility-location model. And, for the former objective function, we provide a sample-path optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. Finally, using call data from a large carrier, we estimate the degree distribution in a contact network, which is central to building random networks to study our models and solution methods.