Influence maximization in stochastic and adversarial settings

Abstract:
We consider the problem of influence maximization in fixed networks, for both stochastic and adversarial contagion models. In the stochastic 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. In the adversarial setting, an adversary is allowed to specify the edges through which contagion may spread, and the player chooses sets of nodes to infect in successive rounds. We establish upper and lower bounds on the pseudo-regret for possibly stochastic strategies of the adversary and player. This is joint work with Justin Khim and Varun Jog.

Biography:
Po-Ling Loh is an assistant professor in the ECE department at the UW-Madison, with a secondary appointment in statistics, and an affiliate of the Grainger Institute and Wisconsin Institute for Discovery. From 2014-2016, Po-Ling was an assistant professor in the statistics department at the Wharton School at the University of Pennsylvania. Po-Ling received an MS in computer science and a PhD in statistics from Berkeley in 2013 and 2014, and a BS in math with a minor in English from Caltech in 2009. She was the recipient of the 2014 Erich L. Lehmann Citation from the Berkeley statistics department for an outstanding PhD dissertation in theoretical statistics, and a best student paper award at the NIPS conference in 2012.