A global optimization algorithm for target set selection problems

Our study concerns the target set selection problem, which involves discovering a subset of influential players in a given social network performing a task of information diffusion to maximize the number of nodes influenced in the network. We are motivated by the facts that the well-known algorithms for target set selection problems are heuristic, and the best heuristic algorithm only ensures that the spread is within 63% of the optimal influence spread based on the submodular assumption. We propose a set-based coding genetic algorithm (SGA), which converges in probability to the optimal solution of target set selection problems. Computational experiments on four synthetically generated graphs and five real-world data sets are carried out to compare the performance of the proposed SGA with those well-known algorithms in the literature. Statistical significance tests indicate that the proposed SGA outperforms the state-of-the-art algorithms for target set selection problems significantly.