Density-Based Link Clustering Algorithm for Overlapping Community Detection

For detecting overlapping communities efficiently and effectively in various real-world social networks, we propose a novel density-based link clustering algorithm called DBLINK. The proposed algorithm firstly partitions the edge set of the network into disjoint link communities, which will be then transformed into the final node communities. The overlapping nodes will be linked with the edges that are assigned into different link communities. Furthermore, for obtaining the overlapping community structure with high quality and without excessive overlap, DBLINK utilizes the density-based algorithm as the clustering method for the edge set, which has the ability of identifying the isolated edges that are not satisfied with certain conditions and assigning them into no-link community. An empirical evaluation of the method using both synthetic and real datasets demonstrates that DBLINK not only has satisfying time efficiency, but also plays better performance than the state-of-the-art methods at the community detection quality aspect.