ACO-IM: maximizing influence in social networks using ant colony optimization

Online social networks play an essential role in propagating information, innovation, and ideas via word-of-mouth spreading. This word-of-mouth phenomenon leads to a fundamental problem, known as influence maximization (IM) or subset selection problem. The IM problem aims to identify a small subset of users, viz. seed nodes such that overall influence spread can be maximized. The seed selection problem is NP-hard, unfortunately. A greedy solution of IM problem is not sufficient due to the use of time-consuming Monte Carlo simulations, which is limited to small-scale networks. However, the greedy solution ensures a good approximation guarantee. In this paper, a local influence evaluation heuristic is adopted to approximate local influence within the two-hope area. With this heuristic, an expected diffusion value under the traditional diffusion models is evaluated. To optimize local influence evaluation heuristic, an influence maximization algorithm based on ant colony optimization (ACO-IM) is presented. ACO-IM redefines the representation and updates the rule of pheromone deposited by ants and heuristic information. The algorithm uses the probabilistic environment to avoid premature convergence. Finally, the experimental results show the superiority of the proposed algorithm. The statistical tests are also performed to distinguish the proposed method from the state-of-the-art methods.