ALCMean’s: Unsupervised community detection using local Laplacian, automatic detection of the number of centers

Document Type : Research Paper

Authors

Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

Community detection is a fundamental problem in the analysis of complex networks. It has applications across social, biological, and financial domains. Traditional algorithms, such as Louvain, LPA, and modularity optimization, often require manual parameter tuning. They also suffer from inaccurate cluster center selection. To address these challenges, we propose AlCMean’s, a novel algorithm. AlCMean’s combines Laplacian energy–based automatic center identification with DeepWalk embeddings for robust node representation. Unlike existing Laplacian-based and clustering methods, AlCMean’s eliminates the need to predefine the number of communities, enhances cluster center selection using structural importance, and leverages representation learning for more accurate and stable assignments. Experimental results on benchmark datasets demonstrate 10–20% higher NMI and ARI scores compared to Louvain, Newman–Girvan, LPA, Fast-Greedy, and a recent GNN-based competitor (MAGI, KDD’24). Additional evaluations with modularity and F1-scores confirm the superiority of AlCMean’s. Ablation studies highlight the critical contributions of each component. Despite its reliance on DeepWalk parameters and increased runtime relative to lightweight heuristics, AlCMean’s consistently outperforms state-of-the-art methods. This makes it a promising tool for real-world network analysis. The source code and datasets are publicly available at https://github.com/shahinmomenzadeh/ALCMeans.git

Keywords

Main Subjects

References

