Scalable Diffusion-Aware Optimization of Network Topology

How can we optimize the topology of a network (graph) to bring a flu under control, propel a video to virality, or stifle a network malware in its infancy? To answer these questions, I will present algorithms that optimize the structure of a diffusion network, by deleting/adding edges. Our setting poses a number of theoretical and algorithmic challenges, which are overcome by a deep analysis of the “linear threshold” diffusion model, the design of efficient data structures, and randomized subroutines. Our algorithms scale linearly in the size of the input network, and have approximation guarantees as to the solution quality. Experimentally, the algorithms outperform an array of heuristics in terms of their effectiveness in controlling diffusion processes, often beating the next best by a significant margin on networks with millions of nodes. Joint work with Prof. Dilkina and Prof. Song, presented at KDD 2014.