  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 coordinates from different
clusters 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.
