Schoenebeck, Grant ;
Tao, Biaoshuai ;
Yu, FangYi
Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
Abstract
We study the rcomplex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the rcomplex contagion model, each uninfected vertex in the network becomes infected if it has at least r infected neighbors.
In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the wellstudied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability omega (n^{(1+1/r)}), under certain mild assumptions, we prove that the optimal seeding strategy is to put all the seeds in a single community. This matches the intuition that in a nonsubmodular cascade model placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e.g., the independent cascade model and the linear threshold model) in which nearby seeds tend to erode each others' effects.
Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in omega (n^{(1+1/r)}) or in o (n^{2}).
BibTeX  Entry
@InProceedings{schoenebeck_et_al:LIPIcs:2019:11254,
author = {Grant Schoenebeck and Biaoshuai Tao and FangYi Yu},
title = {{Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {39:139:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11254},
URN = {urn:nbn:de:0030drops112542},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.39},
annote = {Keywords: Nonsubmodular Influence Maximization, Bootstrap Percolation, Stochastic Blockmodel}
}
17.09.2019
Keywords: 

Nonsubmodular Influence Maximization, Bootstrap Percolation, Stochastic Blockmodel 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 