Optimizing the Structure of Diffusion Networks: Theory and Algorithms
Khalil, Elias B
MetadataShow full item record
How can we optimize the topology of a networked system to make it resilient to flus or malware, or also conducive to the spread of information and multimedia? Previous work on information diffusion has focused on modeling the diffusion dynamics and selecting nodes to maximize influence (e.g. by offering a product for free as part of a marketing campaign). Only a paucity of recent studies have attempted to address the network modification problems, where the goal is to either facilitate desirable spreads or curtail undesirable ones by adding or deleting a small subset of network nodes or edges, as opposed to simply seeding existing nodes. In this thesis, we focus on the widely studied linear threshold diffusion model, and prove, for the first time, that the network modification problems under this model have supermodular objective functions. This surprising property facilitates computational advancements on multiple fronts: it allows us to design efficient data structures and scalable algorithms with provable approximation guarantees, despite the hardness of the problems in question. Both the time and space complexities of our algorithms are linear in the size of the network, which allows us to experiment with networks of millions of nodes and edges. We show that our algorithms outperform an array of heuristics in terms of the effectiveness in controlling diffusion processes, often beating the next best by a significant margin.