Show simple item record

dc.contributor.advisorSong, Le
dc.contributor.authorKhalil, Elias B.
dc.date.accessioned2016-08-22T12:19:28Z
dc.date.available2016-08-22T12:19:28Z
dc.date.created2014-05
dc.date.issued2014-04-09
dc.date.submittedMay 2014
dc.identifier.urihttp://hdl.handle.net/1853/55481
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.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectNetworks
dc.subjectSubmodularity
dc.subjectSupermodularity
dc.subjectOptimization
dc.subjectDiffusion of innovations
dc.subjectEpidemics
dc.subjectGraph theory
dc.subjectAlgorithms
dc.subjectSocial networks
dc.subjectInformation networks
dc.titleOptimizing the Structure of Diffusion Networks: Theory and Algorithms
dc.typeThesis
dc.description.degreeM.S.
dc.contributor.departmentComputer Science
thesis.degree.levelMasters
dc.contributor.committeeMemberDilkina, Bistra
dc.contributor.committeeMemberChau, Duen Horng (Polo)
dc.date.updated2016-08-22T12:19:28Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record