License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.39
URN: urn:nbn:de:0030-drops-112542
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11254/
Go to the corresponding LIPIcs Volume Portal

Schoenebeck, Grant ; Tao, Biaoshuai ; Yu, Fang-Yi

Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization

pdf-format:
LIPIcs-APPROX-RANDOM-2019-39.pdf (0.7 MB)

Abstract

We study the r-complex 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 r-complex 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 well-studied 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 Fang-Yi 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:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11254},
  URN =		{urn:nbn:de:0030-drops-112542},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.39},
  annote =	{Keywords: Nonsubmodular Influence Maximization, Bootstrap Percolation, Stochastic Blockmodel}
}

Keywords: Nonsubmodular Influence Maximization, Bootstrap Percolation, Stochastic Blockmodel
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI