Georgia Institute of Technology
Optimizing the Structure of Diffusion Networks: Theory and Algorithms
Abstract
dc:description.abstractHow 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.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Khalil, Elias B.
- Advisor dc:contributor.advisor
-
- Song, Le
- Committee members dc:contributor.committeemember
-
- Dilkina, Bistra
- Chau, Duen Horng (Polo)
Subjects
dc:subject × 10Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/55481