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.