Epidemics on Large Social Contact Graphs: Algorithmic Challenges

Anil Vullikanti, Virginia Tech

September 18, 2008 @ 05:00 pm to 06:00 pm

100 Life Sciences Building

Event Website

Senior Research Associate, Network Dynamics and Simulation Science Laboratory, VBI Assistant Professor, Department of Computer Science, Virginia Tech ABSTRACT: In recent years, there has been a lot of interest in studying epidemic models on realistic contact graphs. This poses new challenges, as a result of the very large size of these networks and their irregular structure. We focus on the algorithmic aspects of the problems arising out of the simulation of epidemics and the design of interventions to control their spread. Stochastic discrete event simulations are commonly used for studying epidemics on complex networks because of the difficulty with analytical methods, and these do not scale very well on large networks. We will discuss a new algorithm, FastDiffuse, that is based on an extension of classical percolation techniques to directed weighted graphs. This algorithm provably matches discrete event simulations and runs in linear time, leading to very fast simulations of disease dynamics on arbitrary networks. We will also discuss algorithms for solving optimization problems related to quarantining and vaccination in such networks, and show that the faster epidemic simulations lead to new and potentially more effective strategies for such interventions.

Contact

Megan Matthews
mam75@psu.edu
863-3650