Show simple item record

dc.contributor.authorSwaminathan, Ananden
dc.date.accessioned2014-07-04T08:00:24Zen
dc.date.available2014-07-04T08:00:24Zen
dc.date.issued2014-07-03en
dc.identifier.othervt_gsexam:3098en
dc.identifier.urihttp://hdl.handle.net/10919/49381en
dc.description.abstractThe problem of influence maximization has been studied extensively with applications that include viral marketing, recommendations, and feed ranking. The optimization problem, first formulated by Kempe, Kleinberg and Tardos, is known to be NP-hard. Thus, several heuristics have been proposed to solve this problem. This thesis studies the problem of influence maximization under the deterministic linear threshold model and presents a novel heuristic for finding influential nodes in a graph with the goal of maximizing contagion spread that emanates from these influential nodes. Inputs to our algorithm include edge weights and vertex thresholds. The threshold difference greedy algorithm presented in this thesis takes into account both the edge weights as well as vertex thresholds in computing influence of a node. The threshold difference greedy algorithm is evaluated on 14 real-world networks. Results demonstrate that the new algorithm performs consistently better than the seven other heuristics that we evaluated in terms of final spread size. The threshold difference greedy algorithm has tuneable parameters which can make the algorithm run faster. As a part of the approach, the algorithm also computes the infected nodes in the graph. This eliminates the need for running simulations to determine the spread size from the influential nodes. We also study the target set selection problem with our algorithm. In this problem, the final spread size is specified and a seed (or influential) set is computed that will generate the required spread size.en
dc.format.mediumETDen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectInfluence maximizationen
dc.subjectcomplex contagionen
dc.subjectlinear thresholden
dc.titleAn Algorithm for Influence Maximization and Target Set Selection for the Deterministic Linear Threshold Modelen
dc.typeThesisen
dc.contributor.departmentComputer Scienceen
dc.description.degreeMaster of Scienceen
thesis.degree.nameMaster of Scienceen
thesis.degree.levelmastersen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.disciplineComputer Science and Applicationsen
dc.contributor.committeechairMarathe, Madhav Vishnuen
dc.contributor.committeememberBisset, Keith R.en
dc.contributor.committeememberVullikanti, Anil Kumar S.en
dc.contributor.committeememberKuhlman, Christopher Jamesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record