Modeling disease propagation in networks: source-finding and influence maximization
Po-Ling Loh (University of Wisconsin-Madison)
QB F101c (Queen's Building)
Abstract: We present several recent results concerning stochastic modeling of disease propagation over a network. In the first setting, nodes are infected one at a time, starting from a single infected individual, and the goal is to infer the source of the infection based on a snapshot of infected individuals. We show that if the underlying graph is a tree and possesses a certain regular structure, it is possible to construct confidence sets for the diffusion source with size independent of the number of infected nodes. Furthermore, the confidence sets we construct possess an attractive property of “persistence,” meaning they eventually settle down as the disease spreads over the network. In the second setting, nodes are infected in waves according to linear threshold or independent cascade models. We establish upper and lower bounds for the influence of a subset of nodes in the network, where the influence is defined as the expected number of infected nodes at the conclusion of the epidemic. We quantify the gap between our upper and lower bounds in the case of the linear threshold model and illustrate the gains of our upper bounds for independent cascade models in relation to existing results. Importantly, our lower bounds are monotonic and submodular, implying that a greedy algorithm for influence maximization is guaranteed to produce a maximizer within a 1-1/e factor of the truth. This is joint work with Justin Khim and Varun Jog.
Bio : Po-Ling grew up in the lovely town of Madison, Wisconsin. After graduating from Caltech with a BS in math and minor in English, she moved to UC Berkeley, where she subsequently earned an MS in computer science and PhD in statistics. From 2014–2016, She was an assistant professor in the Department of Statistics at the Wharton School of the University of Pennsylvania. She moved back to Madison in the summer of 2016.