Back to search

Georgia Institute of Technology

Optimizing the Structure of Diffusion Networks: Theory and Algorithms

Abstract

dc:description.abstract

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.

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 × 10

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/55481

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Khalil, Elias B.. Optimizing the Structure of Diffusion Networks: Theory and Algorithms. Masters thesis, Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/55481