[1] Papadopoulos, S., et al. (2012). Community detection in social media: Performance and application considerations. Data Mining and Knowledge Discovery, 24, 515-554. https://doi.org/10.1007/s10618-011-0224-z 
[2] Momenzadeh, S., & Mohammadiani, R. P. (2025). Community Detection by ELP-Means: An Unsupervised Approach That Uses Laplacian Centrality and Clustering. arXiv preprint arXiv:2502.19895. https://doi.org/10.48550/arXiv.2502.19895
[3] Fani, H., & Bagheri, E. (2017). Community detection in social networks. Encyclopedia with Semantic Computing and Robotic Intelligence, 1(01), 1630001. https://doi.org/10.1142/S2425038416300019
[4] Tang, L., & Liu, H. (2022). Community detection and mining in social media. Springer Nature. https://doi.org/10.2200/s00298ed1v01y201009dmk003
[5] Berahmand, K., Nasiri, E., & Li, Y. (2021). Spectral clustering on protein-protein interaction networks via constructing anity matrix using attributed graph embedding. Computers in Biology and Medicine, 138, 104933. https://doi.org/10.1016/j.compbiomed.2021.104933
[6] Li, J., et al. (2024). A comprehensive review of community detection in graphs. Neuro-computing, 128169. https://doi.org/10.1016/j.neucom.2024.128169
[7] Shen, H.-W. (2013). Community structure of complex networks. Springer Science & Business Media. https://dl.acm.org/doi/10.1145/2956185
[8] Rossetti, G., & Cazabet, R. (2018). Community discovery in dynamic networks: A survey. ACM Computing Surveys (CSUR), 51(2), 1-37. https://doi.org/10.1145/3172867
[9] Newman, M. E., & Clauset, A. (2016). Structure and inference in annotated networks. Nature Communications, 7(1), 11863. https://doi.org/10.1038/ncomms11863
[10] Zhao, Y. (2017). A survey on theoretical advances of community detection in networks. Wiley Interdisciplinary Reviews: Computational Statistics, 9(5), e1403. https://doi.org/10.1002/wics.1403
[11] Bhowmick, S. S., & Seah, B. S. (2015). Clustering and summarizing protein-protein interaction networks: A survey. IEEE Transactions on Knowledge and Data Engineering, 28(3), 638-658. https://doi.org/10.1109/TKDE.2015.2492559
[12] Khawaja, F. R., et al. (2024). Exploring community detection methods and their diverse applications in complex networks: A comprehensive review. Social Network Analysis and Mining, 14(1), 115. https://doi.org/10.1007/s13278-024-01274-1
[13] Venturini, S. (2023). Complex networks: community detection and graph semi-supervised learning on higher-order networks, with an application to the science of science. https://hdl.handle.net/20.500.14242/160925
[14] Javed, M. A., et al. (2018). Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications, 108, 87-111. https://doi.org/10.1016/j.jnca.2018.02.011
[15] Zhou, S., et al. (2024). A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. ACM Computing Surveys, 57(3), 1-38. https://doi.org/10.1145/3689036
[16] Liu, Y., et al. (2024). Revisiting modularity maximization for graph clustering: A contrastive learning perspective. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. https://doi.org/10.1145/3637528.3671967
[17] Jiang, Y., Jia, C., & Yu, J. (2013). An ecient community detection method based on rank centrality. Physica A: Statistical Mechanics and its Applications, 392(9), 2182-2194. https://doi.org/10.1016/j.physa.2012.12.013
[18] Li, Y., Jia, C., & Yu, J. (2015). A parameter-free community detection method based on centrality and dispersion of nodes in complex networks. Physica A: Statistical Mechanics and its Applications, 438, 321-334. https://doi.org/10.1016/j.physa.2015.06.043
[19] Bai, X., Yang, P., & Shi, X. (2017). An overlapping community detection algorithm based on density peaks. Neurocomputing, 226, 7-15. https://doi.org/10.1016/j.neucom.2016.11.019
[20] Yang, X.-H., et al. (2017). Parameter-free Laplacian centrality peaks clustering. Pattern Recognition Letters, 100, 167-173. https://doi.org/10.1016/j.patrec.2017.10.025
[21] Yuan, X., et al. (2021). A novel density peaks clustering algorithm based on K nearest neighbors with adaptive merging strategy. International Journal of Machine Learning and Cybernetics, 12(10), 2825-2841. https://doi.org/10.21203/rs.3.rs-95747/v1
[22] Guo, W., et al. (2022). Density peak clustering with connectivity estimation. Knowledge-Based Systems, 243, 108501. https://doi.org/10.1016/j.knosys.2022.108501
[23] Yang, Y., et al. (2022). Density clustering with divergence distance and automatic center selection. Information Sciences, 596, 414-438. https://doi.org/10.1016/j.ins.2022.03.027
[24] Hasan, A., & Kamal, A. (2022). LapEFCM: Overlapping community detection using laplacian eigenmaps and fuzzy C-means clustering. International Journal of Information Technology, 14(6), 3133-3144. https://doi.org/10.1007/s41870-022-01028-2
[25] Zhang, C., et al. (2023). Community Deception in Large Networks: Through the Lens of Laplacian Spectrum. IEEE Transactions on Computational Social Systems, 11(2), 2057-2069. https://doi.org/10.1109/TCSS.2023.3268564
[26] Gutman, I., & Zhou, B. (2006). Laplacian energy of a graph. Linear Algebra and its Applications, 414(1), 29-37. https://doi.org/10.1016/j.laa.2005.09.008
[27] Loua , W., & Titouna, F. (2023). PCMeans: Community detection using local PageRank, clustering, and K-means. Social Network Analysis and Mining, 13(1), 103. https://doi.org/10.1007/s13278-023-01109-5
[28] Khan, T. A., et al. (2024). Community Detection and Modularity Analysis in Stack Over ow Network Graphs. In 2024 1st International Conference on Advanced Computing and Emerging Technologies (ACET). IEEE. https://doi.org/10.1109/ACET61898.2024.10730545
[29] Brazinskas, A., Havrylov, S., & Titov, I. (2017). Embedding words as distributions with a Bayesian skip-gram model. arXiv preprint, arXiv:1711.11027. https://aclanthology.org/C18-1151/
[30] Krevl, J.L., & Andrej, A. (2014). SNAP Datasets: Stanford Large Network Dataset Collection. Available from: http://snap.stanford.edu/data 

Files

History

  • Receive Date: 13 August 2025
  • Revise Date: 07 December 2025
  • Accept Date: 16 February 2026

Share

How to cite

Statistics