Research On Multi-objective Evolutionary Algorithm For Community Detection Based On The Guidance Of Incomplete Subgraph

In real life,multi-objective optimization problem exist generally and attracting the attention of scholars in all various of fields and becoming one of the important research fields.At present,a lot of solutions are proposed for multi-objective optimization problems.Among them,multi-objective optimization problems based on genetic algorithm can effectively solve muti-objective optimization problems and have been approved by experts and scholars.The problem of community detection in complex network is also a multi-objevtive optimization problem.Complex networks are widely used in real world,and they can represent many existing systems.Community detection in complex network is helpful to understand the structure of network and explore the potential information and features in the complex network.Therefore,this paper proposed a multi-objective evolutionary algorithm for community detection of complex network,including the research on multi-objective evolutionary for community detection algorithm based on incomplete subgraph guidance of node coding and the research on multi-objective evolutionary for community detection algorithm based on edge coding.The main research works of this paper are as follows:(1)the research on multi-objective evolutionary.for community detection algorithm based on incomplete subgraph guidance of node coding(LMOEA).In evolutionary algorithms,some easily detected communities in complex networks can be detected after a few iterations and the community like that is called incomplete subgraph.The rational use of incomplete subgraph to detect during evolution can improve the performance of multi-objective evolutionary algorithm.In the algorithm LMOEA,an individual updating strategy based on incomplete subgraph is proposed.The algorithm uses the population of evolution to obtain the incomplete subgraph and uses these incomplete subgraph to update some individuals in the population to guide the population to evolve in a better direction.It can accelerate the convergence of population,and ultimately achieve better community detection.LMOEA algorithm compared with four algorithms on LFR benchmark networks and real-world networks and confirmed the performance of the algorithm,shows the effectiveness of the algorithm.(2)This thesis proposed the research on multi-objective evolutionary for community detection algorithm based on edge coding(EMOEA).A complex network can be understand as a graph that consist of nodes and edges.At present,many community detection in complex networks based multi-objective evolutionary algorithm carry out community detection from the perspective of node.However,this paper research on how to use edge information to detect communities on complex networks and proposed the algorithm of EMOEA.EMOEA proposed 0-1 coding which encodes the edges in the network and refers to the idea of cutting.If the encoding of the edge is 0 represent nodes on this edge is disconnect,otherwise,keeping the edge between these two nodes.It is generally believed that the local similarity between the edges within the community is high and the local similarity between the edges is low.Based on this,the algorithm is proposed to use the concept of local similarity to determine the mutation rate of each gene of individual.And finally to identify the edges that need to be cut through the mutation rate.At the same time,the algorithm makes use of incomplete subgraph that is easily available in the process of population evolution to update individual individuals,adjust the direction of evolution,and guide the evolution of population.Compared with other algorithms,the experimental results show that EMOEA shows better performance in community detection.