Title: Unified scheme for finding disjoint and overlapping communities in social networks using strength of ties

Authors: Partha Basuchowdhuri; V.K. Lakshan Prabhu; Mithun Roy; Subhashis Majumder; Sanjoy Kumar Saha

Addresses: Department of Computer Science and Engineering, Heritage Institute of Technology, Kolkata 700107, WB, India ' Department of Computer Science and Engineering, Thiagarajar College of Engineering, Madurai 625015, TN, India ' Department of Computer Science and Engineering, Siliguri Institute of Technology, Siliguri 734009, WB, India ' Department of Computer Science and Engineering, Heritage Institute of Technology, Kolkata 700107, WB, India ' Department of Computer Science and Engineering, Jadavpur University, Kolkata 700032, WB, India

Abstract: In this paper, we have defined a metric that measures the strength of a link (SOL) in the network to calculate the degree to which it is considered to be part of a community. Higher the strength value of a link, more likely it is to be an integral part of a community whereas links with lesser strength value, such as bridges, are considered to be on the border of the communities. Based on the strength of the links, first we have devised a disjoint community detection technique and then we have extended it to form a unified scheme capable of detecting both disjoint and overlapping communities. This method does not need any predefined number of communities as input and shows the best set of clusters as output. Proposed methods produce results closer to ground truth compared to some popular community detection methods and has a high clique retention index.

Keywords: social networks; community detection; overlapping communities; clustering coefficient; disjoint communities; strength of ties.

DOI: 10.1504/IJSNM.2015.072304

International Journal of Social Network Mining, 2015 Vol.2 No.2, pp.173 - 202

Accepted: 30 Jul 2015
Published online: 08 Oct 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article