Back to Search Start Over

Least-Cost Influence Maximization on Social Networks.

Authors :
Günneç, Dilek
Raghavan, S.
Zhang, Rui
Source :
INFORMS Journal on Computing. Spring2020, Vol. 32 Issue 2, p289-302. 14p.
Publication Year :
2020

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10919856
Volume :
32
Issue :
2
Database :
Academic Search Index
Journal :
INFORMS Journal on Computing
Publication Type :
Academic Journal
Accession number :
143098717
Full Text :
https://doi.org/10.1287/ijoc.2019.0886