A branch‐and‐cut approach for the least cost influence problem on social networks

Name: A branch‐and‐cut approach for the least cost influence problem on social networks
Author: Danış, Dilek Günneç, Raghavan, S., Zhang, R.

İsim	A branch‐and‐cut approach for the least cost influence problem on social networks
Yazar	Danış, Dilek Günneç, Raghavan, S., Zhang, R.
Basım Tarihi:	2020-07
Basım Yeri	- Wiley
Konu	Exact method, Influence maximization, Integer programming, Strong formulation
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0028-3045
Kayıt Numarası	adb592e2-f28e-4da1-a1a7-7f0def5af56a
Lokasyon	Industrial Engineering
Tarih	2020-07
Örnek Metin	This paper studies a problem in the online targeted marketing setting called the least cost influence problem (LCIP) that is known to be NP-hard. The goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentives) required to influence a given population. We develop a branch-and-cut approach to solve this LCIP on arbitrary graphs. We build upon Gunnec et al.'s novel totally unimodular (TU) formulation for the LCIP on trees. The key observation in applying this TU formulation to arbitrary graphs is to enforce an exponential set of inequalities that ensure the influence propagation network is acyclic. We also design several enhancements to the branch-and-cut procedure that improve its performance. We provide a large set of computational experiments on real-world graphs with up to 155 000 nodes and 327 000 edges that demonstrates the efficacy of the branch-and-cut approach. This branch-and-cut approach finds solutions that are on average 1.87% away from optimality based on a test-bed of 160 real-world graph instances. We also develop a heuristic that prioritizes nodes that receive low influence from their peers. This heuristic works particularly well on arbitrary graphs, providing solutions that are on average 1.99% away from optimality. Finally, we observe that partial incentives can result in significant cost savings, over 55% on average, compared to the setting where partial incentives are not allowed.
DOI	10.1002/net.21941
Cilt	76

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

A branch‐and‐cut approach for the least cost influence problem on social networks

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

Basım Tarihi 2020-07

Basım Yeri - Wiley

Konu Exact method, Influence maximization, Integer programming, Strong formulation

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0028-3045

Kayıt Numarası adb592e2-f28e-4da1-a1a7-7f0def5af56a

Lokasyon Industrial Engineering

Tarih 2020-07

Örnek Metin This paper studies a problem in the online targeted marketing setting called the least cost influence problem (LCIP) that is known to be NP-hard. The goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentives) required to influence a given population. We develop a branch-and-cut approach to solve this LCIP on arbitrary graphs. We build upon Gunnec et al.'s novel totally unimodular (TU) formulation for the LCIP on trees. The key observation in applying this TU formulation to arbitrary graphs is to enforce an exponential set of inequalities that ensure the influence propagation network is acyclic. We also design several enhancements to the branch-and-cut procedure that improve its performance. We provide a large set of computational experiments on real-world graphs with up to 155 000 nodes and 327 000 edges that demonstrates the efficacy of the branch-and-cut approach. This branch-and-cut approach finds solutions that are on average 1.87% away from optimality based on a test-bed of 160 real-world graph instances. We also develop a heuristic that prioritizes nodes that receive low influence from their peers. This heuristic works particularly well on arbitrary graphs, providing solutions that are on average 1.99% away from optimality. Finally, we observe that partial incentives can result in significant cost savings, over 55% on average, compared to the setting where partial incentives are not allowed.

DOI 10.1002/net.21941

Cilt 76