Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations


  • Naoto Ohsaka The University of Tokyo
  • Takuya Akiba The University of Tokyo
  • Yuichi Yoshida National Institute of Informatics
  • Ken-ichi Kawarabayashi National Institute of Informatics



influence maximization, independent cascade model, social networks


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.




How to Cite

Ohsaka, N., Akiba, T., Yoshida, Y., & Kawarabayashi, K.- ichi. (2014). Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).