论文标题
全面反馈下的影响最大化的适应性差距更好地界定
Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
论文作者
论文摘要
在影响最大化（IM）问题中，我们获得了一个社交网络和一个预算$ K $，我们在网络中寻找一组$ K $的节点，称为种子，可最大程度地提高了由种子产生的影响级联的预期节点数量。在本文中，我们研究了自适应IM，其中逐个选择节点，并且对$ i $ th种子的决定可以基于第一个$ I-1 $种子所观察到的级联。我们专注于全面反馈，在这些反馈中，我们可以观察到每个先前选择的种子的整个级联反馈以及独立的级联模型，其中每个边缘都与扩散影响的独立概率相关联。 我们的主要结果是任何图表都具有的第一个子线性上限。具体来说，我们表明适应性差距由$ \ lceil n^{1/3} \ rceil $限制，其中$ n $是图中的节点的数量。此外，我们从$ \ frac {2e} {e-1} \ 3.16 $到$ \ frac {2e^2} {e^2-1} \大约2.31 $的$ \ frac {2e} {e-1} \大约3.16 $改进了已知的上限。最后，我们研究了$α$结合的图，这是一类无向图，其中最多$α$的节点度的总和高于两个，并表明适应性差距在$ \sqrtα+o（1）$上受到上限。此外，我们表明，在0键的图中，即每个连接的组件是一个路径或周期的无方向图，自适应间隙最多是$ \ frac {3e^3} {e^3-1} \大约3.16 $。为了证明我们的界限，我们介绍了新技术，以将适应性政策与非适应性政策联系起来，这些政策可能是他们自身感兴趣的。
In the influence maximization (IM) problem, we are given a social network and a budget $k$, and we look for a set of $k$ nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. In this paper, we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the $i$th seed can be based on the observed cascade produced by the first $i-1$ seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by $\lceil n^{1/3}\rceil $, where $n$ is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from $\frac{2e}{e-1}\approx 3.16$ to $\frac{2e^2}{e^2-1}\approx 2.31$. Finally, we study $α$-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most $α$, and show that the adaptivity gap is upper-bounded by $\sqrtα+O(1)$. Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most $\frac{3e^3}{e^3-1}\approx 3.16$. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.
