Research On Link Clustering Algorithms In Overlapping Community Detection

Overlapping community detection has been a hot topic in complex networks. It aims to uncover the overlapping community structure. Overlapping community structure is close to the real situations. It is a practical significance to overlapping community detection. Traditional overlapping community detection algorithms mostly concentrate on nodes. In recent years, several works are based on links and identify link communities in complex networks. Those algorithms are named as link community detection algorithms, in general.Different from traditional algorithms, link community detection algorithms are based on the idea that a community is composed of links. Based on links, they have their own advantages. For example, in real networks, a link usually belongs to only one community. Link community detection algorithms form natural overlapping community structure after the link communities identified. Some works use the hierarchical clustering algorithm to cluster links for the advantage of considering hierarchical and overlapping relationships of related nodes simultaneously.Although the advantages mentioned above, they still have the problems of link communities identified with low quality, incomplete link similarity relations and node communities with excessive overlap. To extend strategies of traditional overlapping community detection, in this paper, we begin our work to improve link similarity relation model, from the view of link. Considered link similarity based on line graph, extended cosine link distance, and maxima and minima link similarity, we improve the link similarity model step by step.1. We use line graph to model the problem of link clustering. Considered the link similarity relationship between links with common neighbors and non-neighbors, link similarity method based on line graph is proposed. Combined with markov clustering algorithm and the method, link clustering algorithm based on line graph(LCLG) is proposed. The experiments on three real networks and a biological network show LCLG algorithm is effective to detect link community structure.2. Considered link similarity relations between the links with common neighbors, combined with cosine similarity, an extended cosine link distance method is proposed. The clustering algorithm by fast search and find of density Peaks(FSDP) is introduced for link community detection. A strategy for automatically choosing the center links based on the box model is proposed. Combined with the extended cosine link distance method, FSDP algorithm and the strategy, a link density clustering algorithm(LDC) is proposed. Tests on the empirical and unempirical networks show that LDC algorithm is able to identify overlapping communities with good modularity and high coverage.3. Considered extreme situation between links with common neighbors, maxima and minima non-neighbor link similarity is proposed. Combined with extended modularity to improve the results of hierarchical clustering algorithm, link clustering algorithm based on maxima and minima non-neighbor link similarity(MLC) is proposed. Extensive tests on three real networks show that MLC algorithm is able to find overlapping community detection in terms of good modularity.Proposed in this paper, LCLG, LDC and MLC algorithms are able to find link community structure in complex networks for overlapping community detection. They are of benefit both in theory and practice.