Description-Length Community Detection with Noise-Adaptive Graph Coarsening
DOI:
https://doi.org/10.66525/ijictt130Keywords:
Community Detection, Minimum Description Length, Graph Coarsening, Structural Noise, Network CompressionAbstract
Community detection remains a foundational challenge in network science, with applications ranging from social network analysis to computational biology. Existing methods often struggle with large-scale graphs heavily corrupted by structural noise, leading to suboptimal clustering performance and prohibitive computational costs. This paper introduces a novel framework for description-length community detection integrated with a noise-adaptive graph coarsening mechanism. By formulating community detection through the minimum description length principle, the proposed methodology identifies the optimal network partition that most efficiently compresses the network topology. To address the dual challenges of scalability and structural noise, we develop a noise-adaptive coarsening algorithm that selectively contracts edges based on local topological similarity and estimated noise probabilities. This preprocessing step effectively filters out spurious connections while preserving the mesoscopic community structure, significantly accelerating the subsequent description-length optimization. Comprehensive theoretical analysis demonstrates that our coarsening approach strictly bounds the approximation error of the description length objective. Extensive evaluations on diverse synthetic and real-world network datasets indicate that the proposed framework achieves superior performance in clustering accuracy and computational efficiency compared to state-of-the-art baselines. The integration of noise robustness into information-theoretic community detection offers a scalable and theoretically grounded solution for mining complex, noisy networks.
Downloads
References
1. Zhao, R., Zeng, W., Tang, J., Li, Y., Ye, G., Du, J., & Zhao, X. (2025, May). Towards unsupervised entity alignment for highly heterogeneous knowledge graphs. In 2025 IEEE 41St international conference on data engineering (ICDE) (pp. 3792-3806). IEEE.
2. Zhao, R., Zeng, W., Zhang, W., Zhao, X., Tang, J., & Chen, L. (2025). Towards temporal knowledge graph alignment in the wild. arXiv preprint arXiv:2507.14475.
3. Wang, F., Zhang, Z., Sun, L., Ye, J., & Yan, Y. (2022, April). Dirie: Knowledge graph embedding with dirichlet distribution. In Proceedings of the ACM Web Conference 2022 (pp. 3082-3091).
4. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Technical Report, Stanford University.
5. Li, B., Zhang, R., Liang, H., Zhang, J., Zhang, J., Chen, X., ... & Wang, J. (2026). Interagent: Physics-based multi-agent command execution via diffusion on interaction graphs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 15253-15265).
6. Yao, Y., Lu, Z., Chen, G., Huang, C., Feng, C., & Quek, T. Q. (2026). Interference Management in ISAC-SAGINs Based on Transformer-Enabled Mean-Field Reinforcement Learning Method. IEEE Transactions on Wireless Communications.
7. Yu, H., Zhang, J., Chen, C., Xiang, T., Fang, Y., Niebles, J. C., & Adeli, E. (2026, March). Socialgen: Modeling multi-human social interaction with language models. In 2026 International Conference on 3D Vision (3DV) (pp. 1-17). IEEE.
8. Song, S., Huang, D., Deng, D., Xiong, H., Tang, Y., Zhao, Y., & Qin, R. (2026). Olbedo: An Albedo and Shading Aerial Dataset for Large-Scale Outdoor Environments. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 6474-6483).
9. Yao, Y., Xiao, W., Miao, P., Chen, G., Yang, H., Chae, C. B., & Wong, K. K. (2026). UAV-RHS-enabled full-duplex ISAC covert system: Robust beamforming and trajectory optimization. IEEE Transactions on Communications.
10. Yao, Y., Xiao, W., Miao, P., Chen, G., Yang, H., Chae, C. B., & Wong, K. K. (2025). UAV-relay-aided secure maritime networks coexisting with satellite networks: robust beamforming and trajectory optimization. IEEE Transactions on Wireless Communications.
11. Liu, Y., Cai, Q., Wang, C., Yang, J., Fan, H., Dong, J., & Chen, S. (2024). Geometry-enhanced attentive multi-view stereo for challenging matching scenarios. IEEE Transactions on Circuits and Systems for Video Technology, 34(8), 7401-7416.
12. Yang, Z., Wei, Y., Li, H., Li, Q., Jiang, L., Sun, L., ... & Peng, H. (2024, October). Adaptive differentially private structural entropy minimization for unsupervised social event detection. In Proceedings of the 33rd ACM international conference on information and knowledge management (pp. 2950-2960).
13. Wuyang Zhang and Shichao Pei. 2026. Your LLM Agent Can Leak Your Data: Data Exfiltration via Backdoored Tool
Use. arXiv:2604.05432 [cs.CR] doi:10.48550/arXiv.2604.05432
14. Li, R., Wang, L., Chen, K., Xu, L., & Fei, A. (2024). Full-duplex NOMA-enabled integrated sensing and communication: Joint transmit and receive beamforming optimization. IEEE Internet of Things Journal, 11(16), 27015-27029.
15. Xiong, F., Xu, H., Wang, Y., Cheng, R., Wang, Y., & Chu, X. (2025, November). Hs-star: Hierarchical sampling for self-taught reasoners via difficulty estimation and budget reallocation. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing (pp. 5539-5555).
16. Wei, Q., Li, R., Bai, W., & Han, Z. (2025). Multi-UAV-enabled energy-efficient data delivery for low-altitude economy: Joint coded caching, user grouping, and UAV deployment. IEEE Internet of Things Journal, 12(14), 27519-27532.
17. Li, Q., Ye, Q., Zhang, N., Zhang, W., & Hu, F. (2025). Digital-twin-enabled industrial IoT: Vision, framework, and future directions. IEEE Wireless Communications, 32(6), 173-181.
18. Li, Y. Z., Zhang, J. P., Chen, Z. Y., Wang, H. C., Zhang, K. X., Hu, S. S., ... & Dudley, M. (2026, September). Growth and Characterization of High-Quality Thick Epitaxial 4H-SiC Wafers for High Voltage Devices. In Defect and Diffusion Forum (Vol. 452, pp. 79-85). Trans Tech Publications Ltd.
19. Li, S. (2025). Momentum, volume and investor sentiment study for us technology sector stocks—A hidden markov model based principal component analysis. PloS one, 20(9), e0331658.
20. Wang, S., Zhang, X., Wang, P., & Li, X. (2026). Design of Magnetic Sensor Array-Based PUFs for IoT Security. IEEE Transactions on Instrumentation and Measurement, 75, 1-9.
21. Li, X., Wang, P., Li, G., Ni, L., & Zhang, Y. (2023). Design of interface circuits and lightweight PUF for TMR sensors. IEEE Sensors Journal, 23(11), 11754-11761.
22. Liang, R., Xu, S., Xie, C., Chen, J., Ren, F., Yang, S., & Yabe, T. (2026). Abstain Mask Retain Core: Time Series Prediction by Adaptive Masking Loss with Representation Consistency. Advances in Neural Information Processing Systems, 38, 99445-99471.
23. Li, S. (2024). Machine Learning in Credit Risk Forecasting — — A Survey on Credit Risk Exposure. Accounting and Finance Research, 13(2), 107-107.
24. Pei, Z., Huang, Q., & Wang, S. (2026). When LLMs develop languages: Symbolic communication for efficient multi-agent reasoning. arXiv preprint arXiv:2606.29354.
25. Yang, Z., Ji, W., Guo, Q., & Wang, Z. (2023, October). Javp: Joint-aware video processing with edge-cloud collaboration for dnn inference. In Proceedings of the 31st ACM International Conference on Multimedia (pp. 9152-9160).
26. Peng, Y., & Li, H. (2023). Benthic foraminiferal morphogroups at the end-Guadalupian extinction in eastern Sichuan Basin, China. Palaeogeography, Palaeoclimatology, Palaeoecology, 618, 111522.
27. Xia, Y., & Ma, J. (2022). Locality-guided global-preserving optimization for robust feature matching. IEEE Transactions on Image Processing, 31, 5093-5108.
28. Tan, Z., Luo, X., Liu, Y., & Zhang, Y. (2026, March). Mask the redundancy: Evolving masking representation learning for multivariate time-series clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 40, No. 30, pp. 25787-25795).
29. Zhao, L., Zhang, Y., Ji, Y., Zeng, A., Gu, F., & Luo, X. (2022, October). Heterogeneous drift learning: classification of mix-attribute data with concept drifts. In 2022 IEEE 9th international conference on data science and advanced analytics (DSAA) (pp. 1-10). IEEE.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Matteo Piras (Author)

This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in the International Journal of Information and Communication Technology Trends (IJICTT) are distributed under a Creative Commons license. This allows readers to freely access, share, and adapt the content for non-commercial purposes, provided proper attribution is given to the original authors. Authors retain copyright of their work.
