论文标题
通过简单的贪婪策略改善了自适应影响最大化的近似因素
Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies
论文作者
论文摘要
在自适应影响最大化问题中，我们获得了一个社交网络和一个预算$ k $，并且我们迭代选择了$ k $节点，称为种子，以最大程度地提高影响级联的预期节点数量，这些节点是由它们根据随机模型而产生的影响级联的，以实现影响扩散。与非自适应影响最大化问题不同，必须事先选择所有种子，此处是一一依次选择节点，并且对$ i $ th种子的决定基于第一个$ i-1 $种子所观察到的级联。我们专注于近视反馈模型，在这种模型中，我们只能观察到以前选择的种子的哪些邻居受到了影响，并且在独立的级联模型上，其中每个边缘都与扩散影响的独立概率相关联。先前的工作表明，适应性差距最多为$ 4 $，这意味着非自适应贪婪算法保证了$ \ frac {1} {1} {4} {4} \ left（1- \ frac {1} {1} {e} {e} {e} \ right）$用于适应性问题。在本文中，我们提高了适应性差距和近似因子的边界。我们直接分析了非自适应贪婪算法的近似因子，而无需通过适应性差距，并表明它至少是$ \ frac {1} {2} {2} \ left（1- \ frac {1} {1} {e} {e} {e} {e} \ right）$。因此，自适应间隙最多是$ \ frac {2e} {e-1} \大约3.164 $。为了证明这些界限，我们引入了一种新方法，将贪婪的非自适应算法与自适应最佳相关联。新方法不依赖于多线性扩展或在最佳决策树上随机步行，这些决策树是该领域常用技术。我们认为，它具有独立的兴趣，可用于分析其他自适应优化问题。
In the adaptive influence maximization problem, we are given a social network and a budget $k$, and we iteratively select $k$ nodes, called seeds, in order to maximize the expected number of nodes that are reached by an influence cascade that they generate according to a stochastic model for influence diffusion. Differently from the non-adaptive influence maximization problem, where all the seeds must be selected beforehand, here nodes are selected sequentially one by one, and the decision on the $i$th seed is based on the observed cascade produced by the first $i-1$ seeds. We focus on the myopic feedback model, in which we can only observe which neighbors of previously selected seeds have been influenced and on the independent cascade model, where each edge is associated with an independent probability of diffusing influence. Previous works showed that the adaptivity gap is at most $4$, which implies that the non-adaptive greedy algorithm guarantees an approximation factor of $\frac{1}{4}\left(1-\frac{1}{e}\right)$ for the adaptive problem. In this paper, we improve the bounds on both the adaptivity gap and on the approximation factor. We directly analyze the approximation factor of the non-adaptive greedy algorithm, without passing through the adaptivity gap, and show that it is at least $\frac{1}{2}\left(1-\frac{1}{e}\right)$. Therefore, the adaptivity gap is at most $\frac{2e}{e-1}\approx 3.164$. To prove these bounds, we introduce a new approach to relate the greedy non-adaptive algorithm to the adaptive optimum. The new approach does not rely on multi-linear extensions or random walks on optimal decision trees, which are commonly used techniques in the field. We believe that it is of independent interest and may be used to analyze other adaptive optimization problems.
