Academic

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.