Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks


Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks

Show simple record

dc.contributor.advisor Morton, David P.
dc.contributor.advisor Hasenbein, John J.
dc.creator Lee, Jinho, doctor of operations research and industrial engineering 2012-11-20T19:35:20Z 2012-11-20T19:35:20Z 2012-08 2012-11-20 August 2012
dc.description.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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subject Submodularity
dc.subject Greedy heuristic
dc.subject Down-sampling procedure
dc.subject Monte Carlo approximation
dc.title Stochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks 2012-11-20T19:35:29Z
dc.identifier.slug 2152/ETD-UT-2012-08-5924
dc.contributor.committeeMember Popova, Elmira
dc.contributor.committeeMember Kutanoglu, Erhan
dc.contributor.committeeMember Shakkottai, Sanjay
dc.description.department Operations Research and Industrial Engineering
dc.type.genre thesis
dc.type.material text Operations Research and Industrial Engineering Operations Research and Industrial Engineering University of Texas at Austin Doctoral Doctor of Philosophy

Files in this work

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

This work appears in the following Collection(s)

Show simple record

Advanced Search


My Account