(Informatics Department, Universitas Ahmad Dahlan, Indonesia)(2) Mohd Ridzwan Yaakub
(Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Malaysia)(3) Azuraliza Abu Bakar
(Faculty of Information Science and Technology, Universiti Kebangsaan Malaysia, Malaysia)*corresponding author
AbstractCommunity detection is an important aspect of complex network analysis, especially in attribute networks where topological structure and attribute information both play a role in community formation. Traditional structure-based methods tend to result in topologically dense but semantically inconsistent communities, while attribute-based approaches can improve semantic coherence but face scalability constraints and high computational costs. On the other hand, graph sparsification techniques have been used to reduce the size of the network, but most focus on structural aspects alone and rarely consider attributes, so the quality of the resulting community is often degraded. This study proposes CPSK (Community Preserving Sparsification based on K-core), a sparsification framework that combines k-core decomposition with attribute-based side weighting. This approach is designed specifically for attribute networks, with the aim of maintaining a balance between structural reduction and community semantic consistency, while improving the efficiency of the detection process. Evaluation of the six datasets showed that CPSK consistently generates more stable and meaningful communities than existing attribute-based community detection methods, while maintaining an edge in computing efficiency on large-scale and heterogeneous networks.
KeywordsCommunity detection; Attributed networks; Graph sparsification; K-Core decomposition; Scalability
|
DOIhttps://doi.org/10.26555/ijain.v11i4.2209 |
Article metricsAbstract views : 286 | PDF views : 68 |
Cite |
Full Text Download
|
References
[1] J. Li et al., “A comprehensive review of community detection in graphs,” Neurocomputing, vol. 600, p. 128169, Oct. 2024, doi: 10.1016/j.neucom.2024.128169.
[2] G. Sperlì, “Community detection in Multimedia Social Networks using an attributed graph model,” Online Soc. Networks Media, vol. 46, p. 100312, May 2025, doi: 10.1016/j.osnem.2025.100312.
[3] M. Rostami, M. Oussalah, K. Berahmand, and V. Farrahi, “Community Detection Algorithms in Healthcare Applications: A Systematic Review,” IEEE Access, vol. 11, no. March, pp. 30247–30272, 2023, doi: 10.1109/ACCESS.2023.3260652.
[4] J. Guo, Q. Liang, and J. Zhao, “F-Deepwalk: A Community Detection Model for Transport Networks,” Entropy, vol. 26, no. 8, p. 715, Aug. 2024, doi: 10.3390/e26080715.
[5] T. Setiadi, M. R. Yaakub, and A. A. Bakar, “Community Detection Methods in Library ’ s Books and Borrowers Social Network Segmentation,” J. Adv. Inf. Technol., vol. 14, no. 6, pp. 1177–1185, 2023, doi: 10.12720/jait.14.6.1177-1185.
[6] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys., vol. 69, no. 2 2, pp. 1–15, 2004, doi: 10.1103/PhysRevE.69.026113.
[7] T. Li et al., “Hierarchical Community Detection by Recursive Partitioning,” J. Am. Stat. Assoc., vol. 117, no. 538, pp. 951–968, Apr. 2022, doi: 10.1080/01621459.2020.1833888.
[8] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. Stat. Mech. Theory Exp., vol. 2008, no. 10, p. P10008, Oct. 2008, doi: 10.1088/1742-5468/2008/10/P10008.
[9] S. Aref and M. Mostajabdaveh, “Analyzing modularity maximization in approximation, heuristic, and graph neural network algorithms for community detection,” J. Comput. Sci., vol. 78, p. 102283, Jun. 2024, doi: 10.1016/j.jocs.2024.102283.
[10] C. Huang and Y. Zhong, “An Algorithm Based on Non-Negative Matrix Factorization for Detecting Communities in Networks,” Mathematics, vol. 12, no. 4, p. 619, Feb. 2024, doi: 10.3390/math12040619.
[11] I. Inuwa-Dutse, M. Liptrott, and I. Korkontzelos, “A multilevel clustering technique for community detection,” Neurocomputing, vol. 441, pp. 64–78, Jun. 2021, doi: 10.1016/j.neucom.2021.01.059.
[12] V. A. Traag and L. Šubelj, “Large network community detection by fast label propagation,” Sci. Rep., vol. 13, no. 1, pp. 1–11, 2023, doi: 10.1038/s41598-023-29610-z.
[13] M. Rostami and M. Oussalah, “A novel attributed community detection by integration of feature weighting and node centrality,” Online Soc. Networks Media, vol. 30, p. 100219, 2022, doi: 10.1016/j.osnem.2022.100219.
[14] E. Alinezhad, B. Teimourpour, M. M. Sepehri, and M. Kargari, “Community detection in attributed networks considering both structural and attribute similarities: two mathematical programming approaches,” Neural Comput. Appl., vol. 32, no. 8, pp. 3203–3220, 2020, doi: 10.1007/s00521-019-04064-5.
[15] X. Zhou, L. Su, X. Li, Z. Zhao, and C. Li, “Community detection based on unsupervised attributed network embedding,” Expert Syst. Appl., vol. 213, p. 118937, 2023, doi: 10.1016/j.eswa.2022.118937.
[16] S. Citraro and G. Rossetti, “Eva: Attribute-Aware Network Segmentation,” in Studies in Computational Intelligence, vol. 881 SCI, Springer, Cham, 2020, pp. 141–151, doi: 10.1007/978-3-030-36687-2_12.
[17] K. Yao, J. Liang, J. Liang, M. Li, and F. Cao, “Multi-view graph convolutional networks with attention mechanism,” Artif. Intell., vol. 307, p. 103708, Jun. 2022, doi: 10.1016/j.artint.2022.103708.
[18] J. Kim, S. Jeong, and S. Lim, “Link Pruning for Community Detection in Social Networks,” Appl. Sci., vol. 12, no. 13, 2022, doi: 10.3390/app12136811.
[19] Z. Liu, H. Wang, G. Wang, Z. Guo, and Y. Zhou, “Link community detection combined with network pruning and local community expansion,” Mod. Phys. Lett. B, vol. 35, no. 5, pp. 4–7, 2021, doi: 10.1142/S0217984921500986.
[20] A. Socievole and C. Pizzuti, “Community Detection in Complex Networks Exploiting Spectral Graph Sparsification for Efficient Disaster Response,” 2025, pp. 189–203, doi: 10.1007/978-3-031-85386-9_14.
[21] A. Socievole and C. Pizzuti, “Efficient community detection in disaster networks using spectral sparsification,” Pervasive Mob. Comput., vol. 113, p. 102106, Oct. 2025, doi: 10.1016/j.pmcj.2025.102106.
[22] A. Socievole and C. Pizzuti, “Community Detection in Dense Networks using Effective Resistance and Link Pruning,” in 2023 International Conference on Information and Communication Technologies for Disaster Management (ICT-DM), Sep. 2023, pp. 1–7, doi: 10.1109/ICT-DM58371.2023.10286913.
[23] M. Hashemi, S. Gong, J. Ni, W. Fan, B. A. Prakash, and W. Jin, “A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation,” in Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence, Aug. 2024, pp. 8058–8066, doi: 10.24963/ijcai.2024/891.
[24] G. Wan and H. Schweitzer, “Edge Sparsification for Graphs via Meta-Learning,” in 2021 IEEE 37th International Conference on Data Engineering (ICDE), Apr. 2021, pp. 2733–2738, doi: 10.1109/ICDE51399.2021.00316.
[25] K. Berahmand, S. Haghani, M. Rostami, and Y. Li, “A new attributed graph clustering by using label propagation in complex networks,” J. King Saud Univ. - Comput. Inf. Sci., vol. 34, no. 5, pp. 1869–1883, May 2022, doi: 10.1016/j.jksuci.2020.08.013.
[26] X.-L. Xu, Y.-Y. Xiao, X.-H. Yang, L. Wang, and Y.-B. Zhou, “Attributed network community detection based on network embedding and parameter-free clustering,” Appl. Intell., vol. 52, no. 7, pp. 8073–8086, May 2022, doi: 10.1007/s10489-021-02779-4.
[27] D. Malhotra and A. Chug, “A modified label propagation algorithm for community detection in attributed networks,” Int. J. Inf. Manag. Data Insights, vol. 1, no. 2, p. 100030, Nov. 2021, doi: 10.1016/j.jjimei.2021.100030.
[28] H. Qing, “Community detection by spectral methods in multi-layer networks,” Appl. Soft Comput., vol. 171, p. 112769, Mar. 2025, doi: 10.1016/j.asoc.2025.112769.
[29] M. Huang and A. Ma, “Community detection in stochastic block models via penalized variational estimation,” J. Stat. Comput. Simul., vol. 95, no. 4, pp. 810–824, Mar. 2025, doi: 10.1080/00949655.2024.2439481.
[30] V. A. Traag, L. Waltman, and N. J. van Eck, “From Louvain to Leiden: guaranteeing well-connected communities,” Sci. Rep., vol. 9, no. 1, pp. 1–12, 2019, doi: 10.1038/s41598-019-41695-z.
[31] K. Sismanis, P. Potikas, D. Souliou, and A. Pagourtzis, “Overlapping community detection using graph attention networks,” Futur. Gener. Comput. Syst., vol. 163, p. 107529, Feb. 2025, doi: 10.1016/j.future.2024.107529.
[32] P. Harsha, S. Obaid, D. Mazumder, Y. Nagendar, and Z. A. Almoussawi, “Multi Resolution based Graph Convolutional Networks for Detecting Communities in Social Networks,” in 2024 International Conference on Intelligent Algorithms for Computational Intelligence Systems (IACIS), Aug. 2024, pp. 1–4, doi: 10.1109/IACIS61494.2024.10721782.
[33] G. Bokov, A. Konovalov, A. Uporova, S. Moiseev, I. Safonov, and A. Radionov, “A Parallel Hierarchical Approach for Community Detection on Large-scale Dynamic Networks,” arXiv, pp. 1–46, 2025, [Online]. Available at: https://arxiv.org/abs/2502.18497.
[34] F. Tang and W. Ding, “Community detection with structural and attribute similarities,” J. Stat. Comput. Simul., vol. 89, no. 4, pp. 668–685, Mar. 2019, doi: 10.1080/00949655.2019.1568435.
[35] J. Cai, J. Hao, H. Yang, Y. Yang, X. Zhao, and Y. Xun, “A new community detection method for simplified networks by combining structure and attribute information,” Expert Syst. Appl., vol. 246, no. June 2023, p. 123103, 2024, doi: 10.1016/j.eswa.2023.123103.
[36] S. Kojaku, F. Radicchi, Y. Y. Ahn, and S. Fortunato, “Network community detection via neural embeddings,” Nat. Commun. , vol. 15, no. 1, pp. 1–10, 2024, doi: 10.1038/s41467-024-52355-w.
[37] M. Malekzadeh and J. A. Long, “A network community structure similarity index for weighted networks,” PLoS One, vol. 18, no. 11, p. e0292018, Nov. 2023, doi: 10.1371/journal.pone.0292018.
[38] A. Ahmad, L. Yuan, D. Yan, G. Guo, J. Chen, and C. Zhang, “Accelerating k-Core Decomposition by a GPU,” in 2023 IEEE 39th International Conference on Data Engineering (ICDE), Apr. 2023, pp. 1818–1831, doi: 10.1109/ICDE55515.2023.00142.
[39] J. Tu, G. Mei, and F. Piccialli, “An improved Nyström spectral graph clustering using k-core decomposition as a sampling strategy for large networks,” J. King Saud Univ. - Comput. Inf. Sci., vol. 34, no. 6, pp. 3673–3684, Jun. 2022, doi: 10.1016/j.jksuci.2022.04.009.
[40] G. Mei, J. Tu, L. Xiao, and F. Piccialli, “An efficient graph clustering algorithm by exploiting k-core decomposition and motifs,” Comput. Electr. Eng., vol. 96, p. 107564, Dec. 2021, doi: 10.1016/j.compeleceng.2021.107564.
[41] K. Sotiropoulos and C. E. Tsourakakis, “Triangle-aware Spectral Sparsifiers and Community Detection,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, Aug. 2021, pp. 1501–1509, doi: 10.1145/3447548.3467260.
[42] Q. Ni, J. Wang, and Z. Tang, “Degree and betweenness-based label propagation for community detection,” J. Comb. Optim., vol. 49, no. 2, p. 21, Mar. 2025, doi: 10.1007/s10878-024-01254-3.
[43] Y. Liu, X. Dong, Y. Gu, and Y. Sun, “Parallel k -Core Decomposition: Theory and Practice,” Proc. ACM Manag. Data, vol. 3, no. 3, pp. 1–27, Jun. 2025, doi: 10.1145/3725332.
[44] X. Zhang, D. Song, and D. Tao, “Ricci Curvature-Based Graph Sparsification for Continual Graph Representation Learning,” IEEE Trans. Neural Networks Learn. Syst., vol. 35, no. 12, pp. 17398–17410, Dec. 2024, doi: 10.1109/TNNLS.2023.3303454.
[45] X. Wu, C.-D. Wang, J.-Q. Lin, W.-D. Xi, and P. S. Yu, “Motif-Based Contrastive Learning for Community Detection,” IEEE Trans. Neural Networks Learn. Syst., vol. 35, no. 9, pp. 11706–11719, Sep. 2024, doi: 10.1109/TNNLS.2024.3367873.
[46] M. Li et al., “Topology-Driven Attribute Recovery for Attribute Missing Graph Learning in Social Internet of Things,” IEEE Internet Things J., vol. 12, no. 11, pp. 16298–16313, 2025, doi: 10.1109/JIOT.2025.3531985.
[47] A. Polanco and M. E. J. Newman, “Hierarchical core-periphery structure in networks,” Phys. Rev. E, vol. 108, no. 2, p. 024311, Aug. 2023, doi: 10.1103/PhysRevE.108.024311.
[48] C. Jia, Y. Li, M. B. Carson, X. Wang, and J. Yu, “Node Attribute-enhanced Community Detection in Complex Networks,” Sci. Rep., vol. 7, no. 1, pp. 1–15, 2017, doi: 10.1038/s41598-017-02751-8.
[49] S. Ali, M. Ahmad, M. A. Beg, I. U. Khan, S. Faizullah, and M. A. Khan, “<scp>SsAG</scp> : Summarization and Sparsification of Attributed Graphs,” ACM Trans. Knowl. Discov. Data, vol. 18, no. 6, pp. 1–22, Jul. 2024, doi: 10.1145/3651619.
[50] S. S. Das, N. A. Arafat, M. Rahman, S. M. Ferdous, A. Pothen, and M. M. Halappanavar, “SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks,” arXiv, pp. 1–26, 2025, [Online]. Available at: https://arxiv.org/abs/2502.10208.
[51] J. Wang, K. Wang, X. Lin, W. Zhang, and Y. Zhang, “Neural Attributed Community Search at Billion Scale,” Proc. ACM Manag. Data, vol. 1, no. 4, pp. 1–25, Dec. 2023, doi: 10.1145/3626738.
[52] F. Tang, J. Li, X. Liu, C. Chang, and L. Teng, “GATFELPA integrates graph attention networks and enhanced label propagation for robust community detection,” Sci. Rep., vol. 15, no. 1, pp. 1–17, 2025, doi: 10.1038/s41598-024-84962-4.
[53] J. Zhao et al., “FS-GNN: Improving Fairness in Graph Neural Networks via Joint Sparsification,” Neurocomputing, vol. 648, p. 130641, Oct. 2025, doi: 10.1016/j.neucom.2025.130641.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0