Research On Overlapping Community Detection Methods Based On Extended Link Clustering

Social Network Analysis started in1930s. Now it has become an important item inSociology and Data Mining. In actual, there are lots of social networks such as scientificresearch and citation network, social relations network, protein-protein interaction networkand so on. And there are always some nodes in groups. The structure of the nodes in groupsoften is called community structure. So it is meaningful for community detection in real socialnetworks.Traditional methods of community detection can only deal with the situation that nodebelongs to one community. But in real social networks, nodes are usually overlapped. So it ismore meaningful for overlapping community detection. In2005, Palla etc. firstly found thephenomenon of overlapping community and put forwards a method called CPM method foroverlapping community detection. After this, a lot of methods for solving this problem areproposed. And overlapping community detection has become a hot issue in communitydetection.Link clustering (LC) is a method proposed by Ahn etc. in2010on Nature for solving theproblem of overlapping community detection. Traditional overlapping community detectionmethods mainly focus on nodes but LC methods focus on links. Firstly, LC method calculatesa similarity matrix whose elements are the link similarity of neighbor links based on theJaccard distance and gets the similarity matrix. Look on the row vectors of the similaritymatrix as the points in Euclidean space, LC method uses hierarchical clustering to the pointsto cluster and get a dendrogram. Finally, it uses a measure of partition density on thedendrogram to make the best level for community detection and then get the communities’division result. The result is for the links of community detection and a link belongs only toone community. But as a node has some links, it may causes nodes belong to differentcommunities. Naturally, the overlapping communities come out, as a result.However, the original link clustering method does not consider the link similarity ofnon-neighbor links. For making up this short, an extended link clustering similarity (ELS) isproposed and an extended link clustering method (ELC) is put forward for overlappingcommunity detection in this paper. Firstly, the extended link clustering method calculates link similarity between links in the network and gets a similarity matrix. Then it employshierarchical clustering similar to link clustering method, and uses the maximum value of EQ(an extended measure of quality of modularity) to cut the dendrogram in order to get betterpartition results in the original network space. Extended link similarity, namely ELS usesmore link information and enhances the similarity matrix’s capability to be a representativebasis for community detection. Meanwhile, using the EQ value to find the best level for thehierarchical clustering dendrogram division, defines communities that are more sensible andreasonable than the ones obtained by the partition density evaluation. Experimentation on fivereal-world networks such as Zachary’s karate club, Dolphin social network, Books about USpolitics, American College football shows that the extended link clustering method getshigher EQ and communities closer to the real situation than the original link clusteringmethod and the classical CPM method. Meanwhile, experimentation on artificial networksshows some features of the networks that three methods are good at, such as nodes averagedegree and the inner links proportion in communities.