Research Of Community Detection Algorithm Based On Core Vertex Expansion

Many relationships in the real world that can be regarded as complex networks,such as social communication circles,reference relations of papers,connections between organisms,aviation lines,and so on.Community is the most typical feature structure in complex networks,and the interconnections between communities determine the composition of complex networks.Studying communities in complex networks can explore the potential rules of complex networks,and can also help to further understand the property of a network from the internal structure.Community detection is an important method to mine complex networks,and it can provide solutions for many complex problems in real life.Therefore,it is very important to study community detection algorithm not only in academics,but also in real life.At present,many community detection algorithms can identify community structure in complex networks.In this thesis,the existing community detection algorithms have been deeply studied,and some problems and shortcomings of these algorithms have been found,such as the parameters are difficult to determine,high time complexity and low clustering accuracy.To overcome the disadvantages,this work proposed two no-parameter community detection algorithms.The first is a core vertex expansion community detection algorithm based on PageRank,called CEPR.CEPR focuses on improving the accuracy of community detection algorithms,and detecting the community structure more effectively.It first groups the similar vertices into one community,then uses the PageRank algorithm to find the core vertices in a complex network and further partition the core community.Next,the remaining unlabeled vertices are added to the core community according to their degree values.Finally,a stable community structure is formed through the merger of the community.In the experimental part,CEPR is compared with four state-of-the-art algorithms on nine network datasets of different structures and scales.And to comprehensively demonstrate the effectiveness of CEPR,we used three common indicators to evaluate the performances of all the algorithms.Experimental results indicate that CEPR outperforms the four compared algorithms and can get community structure more accurately in most cases.The second is a core vertex expansion community detection algorithm based on local density,named CELD.It focuses on overcoming the shortcomings of high time complexity in some community detection algorithms,and quickly mining accurate and appropriate community structure from complex networks.CELD defines a local density formula to select core vertices.The local density of the vertex is proportional to the number of the neighbors,and is inversely proportional to the sum of the distance between the neighbors and the vertex.It first puts the similar vertices into a community,then,sorts the vertexes according to the local density to get the core vertex,next,assigns the remaining vertices to the core community,and finally,merges the communities to obtain final result.In experiments,CELD is compared with four state-of-the-art algorithms,on four network datasets with ground-truth and three network datasets without ground-truth,and it is evaluated through three indexes.Experimental results show that CELD has low time complexity,and outperforms the four compared algorithms in most cases.The two algorithm can work effectively without any input parameter.CEPR algorithm can choose the well-founded core vertex,and the CELD algorithm can get the community structure with high quality in a low time complexity.