Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations
Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations
复制标题
DOI：
10.1609/aaai.v28i1.8726
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Naoto Ohsaka;Takuya Akiba;Yuichi Yoshida;K. Kawarabayashi
中科院分区：
文献类型：
--
作者：
Naoto Ohsaka;Takuya Akiba;Yuichi Yoshida;K. Kawarabayashi
影响力最大化（英语：Influence maximization）是在随机级联传播模型下，在社会网络中寻找具有高度影响力的个体的小集合，以最大化影响力的传播。虽然这个问题已经得到了很好的研究，但在当今的大规模网络中找到高质量的解决方案仍然具有很大的挑战性。虽然基于蒙特-卡罗模拟的方法产生具有理论保证的接近最优的解决方案，但是它们对于大型图来说非常慢。因此，许多启发式方法没有任何理论保证已经开发，但他们都大大妥协的解决方案的质量。为了解决这个问题，我们提出了一个新的方法的影响最大化问题。与其他最近的启发式方法，所提出的方法是一个蒙特-卡罗模拟为基础的方法，因此，它始终产生高质量的解决方案的理论保证。另一方面，与其他以前的基于蒙特-卡罗模拟的方法不同，它运行速度与其他最先进的方法一样快，并且可以应用于当今的大型网络。通过我们广泛的实验，我们证明了所提出的方法的可扩展性和解决方案的质量。
Influence maximization is a problem to find small sets of highly influential individuals in a social network to maximize the spread of influence under stochastic cascade models of propagation. Although the problem has been well-studied, it is still highly challenging to find solutions of high quality in large-scale networks of the day. While Monte-Carlo-simulation-based methods produce near-optimal solutions with a theoretical guarantee, they are prohibitively slow for large graphs. As a result, many heuristic methods without any theoretical guarantee have been developed, but all of them substantially compromise solution quality. To address this issue, we propose a new method for the influence maximization problem. Unlike other recent heuristic methods, the proposed method is a Monte-Carlo-simulation-based method, and thus it consistently produces solutions of high quality with the theoretical guarantee. On the other hand, unlike other previous Monte-Carlo-simulation-based methods, it runs as fast as other state-of-the-art methods, and can be applied to large networks of the day. Through our extensive experiments, we demonstrate the scalability and the solution quality of the proposed method.