Least-cost influence maximization on social networks
dc.contributor.author | Danış, Dilek Günneç | |
dc.contributor.author | Raghavan, S. | |
dc.contributor.author | Zhang, R. | |
dc.date.accessioned | 2021-01-28T08:27:27Z | |
dc.date.available | 2021-01-28T08:27:27Z | |
dc.date.issued | 2020-03 | |
dc.identifier.issn | 1091-9856 | en_US |
dc.identifier.uri | http://hdl.handle.net/10679/7238 | |
dc.identifier.uri | https://pubsonline.informs.org/doi/pdf/10.1287/ijoc.2019.0886 | |
dc.description.abstract | Viral-marketing strategies are of significant interest in the online economy. Roughly, in these problems, one seeks to identify which individuals to strategically target in a social network so that a given proportion of the network is influenced at minimum cost. Earlier literature has focused primarily on problems where a fixed inducement is provided to those targeted. In contrast, resembling the practical viral-marketing setting, we consider this problem where one is allowed to "partially influence" (by the use of monetary inducements) those selected for targeting. We thus focus on the "least-cost influence problem (LCIP)": an influence-maximization problem where the goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentive) required to influence a given proportion of the population. Motivated by the desire to develop a better understanding of fundamental problems in social-network analytics, we seek to develop (exact) optimization approaches for the LCIP. Our paper makes several contributions, including (i) showing that the problem is NP-complete in general as well as under a wide variety of special conditions; (ii) providing an influence greedy algorithm to solve the problem polynomially on trees, where we require 100% adoption and all neighbors exert equal influence on a node; and (iii) a totally unimodular formulation for this tree case. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Informs | en_US |
dc.relation.ispartof | INFORMS Journal on Computing | |
dc.rights | restrictedAccess | |
dc.title | Least-cost influence maximization on social networks | en_US |
dc.type | Article | en_US |
dc.peerreviewed | yes | en_US |
dc.publicationstatus | Published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0002-0749-2584 & YÖK ID 121183) Günneç, Dilek | |
dc.contributor.ozuauthor | Danış, Dilek Günneç | |
dc.identifier.volume | 32 | en_US |
dc.identifier.issue | 2 | en_US |
dc.identifier.startpage | 289 | en_US |
dc.identifier.endpage | 302 | en_US |
dc.identifier.wos | WOS:000531097900008 | |
dc.identifier.doi | 10.1287/ijoc.2019.0886 | en_US |
dc.subject.keywords | Social networks | en_US |
dc.subject.keywords | Influence maximization | en_US |
dc.subject.keywords | Complexity | en_US |
dc.subject.keywords | Integer programming | en_US |
dc.subject.keywords | Strong formulation | en_US |
dc.subject.keywords | Greedy algorithm | en_US |
dc.identifier.scopus | SCOPUS:2-s2.0-85089414736 | |
dc.contributor.authorFemale | 1 | |
dc.relation.publicationcategory | Article - International Refereed Journal - Institutional Academic Staff |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Share this page