An upper approximation based community detection algorithm for complex networks

Pradeep Kumar

doi:10.1016/j.dss.2017.02.010

Return

An upper approximation based community detection algorithm for complex networks

2017-04-01

PRE

Pradeep Kumar

Gupta, Samtat *

Bharat Bhasker

DOI：10.1016/j.dss.2017.02.010

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Community structure

Complex networks

Community detection algorithms

Overlapping communities

Neighborhood model

Rough sets

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.