CAREER: Algorithms for Controlling Epidemic Phenomena in Networks

University Of Southern California, Los Angeles CA

Investigators

Abstract

Epidemic phenomena in networks occur when an infectious disease, computer virus, behavior, piece of information, or innovation is disseminated in a highly decentralized and parallel way along the links of a social or computer network. Epidemic phenomena often have a strong effect on society. Diseases and computer viruses cause the loss of human lives and economic damage. Behavioral patterns, spread by imitation or coercion, can be desirable or undesirable. An innovation or piece of information can lead to improvements in quality of life, or to increased sales revenue for a company. It is thus crucial to study ways of leveraging the limited control one has over epidemics. In the case of harmful epidemics, this includes vaccinations, anti-virus software deployment, and other policy decisions. For the diffusion of innovations, effective "word-of-mouth marketing" strategies (such as identifying influential individuals) must be chosen. For the dissemination of information, efficient network protocols need to be designed. Given the increasingly detailed data available about social and computer networks, it is becoming feasible to model such epidemic phenomena accurately, and to address algorithmically the problems of minimizing or maximizing the spread of an epidemic in a network. Problems relating to the containment of epidemics lead to novel graph cut optimization problems, while maximization problems relate to graph covering. When multiple influences are competing, the problems take on a game-theoretic component, and in many cases, the models for epidemics are based on Markov Chains and random graphs. The investigator will study algorithms with provable guarantees for the problems of minimizing or maximizing the spread of epidemics.