Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks


Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks

Show full record

Title: Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks
Author: Lee, Jinho, doctor of operations research and industrial engineering
Abstract: 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 heuristic 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. Using data from a large carrier, we build several base cellphone contact networks of different scale. We then rescale these base networks using the so-called c-core decomposition that removes vertices of low degree in a recursive way. We further show that this down-sampling strategy preserves, in general, the topological properties of the base networks, based on testing several measures. For the objective that maximizes the probability that we detect a virus by a time threshold, we provide a sample-average optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. To choose a relevant time threshold, we perform a simulation for some spread models. We then test the performance of our proposed solution methods by solving the presented optimization models for some spread dynamics using some of the contact networks built after the c-core decomposition. The computational results show that the greedy algorithm is an efficient way to solve the corresponding sample-average approximation model, and the greedy solutions outperform some other simple solution approaches.
Department: Operations Research and Industrial Engineering
Subject: Submodularity Greedy heuristic Down-sampling procedure Monte Carlo approximation
Date: 2012-08

Files in this work

Download File: LEE-DISSERTATION.pdf
Size: 1.293Mb
Format: application/pdf

This work appears in the following Collection(s)

Show full record

Advanced Search


My Account