Probing for high influential nodes in social networks via a co-evolutionary memetic algorithm

The identification of a subset of k high influential nodes in a given network as seed nodes is a fundamental operation to address the influence maximization (IM) problem, which can be formulated as a combinatorial optimization problem and was demonstrated to be NP-hard. Solutions based on evolutionary optimization have been demonstrated to be a promising way to solve the IM problem. However, the utilization of a unified paradigm based on stochastic evolutionary searching mechanisms in the resolution process usually results in premature convergence and susceptibility to local optima. To address the issue, this paper presents a novel bi-directional co-evolutionary memetic algorithm (COMA). By adopting the co-evolution strategy and the memetic concept for reference, the proposed algorithm introduces two distinct evolution directions for the same population as its core. The algorithm employs specific evolutionary strategies for the elite individuals and the common ones to manage a trade-off between the global exploration and local exploitation operations on the partitioned populations, while preserving population diversity. Furthermore, these two evolution directions refine and select individuals based on different evaluation functions, with resulting individuals forming the population of the next generation. Extensive experiments conducted on both synthetic and real-world networks demonstrate the feasibility and effectiveness of the proposed algorithm. The experimental findings indicate that, in comparison to alternative algorithms, COMA enhances the influence spread by an average of 10% in small propagation probabilities and 5.9% in high propagation probabilities.