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

There are a large number of complex systems in the real world,which can be abstractly described as complex networks--biological networks,neural networks,the Internet,the worldwide web and social networks etc.These complex networks usually have the characteristics of community structure.Detecting community structure can help analyze the structure of complex network and find potential functions of complex network.Thus,community detection in complex network is an important research topic,which has important theoretical meanings and realistic values.In recent years,researchers have proposed a large number of algorithms for community detection in complex network,Evolutionary algorithms exhibit good performance due to their good parallelism,global search,and the availability of any function classes.Therefore the community detection methods based evolutionary algorithms are becoming one of kinds of important methods to solve the problem of community detection in complex network.However,these evolutionary algorithms are worthy of further study in non-overlapping community detection and overlapping community detection.Thus this paper proposes a network reduction based multi-objective evolutionary algorithm(named RMOEA)for non-overlapping community detection and proposes a mixed representation based multi-objective evolutionary algorithm(named MRMOEA)for overlapping community detection.The main research work and innovations of this thesis are shown as follows:(1)This thesis proposed a network reduction based multi-objective evolutionary algorithm for non-overlapping community detection(termed as RMOEA).At present,community detection based multi-objective optimization algorithms have great detection ability on small networks.However,these algorithms can not perform well on large networks.The main reason is that these algorithms do not take into account that the larger the network size is,the larger the search space of the multi-objective evolutionary algorithm is.Thus this thesis proposes a network reduction based multi-objective evolutionary algorithm for non-overlapping community detection.The main idea of the algorithm is to gradually reducing the search space of the evolutionary algorithm by gradually reducing the complexity of the network.The network reduction strategy runs through the entire algorithm of RMOEA:firstly using the characteristic thatsaclosely connected nodes are easy to be divided into a community to reduce the complexity of network in pre-evolutionary stage,which can be described as pre-reduction;Then using the second characteristic which individuals always have the same local community structure to reduce complex network scale in evolutionary stage,which can be described as evo-reduction;Finally a fault tolerant strategy is proposed to correct the error nodes in the process of reducing the complexity of the network.The experimental results show that RMOEA is an effective and efficient community detection algorithm,compared to other community detection algorithm based optimization on real data sets and LFR synthetic data sets.(2)This thesis proposed a mixed representation based multi-objective evolutionary algorithm(named MRMOEA)for overlapping community detection.At present,there are a lot of research results based multi-objective evolutionary algorithm in the non-overlapping community,but the research results in overlapping societies are very few.The main reason for this is that there are few codes that can be decoded into overlapping community structures.Thus this thesis proposes a mixed representation based multi-objective evolutionary algorithm.The main idea of the algorithm is mixed representation.The gene of mixed representation is composed of candidate overlapping nodes and non-overlapping nodes.The candidate overlapping nodes use discrete coding(0 or-1),and the non-overlapping nodes use vector coding.Based on the mixed representation,a method of mining candidate overlapping nodes is proposed and a particle swarm learning method is proposed to produce offspring.The experimental results show that MRMOEA is an effective and efficient community detection algorithm,compared to other community detection algorithm based optimization on real data sets.