HotCSE Seminar
Computational Science & Engineering
Monday February 09, 12pm-1pm, 1116-E Klaus

Scalable Diffusion-Aware Optimization of Network Topology

Elias Khalil
Advisor: Prof. Bistra Dilkina

ABSTRACT

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.

BIO

Elias Khalil is a first-year Ph.D. student in CSE, working with Prof. Bistra Dilkina and Prof. Le Song. His research interests are in discrete optimization, machine learning and networks. Elias holds an M.S. from Georgia Tech, and a B.S. from the American University of Beirut, Lebanon, both in Computer Science.