Simulated Annealing Based Influence Maximization in Social Networks

Authors

  • Qingye Jiang Peking University
  • Guojie Song Peking University
  • Cong Gao Nanyang Technological University
  • Yu Wang Peking University
  • Wenjun Si Peking University
  • Kunqing Xie Peking University

Abstract

The problem of influence maximization, i.e., mining top-k influential nodes from a social network such that the spread of influence in the network is maximized, is NP-hard. Most of the existing algorithms for the prob- lem are based on greedy algorithm. Although greedy algorithm can achieve a good approximation, it is computational expensive. In this paper, we propose a totally different approach based on Simulated Annealing(SA) for the influence maximization problem. This is the first SA based algorithm for the problem. Additionally, we propose two heuristic methods to accelerate the con- vergence process of SA, and a new method of comput- ing influence to speed up the proposed algorithm. Experimental results on four real networks show that the proposed algorithms run faster than the state-of-the-art greedy algorithm by 2-3 orders of magnitude while being able to improve the accuracy of greedy algorithm.

Downloads

Published

2011-08-04

How to Cite

Jiang, Q., Song, G., Gao, C., Wang, Y., Si, W., & Xie, K. (2011). Simulated Annealing Based Influence Maximization in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 127-132. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7838