Document Type


Date of Degree


Degree Name

PhD (Doctor of Philosophy)

Degree In

Computer Science

First Advisor

Sriram Pemmaraju


Social networks encode important information about the relationships between individuals. The structure of social networks has important implications for how ideas, information, and even diseases spread within a population. Data on online social networks is becoming increasingly available, but fine-grained data from which physical proximity networks can be inferred is still a largely elusive goal. We address this problem by using nearly 20 million anonymized login records from University of Iowa Hospitals and Clinics to construct healthcare worker (HCW) contact networks. These networks serve as proxies for potentially disease-spreading contact patterns among HCWs. We show that these networks exhibit properties similar to social networks arising in other contexts (e.g., scientific collaboration, friendship, etc.) such as the "Six Degrees of Kevin Bacon" (i.e., small-world) phenomenon. In order to develop a theoretic framework for analyzing these HCW contact networks we consider a number of random graph models and show that models which only pay attention to local structure may not adequately model disease spread. We then consider the best known approximation algorithms for a number of optimization problems that model the problem of determining an optimal set of HCWs to vaccinate in order to minimize the spread of disease. Our results show that, in general, the quality of solutions produced by these approximations is highly dependent on the dynamics of disease spread. However, experiments show that simple policies, like vaccinating the most well-connected or most mobile individuals, perform much better than a random vaccination policy. And finally we consider the problem of finding a set of individuals to act as indicators for important healthcare related events on a social network for infectious disease experts. We model this problem as a generalization of the budgeted maximum coverage problem studied previously and show that in fact our problem is much more difficult to solve in general. But by exposing a property of this network, we provide analysis showing that a simple greedy approach for picking indicators provides a near-optimal (constant-factor) approximation.


Infectious Disease, Modeling, Optimization Algorithms, Social Networks


xv, 194 pages


Includes bibliographical references (pages 185-194).


Copyright 2011 Donald Ephraim Curtis