Clustering Based on Density Propagation and Subcluster Merging
This is an incremental improvement for clustering tasks, offering a method that works in both data and graph spaces without requiring pairwise distance calculations.
The paper tackles the problem of automatically determining the number of clusters in density-based clustering by proposing the DPSM method, which uses density propagation and subcluster merging, and validates its effectiveness through experiments.
We propose the DPSM method, a density-based node clustering approach that automatically determines the number of clusters and can be applied in both data space and graph space. Unlike traditional density-based clustering methods, which necessitate calculating the distance between any two nodes, our proposed technique determines density through a propagation process, thereby making it suitable for a graph space. In DPSM, nodes are partitioned into small clusters based on propagated density. The partitioning technique has been proved to be sound and complete. We then extend the concept of spectral clustering from individual nodes to these small clusters, while introducing the CluCut measure to guide cluster merging. This measure is modified in various ways to account for cluster properties, thus provides guidance on when to terminate the merging process. Various experiments have validated the effectiveness of DOSM and the accuracy of these conclusions.