In-time estimation for influence maximization in large-scale social networks

Abstract

Influence Maximization aims to find the top-K influential individuals to maximize the influence spread within a social network, which remains an important yet challenging problem. Most of the existing studies focus on greedy algorithms and mainly suffer from low computational efficiency, limiting its application to real-world social networks. In this paper, we propose a novel approach ESMCE that can significantly reduce the running time. Utilizing a power-law exponent supervised Monte Carlo method, ESMCE is able to efficiently estimate the influence spread for nodes with specified precision by randomly sampling only a small portion of child nodes, thus is well suitable for large-scale social networks. Extensive experiments on five real-world social network demonstrate that, compared with state-of-the-art influence maximization algorithms, ESMCE is able to achieve more than an order of magnitude speedup in execution time with only negligible error (2.21% on average) in influence spread.