Journal
SIGNAL PROCESSING
Volume 187, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.sigpro.2021.108147
Keywords
Sparse graphs; Community detection; Network analysis; Graph-based clustering; Cluster enumeration
Categories
Funding
- Republic of Turkey Ministry of National Education
- LOEWE initiative (Hesse, Germany) within the emergenCITY centre
- 'Athene Young Investigator Programme' of Technische Universitat Darmstadt, Hesse, Germany
Ask authors/readers for more resources
SPARCODE is a new method for sparsity-aware robust community detection that finds the correct number of communities by optimizing sparsity level and outperforms existing methods in terms of performance, robustness, and modularity score.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available