An overlapping community detection algorithm based on rough clustering of links

Abstract

The growth of networks is prevalent in almost every field due to the digital transformation of consumers, business and society at large. The unfolding of community structure in such real-world complex networks is crucial since it aids in gaining strategic insights leading to informed decisions. Moreover, the co-occurrence of disjoint, overlapping and nested community patterns in such networks demands methodologically rigorous community detection algorithms so as to foster cumulative tradition in data and knowledge engineering. In this paper, we introduce an algorithm for overlapping community detection based on granular information of links and concepts of rough set theory. First, neighborhood links around each pair of nodes are utilized to form initial link subsets. Subsequently, constrained linkage upper approximation of the link subsets is computed iteratively until convergence. The upper approximation subsets obtained during each iteration are constrained and merged using the notion of mutual link reciprocity. The experimental results on ten real-world networks and comparative evaluation with state-of-the-art community detection algorithms demonstrate the effectiveness of the proposed algorithm.