Least-cost influence maximization on social networks

Name: Least-cost influence maximization on social networks
Author: Danış, Dilek Günneç, Raghavan, S., Zhang, R.

İsim	Least-cost influence maximization on social networks
Yazar	Danış, Dilek Günneç, Raghavan, S., Zhang, R.
Basım Tarihi:	2020-03
Basım Yeri	- Informs
Konu	Social networks, Influence maximization, Complexity, Integer programming, Strong formulation, Greedy algorithm
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1091-9856
Kayıt Numarası	9a1f6877-2e18-4199-a5a6-11e876201247
Lokasyon	Industrial Engineering
Tarih	2020-03
Örnek Metin	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.
DOI	10.1287/ijoc.2019.0886
Cilt	32

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Least-cost influence maximization on social networks

Yazar Danış, Dilek Günneç, Raghavan, S., Zhang, R.

Basım Tarihi 2020-03

Basım Yeri - Informs

Konu Social networks, Influence maximization, Complexity, Integer programming, Strong formulation, Greedy algorithm

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1091-9856

Kayıt Numarası 9a1f6877-2e18-4199-a5a6-11e876201247

Lokasyon Industrial Engineering

Tarih 2020-03

Örnek Metin 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.

DOI 10.1287/ijoc.2019.0886

Cilt 32