文章基本信息

标题：On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback
本地全文：下载
作者：Wei Chen ; Binghui Peng
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-19
DOI：10.4230/LIPIcs.ISAAC.2019.24
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we study the adaptivity gap of the influence maximization problem under the independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the in-arborescences is between [e/(e-1), 2e/(e-1)], and for the out-arborescences the gap is between [e/(e-1), 2]. These are the first constant upper bounds in the full-adoption feedback model. Our analysis provides several novel ideas to tackle the correlated feedback appearing in adaptive stochastic optimization, which may be of independent interest.
关键词：Adaptive influence maximization; adaptivity gap; full-adoption feedback