A Multi-criteria Approximation Algorithm for Influence Maximization with Probabilistic Guarantees
A Multi-criteria Approximation Algorithm for Influence Maximization with Probabilistic Guarantees
复制标题
具有概率保证的影响力最大化的多标准近似算法
DOI：
10.1137/1.9781611976007.7
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhang, Qin.
中科院分区：
文献类型：
--
作者：
Khan, Maleq;Pandurangan, Gopal;Dinh Pham, Nguyen;Vullikanti, Anil;Zhang, Qin.
研究充分的影响最大化问题涉及到选择一个给定大小的种子集，它最大化了预期的影响。然而，这样的解决方案可能具有实现低影响的显著概率，这可能不适合于许多应用。在本文中，我们考虑一种不同的方法：找到一个种子集，最大化的影响集大小与给定的概率。我们表明，这个目标是不是次模块化，并设计了一个贪婪的，多标准的近似算法，这个问题的严格近似保证。我们还在多个数据集上评估了我们的算法，并表明它们与优化预期影响的算法具有相似或更好的质量，但对概率有额外的保证。
The well-studied influence maximization problem involves choosing a seed set of a given size, which maximizes the expected influence. However, such solutions might have a significant probability of achieving low influence, which might not be suitable in many applications. In this paper, we consider a different approach: find a seed set that maximizes the influence set size with a given probability. We show that this objective is not submodular, and design a greedy, multi-criteria approximation algorithm for this problem with rigorous approximation guarantees. We also evaluate our algorithm on multiple datasets, and show that they have similar or better quality as the ones optimizing the expected influence, but with additional guarantees on the probability.