Detection Of Overlapping Community In Social Networks

Community structure is a common property of various kinds of networks(such as online social networks,biological interaction networks and the Internet).By studying the network and detecting the community structure in the network,we can better understand the topology of the network,the attributes and characteristics of the entities in the network,and the information transmission channels in network,etc.In addition,research on community discovery has many practical significance,such as personalized service,information push and so on.In a real network,a node often belongs to multiple communities.In this paper,we focus on the discovery of overlapping nodes in overlapping communities.Unlike most current community discovery algorithms,we separate community discovery process from overlapping detection process.In this paper,we focus on overlapping nodes detection,and propose two algorithms.The first algorithm is named Link Partition of Overlapping Communities(LPOC),which is based on link clustering.The algorithm is divided into community discovery and filtering process in two parts.LPOC algorithm can detect the overlapping nodes accurately and overcome the defects of link clustering which produces too many overlapping nodes.In large networks,LPOC algorithm based on link graph clustering is not suitable for such networks because of the large number of edges.To overcome this,we propose another algorithm named candidate overlapping nodes screening(CONS)algorithm,which find community structure at first,then we design a screening method and the corresponding objective function to identify nodes that really connect multiple communities.We evaluated these two algorithms on both LFR benchmarks and real-world networks,and compare with several other approaches.Results show that our algorithms have better accuracy than the contrast algorithms in LFR networks,and perform much better than many other algorithms in terms of partition density,modularity and WAC function in real networks.