A novel two-step approach for overlapping community detection in social networks

Abstract

With the rapid increase in popularity of online social networks, community detection in these networks has become a key aspect of research field. Overlapping community detection is an important NP-hard problem of social network analysis. Modularity-based community detection is one of the most widely used approaches for social network analysis. However, modularity-based community detection technique may fail to resolve small-size communities. Hence, we propose a novel two-step approach for overlapping community detection in social networks. In the first step, modularity density-based hybrid meta-heuristics approach is used to find the disjoint communities and the quality of these disjoint communities can be verified using Silhouette coefficient. In the second step, the quality disjoint communities with low computation cost are used to detect overlapping nodes based on Min-Max Ratio of minimum(indegree, outdegree) to the maximum(indegree, outdegree) values of nodes. We tested the proposed algorithm based on 10 standard community quality metrics along with Silhouette score using seven standard datasets. Experimental results demonstrate that the proposed approach outperforms the current state-of-the-art works in terms of quality and scalability. 2017, Springer-Verlag GmbH Austria.