An efficient discrete differential evolution algorithm based on community structure for influence maximization

摘要

As one of the main contents of influence analysis, influence maximization is selecting a group of influential nodes with specified size in a given network to form a seed node set, and the influence spread cascaded by the selected seed node set can be maximized under a given propagation model. The research of influence maximization is helpful to understand social network and viral marketing. How to develop an effective algorithm to solve this problem in large-scale networks is still a challenge. In this paper, a discrete differential evolution algorithm based on community structure (CDDE) is proposed. At first, the fast Louvain algorithm is used to detect the community structure. On this basis, significant communities are defined and candidate nodes are extracted from each significant community. And then, an improved discrete differential evolution algorithm is proposed to obtain influential nodes. Furthermore, a population initialization strategy based on candidate nodes is designed, and the candidate nodes are also used to accelerate the discrete evolution process of the population. Experimental results on six real-world social networks show that the proposed CDDE is competitive with the comparison algorithms in terms of effectiveness and efficiency, and achieves comparable influence spread to CELF.