A Differential Evolutionary Influence Maximization Algorithm Based on Network Discreteness

Abstract

The influence maximization problem is designed to seek a set of nodes in a social network so that the set has the maximum information propagation capacity on the network. In response to the inefficiency of existing greedy algorithms and the low accuracy of centrality-based heuristics, we propose an improved differential evolution algorithm (IDDE) based on the network discretization in this paper. The algorithm improves the variance rule of the differential evolution algorithm, takes the discrete number and discrete granularity of the remaining network after the removal of the target node as the index to evaluate the importance of the node, and proposes a fitness function based on the robustness of the network. The method embodies symmetry in two aspects. Firstly, the global connectivity among nodes in the network decreases as the number of target nodes removed in the social network increases. Secondly, the gain of global influence range gradually becomes smaller as the number of target nodes screened by the proposed method increases. We conducted comparison experiments on four real datasets of different sizes, and the results show that the IDDE algorithm outperforms the comparison algorithm.

Keywords

• influence maximization
• differential evolution algorithm
• network discretization