An upper approximation based community detection algorithm for complex networks

摘要

The emergence of multifarious complex networks has attracted researchers and practitioners from various disciplines. Discovering cohesive subgroups or communities in complex networks is essential to understand the dynamics of real-world systems. Researchers have made persistent efforts to investigate and infer community patterns in complex networks. However, real-world networks exhibit various characteristics wherein existing communities are not only disjoint but are also overlapping and nested. The existing literature on community detection consists of limited methods to discover co-occurring disjoint, overlapping and nested communities. In this work, we propose a novel rough set based algorithm capable of uncovering true community structure in networks, be it disjoint overlapping or nested. Initial sets of granules are constructed using neighborhood connectivity around the nodes and represented as rough sets. Subsequently, we iteratively obtain the constrained connectedness upper approximation of these sets. To constrain the sets and merge them during each iteration, we utilize the concept of relative connectedness among the nodes. We illustrate the proposed algorithm on a toy network and evaluate it on fourteen real-world benchmark networks. Experimental results show that the proposed algorithm reveals more accurate communities and significantly outperforms state-of-the-art techniques. (C) 2017 Elsevier B.V. All rights reserved.