Abstract: Diffusion processes over an underlying network can be used to describe a variety of dynamic phenomena, including the spread of social influence or information, infectious disease propagation, spatial conservation planning, and river network optimization. At a high level, a subset of nodes in the network, called source nodes, are infected at the beginning of the diffusion process, and at each time step infected nodes may infect their neighbors with some probability. A classic question is -- how can we select the source nodes (or alter the source nodes given a budget) to maximize/minimize the number of infected nodes within a time horizon. More recently, researchers have investigated the use of additional intervention actions that alter the underlying network with some cost to further optimize their objective. In this talk I will give a brief overview of a popular model for this problem, the Independent Cascade (IC) model, and review existing results on the existence of an FPTAS for this problem under the IC regime when the underlying network is a tree.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.