Research On Parallel Multi-objective Evolutionary Algorithm For Community Detection In Large-scale Complex Networks

In real life,there are many kinds of complex systems,some of which can be described as complex networks abstractly.Using community detection algorithms to detect community in complex networks,it can better understand the system structure,mine the potential information of the system,and predict some unknown functions and attributes.Multi-objective Evolutionary Algorithms(MOEAs)have become one of the most important methods for community detection in complex networks because of their good parallelism,global search ability and availability to any functional class.However,most of the evolutionary algorithms for community detection are constrained by network scale.In order to further improve the quality and efficiency of community detection in large-scale complex networks,this thesis proposes a parallel multi-objective evolutionary algorithm for community detection.They are parallel multi-objective evolutionary algorithm for non-overlapping community detection in large-scale complex networks and parallel multi-objective evolutionary algorithm for overlapping community detection in large-scale complex networks.The main research works of this thesis are as follows:(1)A parallel multi-objective evolutionary algorithm for non-overlapping community detection in large-scale complex networks(PMOEA)is proposed.In PMOEA,a MOEA is designed to focus on detecting a set of communities associated with key nodes in the network,instead of directly detecting all communities in the network,and multiple multi-objective evolutionary algorithms are detected in parallel.Finally,using the single-objective evolution algorithm EA,the community partition of the whole network is obtained from the community set associated with all key nodes.In this thesis,the parallel mechanism adopts different optimization objectives from the traditional multi-objective algorithm for community detection,and at the same time,a special cross-mutation strategy is designed to greatly shorten the individual coding length.Each multi-objective evolutionary algorithm outputs a set of high-quality communities associated with key nodes.Combined with multi-threaded and distributed computing resources,multiple multi-objective evolutionary algorithms are used to detect large-scale complex networks communities in parallel,which reduces the search space of the population in the evolutionary process,improves the quality of the excavated communities,and greatly reduces the time-consuming of multi-objective evolutionary algorithms to detect large-scale complex networks communities.This thesis verifies the effectiveness of the proposed PMOEA algorithm on real networks and LFR benchmark networks.The experimental results show that the proposed algorithm outperforms six representative community detection algorithms and has great advantages in large-scale complex networks community detection.(2)A parallel multi-objective evolutionary algorithm for overlapping community detection in large-scale complex networks(PMOEAO)is proposed.On the basis of the work(1)further improvements are made.In the evolution process of MOEA,candidate overlapping nodes are used to adjust the community boundaries,so that the community boundaries associated with key nodes can be more reasonable.The overlapping nodes are the boundary nodes between communities.The candidate overlapping nodes are obtained by investigating the edges of the network with less similarity.Then,the extended modularity of evaluating overlapping communities is selected as the objective function,and the whole overlapping communities are determined by single-objective evolutionary algorithm EA.Compared with several other competitive overlapping community detection algorithms,the experimental results show that the PMOEAO algorithm also performs well in overlapping community detection,and is suitable for solving overlapping community detection problems in large-scale complex networks.