CAREER: Algorithms for Controlling Epidemic Phenomena in Networks

当传染病、计算机病毒、行为、信息或创新以高度分散和并行的方式沿着社会或计算机网络的链接传播时，网络中的流行病现象就会发生。流行病现象往往对社会产生强烈的影响。疾病和计算机病毒造成人类生命损失和经济损失。通过模仿或胁迫传播的行为模式可以是可取的，也可以是不可取的。一项创新或一条信息可以改善生活质量，或增加公司的销售收入。 因此，必须研究如何利用人们对流行病的有限控制。在有害流行病的情况下，这包括疫苗接种、防病毒软件部署和其他政策决定。为了传播创新，必须选择有效的“口碑营销”战略（如确定有影响力的个人）。为了传播信息，需要设计有效的网络协议，鉴于有关社会和计算机网络的数据越来越详细，准确地模拟这种流行病现象并通过算法解决最小化或最大化网络中流行病传播的问题变得可行。 与遏制流行病有关的问题导致新的图切割优化问题，而最大化问题与图覆盖有关。当多种影响相互竞争时，问题就具有博弈论的成分，在许多情况下，流行病的模型是基于马尔可夫链和随机图的。研究人员将研究算法与可证明的保证问题的最小化或最大化的流行病的传播。

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.