Research On Overlapping Community Detection Algorithm Based On Seed Expansion

Community structure is an important characteristic of complex networks,a community is a group of nodes with tight internal connections and relatively sparse external connections.The community detection algorithm is of great value to the study of the internal laws of the complex network.Several classical community detection algorithms in the field of community detection algorithm are analyzed and studied in this thesis.Aiming at the problem of low accuracy of overlapped community detection results due to poor seed selection in the algorithm based on seed extension,a new overlapped community detection algorithm is proposed in this thesis.First,the new seed selection strategy is used to generate a seed set,and then the initial community detection is completed by continuously expanding the seed according to the community measure function,that is,the principle of optimal conductance,finally,a swarm intelligence algorithm-Cockroach Swarm Optimization algorithm is introduced to optimize the community detection results to achieve a better detection effect.Through to the overlapping community detection algorithm thorough research,The main contribution of this thesis is in the following three aspects:(1)The radius parameter Eps and the density threshold value Min Pts in DBSCAN algorithm need to be input manually,if the parameters are not chosen properly,the clustering accuracy will be reduced and noise will appear.In order to solve the problem that the clustering algorithm DBSCAN is sensitive to the parameters which will lead to poor clustering effect,this thesis proposes a clustering algorithm IDBSCAN,which realizes the clustering of all nodes by merging the noisy nodes and clusters with the number of nodes less than 3 into the nearest cluster,therefore,the accuracy of selecting the most influential seed node from the cluster is improved.(2)A new method to calculate the influence of nodes,TON,is proposed,which calculates the topological position of nodes in the network according to the K-shell decomposition algorithm,the influence of nodes in the network is recalculated by using the method of topological position,the influence of nodes themselves and the contribution of neighboring nodes to the influence of nodes.This method provides a basis for selecting high quality seeds.(3)Using swarm intelligence algorithm-Cockroach Swarm Optimization algorithm CSO to optimize the results of community detection,and merge unreasonable communities to achieve better results of community detection.Experimental results show that the proposed algorithm improves the accuracy of detection results and is superior to other overlapping community detection algorithms.