Research On Community Detection Algorithm Based On Dense Subgraphs

The analysis of complex network is widely used in biological networks,social organization,search engines and recommendation systems.Community structure is an important feature of complex networks.A complex network usually contains several communities.The links between the objects in the same community are relatively dense,and the links between the objects in different community are relatively loose.Community detection in large-scale complex networks has become one of the hotspots of current research in many fields.The research on community structures in complex networks contributes to analyzing and understanding the topology of complex networks,so that researchers can study the complex systems more effectively.Density-based graph clustering algorithm detects communities by searching local dense subgraphs in the network and has been widely used in community detection.However,the result of the algorithm has lots of vertices which can't constitute dense subgraphs.Above all,this paper studies the overlapping clustering algorithm based on dense subgraph,which mainly includes the following two aspects:(1)A clustering algorithm based on dense subgraphs(BDSG)is proposed for undirected networks.Firstly,the algorithm searches the central communities in the network based on the dense subgraph,whose density is greater than the threshold.For the vertices that are not belonging to the central community,the belonging degree of node is defined,and the central community extended strategy is proposed based on the belonging degree.Then the algorithm adds the vertices to some central communities.Finally,the clustering results of a network are obtained.The central community extended strategy ensures that the algorithm can detect overlapping community structures in the network.Compared with the classical density-based graph clustering method CPM and k-dense algorithm on five real network datasets,BDSG algorithm shows a considerable or better performance on modularity and time efficiency,and the central community extended strategy can improve the effectiveness of the clustering methods based density,such as CPM,k-dense and so on.(2)An overlapping community detection algorithm on weighted networks(OCDW)based on weighted dense subgraphs is proposed.In this paper,we combine the topology of the network with the weight information of the edge,and give a method of weight definition of the edge in the network.Next,we give the vertices weight definition based on the edge weights,select the node with the largest weight as the seed node.The seed nodes are gradually expanded into a dense subgraph as the central community.Finally,the vertices are assigned to the central community according to the belonging degree,and the final community is found by merging and optimizing process.Compared with k-dense,CPM,MCODE,HC-PIN,MDOS and BGLL algorithm in six unweighted networks and three weighted networks,the comparison result shows that the algorithm OCDW has a better performance in terms of F-measure,accuracy,resolution,standard mutual information,adjusted rand index,modularity and running time.