Community Detection Based On Multi-objective Particle Swarm Optimization

In recent years,with the development of network science,community networks detection is a hot issue.The task of community detection is describing the local characteristics of an individual in a network and the close relationship between individuals.It plays an important role in studying the structural functions of networks and in analyzing and predicting the direct relationship between individuals.Nowadays,in order to improve the quality of community structure,a set of community detection algorithms based on multiple optimization functions are proposed.These multi-objectives algorithms increase in time and complexity as the number of optimization functions increases.In order to reduce the time complexity of multi-objective community detection algorithm,considering that PSO has high efficiency and accuracy in solving multi-objective optimization problems,this thesis develop an improved non-overlapping community detection algorithm based on multi-objective particle swarm optimization(MOPSO-CD).In order to promote the algorithm to discover overlapping community and find overlapping community accurately,this thesis proposes a new screening strategy to find the overlapping noeds,based on the determined non-overlapping community structure.This algorithm is called MOPSO-OCD.The main work includes the following two aspects:MOPSO-CD.Most of the multi-objective community detection algorithms can find community structures in complex networks well.But their time complexity is high.In oder to take account of the accuracy and efficiency of multi-target community detection algorithm,according to the adjacency list,this thesis proposed a new particle swarm update strategy.The new update strategy allows the particles that need to be updated to adjust its position randomly to a neighbor node from the adjacency list.Then the multi-objective optimization algorithm is used which preserves all th Pareto optimal solutions to adjust the population to correct the missing accuracy cauesd bu the randomness of the update strategy.In addition,in order to improve the efficiency of the algorithm,an efficient method in finding Pareto optimal solutions is introduced in this thesis.Compared with the traditional multi-objective optimization strategy,the time complexity of Pareto optimization reduces from O(n2)to O(nlogn).Through experimental analysis,the MOPSO-CD has high efficiency and greate community structure quality.MOPSO-OCD.Considering the efficiency and accuracy of MOPSO-CD algorithm for the detection of non-overlapping community,this thesis uses the determined non-overlapping community structure to find out the overlapping nodes.In order to improve the efficiency of the algorithm,this thesis designs a two-level filtering strategy.The algorithm adopts a new screening strategy to find the candidates of overlapping nodes.The judgment method of overlapping nodes according to the weight ratio is proposed to judge whether the candidate nodes belong to overlapping nodes.This process effectivly reduces the times of the overlapping nodes detection.Based on experimental analysis,MOPSO-OCD algorithm can well find out the overlapping nodes in complex networks.