Detect Hierarchical And Overlapping Community Structure In Complex Networks

Community structure is an important property in the field of complex networkswhich is discovered latest. Community is the set of nodes which is partitioned accordingto the relationship between of nodes in the networks. The property of communitystructure，in which network nodes are joined together in tightly knit groups， betweenwhich there are only looser connections. Networks will be organized visually bycommunity; it is more practical significance to research some real complex networks.The process of detecting community structure provides effective theoretical basis forgroup characteristics in research of networks.For many real world networks, their community structure often appears to behierarchical and overlapped i.e. one large community can be further divided into severalsmaller ones and one node may belong to several different communities due to theeffect of multiple inter connection. Communities and overlapping structures in socialnetworks are more obvious and as a result，easier to identify. But traditional algorithmsfor the identification of communities in complex networks are targeting at node sets，they use hierarchical clustering approach to better identify the hierarchical structure ofcommunities. In this paper，we view this problem from another perspective under whichcommunities were identified not by the sets of nodes but sets of links. The originalgraph should be converted to line graph，in which nodes are links. Thus the nodecommunity will be converted to edge community. Then networks can be representedby line graph，using hierarchical clustering algorithm to construct the dendrogram ofline graph. Each level of dendrogram is the community partitions of networks. In theoriginal graph every link belongs to an independent community in the clusteringprocess，but a node maybe connected to multiple links，so it can make some nodes mayalso belong to multiple communities， thus it is further to detect the overlappingstructure.The purpose of this paper is to detect both hierarchical structure and overlappingstructure in the network community. An algorithm which is based on the similarity ofnode in line graph to detect the hierarchical and overlapping community is proposed inthis paper. There are three parts in this algorithm. Firstly，line graph of network could beconstructed. Secondly， according to the definition of node similarity， the concept ofextensive node neighbor is proposed，the formula of similarity of node in line graph is proposed based on this concept. And then it is extended to weighted network. The nodesin the network are clustered by hierarchical agglomerative method according to thesimilarity between them. Thirdly， the classic measure of node set communitymodularity standard for link as a collection of community is no longer applicable. Anew measure is proposed which called partition density to evaluate the communitypartitions according to the density of internal edges of the node community.Finally，applying the proposed algorithm to several real world datasets to evaluateits performance. And then，analyzing the experimental results compared with Newman’sfast algorithm and CPM algorithm. The experimental result indicates that the proposeddiscovery algorithm can be effectively detected the hierarchical and overlappingstructure. At the same time，the complexity of the algorithm is improved obviously，andthe problem of low efficiency of the traditional algorithm is avoided.