Least-Cost Influence Maximization on Social Networks

Dilek Günneç (), S. Raghavan () and Rui Zhanga ()
Additional contact information
Dilek Günneç: Department of Industrial Engineering, Ozyegin University, Istanbul 34794, Turkey
S. Raghavan: Robert H. Smith School of Business and Institute for Systems Research, University of Maryland, College Park, Maryland 20742
Rui Zhanga: Leeds School of Business, University of Colorado, Boulder, Colorado 80309

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 289-302

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.

Keywords: social networks; influence maximization; complexity; integer programming; strong formulation; greedy algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0886 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:2:p:289-302

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().