A density-based noisy graph partitioning algorithm

• We propose a graph-based clustering algorithm based on a density-of-graph structure.
• The proposed algorithm is useful for data exhibiting noisy and nonlinear patterns.
• The proposed algorithm does not require to specify the number of clusters in advance.
• The proposed algorithm outperformed other graph-based clustering algorithms.

Clustering analysis can facilitate the extraction of implicit patterns in a dataset and elicit its natural groupings without requiring prior classification information. Numerous researchers have focused recently on graph-based clustering algorithms because their graph structure is useful in modeling the local relationships among observations. These algorithms perform reasonably well in their intended applications. However, no consensus exists about which of them best satisfies all the conditions encountered in a variety of real situations. In this study, we propose a graph-based clustering algorithm based on a novel density-of-graph structure. In the proposed algorithm, a density coefficient defined for each node is used to classify dense and sparse nodes. The main structures of clusters are identified through dense nodes and sparse nodes that are assigned to specific clusters. Experiments on various simulation datasets and benchmark datasets were conducted to examine the properties of the proposed algorithm and to compare its performance with that of existing spectral clustering and modularity-based algorithms. The experimental results demonstrated that the proposed clustering algorithm performed better than its competitors; this was especially true when the cluster structures in the data were inherently noisy and nonlinearly distributed.