Study On Hierarchical Community Detection Algorithm In Social Network

Community structure is one of the most important features in social networks.It means that internal connections between vertices in the same community are tight while external connections between vertices in different communities are loose.The community structure in social network often demonstrates a hierarchy with small communities embedded in big ones.Mining the community structure in social networks is of great significance to understand the structure and function of social networks.Existing hierarchical community detection methods can be classified into divisive and agglomerative methods,in which the agglomerative type has been widely used because of its excellent characteristics.However,the typical agglomerative methods often have the following problems: 1.most methods treat each vertex in the network as an initial community and the corresponding dendrogram is complex,which is not conductive to understanding and analysis.2.most methods are difficult to ensure the efficiency and accuracy at the same time.To overcome the above problems,the paper studies the hierarchical structure of the social networks from the topological potential and minimum spanning tree,the main contents include:(1)A hierarchical community detection method based on topological potential.The method first searches for the local maximal potential vertices in the network and divides the network into initial communities based on these vertices,then iteratively merges these communities according to the distance between the maximal potential vertices,which significantly reduces the merging times and makes the generated dendrogram simple and meaningful.Experimental results on real and artificial networks show that this method can both guarantee the efficiency and accuracy.(2)A hierarchical community detection method based on minimum spanning tree.The method first constructs micro-community according to the link strength of the adjacent vertices,and then iteratively merges these micro-communities to generate the minimum spanning tree.The hierarchical structure is revealed during the tree generating process.Experimental results in real and artificial networks show that the generated dendrogram is simple and the method can completely discover the community structure in a linear time accurately.