K-Means Community Detection Algorithm Based on Density Peaks
Open Access
Abstract
The identification of community structure is pivotal for understanding the functional characteristics of complex networks. To address the limitations of most existing community detection algorithms, which often require predefining the number of communities and lack robustness, this paper proposes a novel community detection algorithm named D-means (K-means community detection algorithm based on density peaks). This algorithm integrates the concept of density peak clustering with K-means spectral clustering, employing Chebyshev’s inequality to automatically determine the number of community centers, thereby enabling unsupervised identification of community quantities. By designing a multi-dimensional evaluation framework, the comparative experiments were conducted on LFR benchmark networks (Lancichinetti-Fortunato-Radicchi benchmark networks) and real-world social network datasets. The results demonstrate that the D-means algorithm outperforms traditional algorithms in terms of ACC (accuracy), ARI (adjusted rand index), and NMI (normalized mutual information) metrics, while also achieving improvements in runtime efficiency, showcasing strong robustness. Finally, the D-means algorithm was applied to the public transportation network of Urumqi. Empirical analysis identified 12 functionally significant transportation communities, providing theoretical support for urban rail transit optimization and commercial facility layout planning.Keywords
This publication has 18 references indexed in Scilit:
- WANN-DPC: Density peaks finding clustering based on Weighted Adaptive Nearest NeighborsPattern Recognition, 2025
- A review of synchronization of extreme precipitation events in monsoons from complex network perspectiveJournal of Hydrology, 2024
- DPC-MFP: An adaptive density peaks clustering algorithm with multiple feature pointsNeurocomputing, 2024
- Network community detection via neural embeddingsNature Communications, 2024
- An overview on density peaks clusteringNeurocomputing, 2023
- Community structure detection in networks based on Tabu searchJournal of Control and Decision, 2022
- Semi-supervised overlapping community detection in attributed graph with graph convolutional autoencoderInformation Sciences, 2022
- Local community detection with hintsApplied Intelligence, 2022
- Dynamic graph-based label propagation for density peaks clusteringExpert Systems with Applications, 2019
- An Improved Complex Network Community Detection Algorithm Based on K-Means2012