Show simple item record

dc.contributor.authorSwaminathan, Ananden_US
dc.date.accessioned2014-07-04T08:00:24Z
dc.date.available2014-07-04T08:00:24Z
dc.date.issued2014-07-03en_US
dc.identifier.othervt_gsexam:3098en_US
dc.identifier.urihttp://hdl.handle.net/10919/49381
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_US
dc.format.mediumETDen_US
dc.publisherVirginia Techen_US
dc.rightsThis Item is protected by copyright and/or related rights. Some uses of this Item may be deemed fair and permitted by law even without permission from the rights holder(s), or the rights holder(s) may have licensed the work for use under certain conditions. For other uses you need to obtain permission from the rights holder(s).en_US
dc.subjectInfluence maximizationen_US
dc.subjectcomplex contagionen_US
dc.subjectlinear thresholden_US
dc.titleAn Algorithm for Influence Maximization and Target Set Selection for the Deterministic Linear Threshold Modelen_US
dc.typeThesisen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelmastersen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Science and Applicationsen_US
dc.contributor.committeechairMarathe, Madhav Vishnuen_US
dc.contributor.committeememberBisset, Keith R.en_US
dc.contributor.committeememberVullikanti, Anil Kumar S.en_US
dc.contributor.committeememberKuhlman, Christopher Jamesen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record