Discovering Overlapping Communities by Clustering Local Link Structures

Recent advances point out that the existing community detection methods commonly face two challenges:incorrect base-structures and incorrect membership of weak-ties. To overcome both problems, a Local link structure (LLS) clustering based method for overlapping community detection is proposed. We extend the similarity of a pair of links to a group of links named LLS, and thus transform mining LLSs as a pattern mining problem. We prove that LLS with an appropriate threshold can filter weak-ties in the form of bridge and local bridge with its span being larger than 3. A compositive framework is presented for overlapping community detection based on LLS mining and clustering. Comparative experiments on both synthetical and real-world networks demonstrate that our method has advantage over six existing methods on discovering higher quality communities.