Topology-Guided Density Peak Clustering

Abstract

Density Peak Clustering (DPC) has emerged as a powerful clustering algorithm capable of identifying clusters of arbitrary shapes by detecting density peaks in data. However, DPC suffers from several limitations: manual selection of cluster centers from the decision graph, sensitivity to the cutoff distance parameter, and suboptimal assignment of border points. We propose TGDPC (Topology-Guided Density Peak Clustering, Figure 1), a novel algorithm that address these limitations through an adaptive strategy combining graph connectivity analysis with density peak detection. TGDPC constructs a degree-constrained k-nearest neighbor graph to identify natural data partitions, employs delta-based center selection for more robust center identification, and implements an intelligent multi-stage merging strategy to guarantee exactly K clusters. Graph preprocessing is a natural approach to data preprocessing. Extensive experiments on synthetic and real-world datasets demonstrate that TGDPC achieves significantly superior clustering performance over classic algorithms (e.g., K-means, DBSCAN, and Spectral Clustering) as well as state-of-the-art DPC variants such as DPC-DBFN, DGDPC, WANN-DPC, and VDPC. The algorithm maintains O(n2) time complexity while providing deterministic, parameter-robust results without requiring manual intervention.