Sparsity-aware robust community detection (SPARCODE)

Aylin Taştan

doi:10.1016/j.sigpro.2021.108147

Return

Sparsity-aware robust community detection (SPARCODE)

2021-10-01

Aylin Taştan *

Michael Muma

Abdelhak M. Zoubir

DOI：10.1016/j.sigpro.2021.108147

Original

Save

View PDF

Abstract

En 中文

Community detection refers to finding densely connected groups of nodes in graphs. In important applications, such as cluster analysis and network modelling, the graph is sparse but outliers and heavy-tailed noise may obscure its structure. We propose a new method for Sparsity-aware Robust Community Detection (SPARCODE). Starting from a densely connected and outlier-corrupted graph, we first extract a preliminary sparsity-improved graph model where we optimize the level of sparsity by mapping the feature vectors from different communities such that the distance of their embedding is maximal. Then, undesired edges are removed and the graph is constructed robustly by detecting the outliers using the connectivity of nodes in the improved graph model. Finally, fast spectral partitioning is performed on the resulting robust sparse graph model. The number of communities is estimated using modularity optimization on the partitioning results. We compare the performance to popular graph and cluster-based community detection approaches on a variety of benchmark network and cluster analysis data sets. Comprehensive experiments demonstrate that our method consistently finds the correct number of communities and outperforms existing methods in terms of detection performance, robustness and modularity score while requiring a reasonable computation time. (c) 2021 Elsevier B.V. All rights reserved.

Keywords:

Sparse graphs

Community detection

Network analysis

Graph-based clustering

Cluster enumeration

AI Summary

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