ABSTRACT
Virginia Bioinformatics Institute and Department of Computer Science, Virginia Tech
Eric J. Bohm and Abhishek Gupta
Department of Computer Science, University of Illinois at Urbana-Champaign
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 10.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
10.2.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 10.2.2 Application to Computational Epidemiology . . . . . . . . . . . 217
10.3 EpiSimdemics Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 10.3.1 The Disease Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 10.3.2 Modeling Behavior of Individual Agents . . . . . . . . . . . . . . . . 220 10.3.3 Intervention and Behavior Modification . . . . . . . . . . . . . . . . . 221 10.3.4 Social Network Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.4 EpiSimdemics Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 10.5 Charm++ Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
10.5.1 Designing the Chares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 10.5.2 The EpiSimdemics Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 10.5.3 Charm++ Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
10.6 Performance of EpiSimdemics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 10.6.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 10.6.2 Performance Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 10.6.3 Effects of Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 10.6.4 Effects of Strong Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 10.6.5 Effects of Weak Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 10.6.6 Effect of Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
10.7 Representative Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
Parallel Approach
Contagion is used here broadly to mean transmitted phenomena such as diseases, opinions, fads, trends, norms, packet diffusion, worm propagation in computer networks, database replication in sensor networks, spread of social movements and influence among peers to purchase music videos or go to movies [88, 165, 152, 94, 56, 36, 178]. The spread of contagions across a national population is a well known complex problem, and includes: (i) pandemics, such as H1N1 and swine influenza outbreaks in recent years, in which the spread of the flu virus is often modeled by stochastic processes, such as the SIR process [185, 59, 73], (ii) spread of information on online social media, such as Twitter and Facebook [207], which are often modeled by stochastic and threshold based models [133] and (iii) the 2003 blackout in Northeastern U.S., and the cascading effects on traffic, communication and other infrastructures that cost $6 billion [174]. A key observation from numerous studies shows that the underlying network structure has a significant impact on the dynamics [84, 221], and as in the case of the 2003 blackout, this could span multiple networks [184].
