Research On Multi-objective Evolutionary Algorithm For Overlapping Community Detection In Complex Networks

Complex systems in the real world are inseparable from people's lives,these complex systems can be represented as complex networks.As an important characteristic of complex networks,community structure plays an irreplaceable role in analyzing the structural attributes and potential functions of complex networks.There are two main types of communities in complex network: one is non-overlapping community,which means that nodes in the network can only belong to one community;the other is overlapping community,which means that nodes in the network can belong to multiple communities.Most complex networks in the real world have overlapping communities,so this paper focuses on overlapping community detection problem.To solve this problem,researchers are paying more and more attention to overlapping community detection algorithms based on multi-objective optimization,which can simultaneously optimize multiple objective functions that are contradictory and make full use of network structure information,finally get a set of network divisions at different levels,where decision makers can choose a community structure that meets the conditions.One of the main challenges of applying multi-objective evolutionary optimization methods to overlapping community detection is to design appropriate individual representation and corresponding evolutionary strategies,so this paper designs a dual representation strategy from the perspective of encoding,which can effectively encode individuals in the population and decode to get the overlapping community structures.On the basis of the dual representation,this paper proposes a dual representation-based multi-objective evolutionary algorithm for overlapping community detection.This paper explores the problem of detecting overlapping communities in large-scale complex networks,and use the reduction strategy to reduce the network dimension.Based on the dual representation,this paper proposes a network reduction and dual representation based multi-objective evolutionary algorithm for large-scale overlapping community detection.The research content of this paper is as follows:(1)This paper designs a dual representation method,which can encode the community structure and overlapping nodes separately.According to the dual representation,a dual representation-based multi-objective evolutionary algorithm for overlapping community detection(DRMOEA)is proposed.In the overlapping community detection algorithm based on multi-objective evolution,the main challenge is design of individual representation so that it can be intuitively decoded into overlapping communities.In this paper,the problem of overlapping community detection in complex networks is transformed into a multi-objective optimization problem,while considering the proportion of internal contacts in the community and the proportion of external contacts in the community,and proposes a dual representation-based multiobjective evolutionary algorithm for overlapping community detection,termed as DRMOEA.In the DRMOEA algorithm,an initialization strategy based on community boundary nodes is proposed to obtain good initial individuals and improve the detection performance of the algorithm.In the evolution process,a crossover strategy based on the boundary nodes of elite individuals is proposed for overlapping node representation.This strategy uses community boundary information to guide the population to evolve in a good direction and effectively improves the performance of the algorithm.Finally,the experiments verify that DRMOEA can effectively deal with overlapping community detection problem.(2)This paper proposes a network reduction and dual representation based multi-objective evolutionary algorithm for large-scale overlapping community detection(RDRMOEA).As the number of nodes in the network increases,the length of individual representation will increase and the population search space will increase.Therefore,this paper proposes a network reduction and dual representation based multi-objective evolutionary algorithm for large-scale overlapping community detection,which is used to solve the problem of overlapping community detection in large-scale complex networks.In the RDRMOEA algorithm,firstly,the closely connected nodes in the network are reduced and the network is reconstructed.In the evolution process,the network is further reduced by using the same local characteristics of individuals in the population,and an individual local repair strategy is proposed to correct the nodes that were erroneously reduced during the network reduction process.Finally,the experimental results on real networks and LFR benchmark networks show that the RDRMOEA algorithm can effectively deal with the problem of overlapping community detection in large-scale complex networks.