A density-based noisy graph partitioning algorithm

Jaehong Yu, Seoung Bum Kim

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Publication statusAccepted/In press - 2015 Mar 8


  • Clustering algorithm
  • Density coefficient
  • Maximizing connectivity
  • Nonlinearity

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications
  • Cognitive Neuroscience


Dive into the research topics of 'A density-based noisy graph partitioning algorithm'. Together they form a unique fingerprint.

Cite this