论文标题
最大化影响：分析激活概率计算方法
Maximizing the Influence: Analytic Activation Probability Computation Approach
论文作者
论文摘要
影响最大化是在网络中找到最有影响力的个体的子集的问题。社交网络对信息传播和病毒营销的发展的影响使这个问题成为许多研究的主题。影响最大化是$ \ np $ - hard，并且已经提出了许多贪婪的算法来解决该问题。 在本文中，我们提出了一种贪婪的算法，该算法通过使用新颖的分析激活概率计算方法近似影响。我们提出了一个非线性方程系统来计算比最新技术更准确的激活概率。此外，我们提出了一种有效计算激活概率的方法，以减少算法的运行时间。 我们在一些现实世界数据集上检查了我们提出的方法。我们的实验表明，所提出的算法通过计算更准确的激活概率来优于先前的作品。此外，我们的有效方法在运行时有很大的改进，因此很容易在大型网络上缩放。
Influence maximization is the problem of finding a subset of the most influential individuals in a network. The impact of social networks on the dissemination of information and the development of viral marketing has made this problem as the subject of many studies. Influence maximization is $\NP$-hard and many greedy algorithms have been proposed to solve the problem. In this paper we propose a greedy algorithm that approximates the influence by using a novel analytic activation probability computation method. We propose a nonlinear system of equations to compute the activation probabilities which is more accurate than state-of-the-arts. Moreover, we propose a method to compute the activation probabilities efficiently, in order to reduce the running time of the algorithm. We examine our proposed methods on some real-world data sets. Our experiments demonstrate that the proposed algorithms outperform the previous works by computing more accurate activation probabilities. In addition, Our efficient method has much improvements on the running-time, so it can be easily scaled on large networks.
