- 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

Heuristic and exact modularity optimization with size-constrained communities

Filipi N. Silva1, Samin Aref2, Vincent Traag3, and Santo Fortunato4

PDF

Phys. Rev. E 114, 044314 – Published 13 October, 2026

DOI: https://doi.org/10.1103/y6ss-j5qv

Abstract

When searching for communities in networks, domain experts may have some prior expectations about the size of communities. Yet, community detection methods normally do not optimize communities under cluster size constraints. Multiresolution techniques allow users to indirectly control the average community size through changing a resolution parameter, but this practice does not control the size of individual communities. We here study the problem of size-constrained community detection, where the size of all communities is limited to a user-specified range of values, in the context of modularity optimization. We propose a heuristic for modularity optimization under community-size constraints. To demonstrate the reliability of our proposed heuristic, we also formulate an exact integer optimization model and use its results as a baseline. Our analysis based on synthetic benchmarks and real networks demonstrate the issues with the currently common practice of changing resolution parameters and reveal the advantages of the proposed methods as a principled way of obtaining size-constrained communities.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (32)

  1. S. Fortunato, Community detection in graphs, Phys. Rep. 486, 75 (2010).
  2. J. Korczak, M. Pondel, and W. Sroka, in 2019 Federated Conference on Computer Science and Information Systems (FedCSIS) (IEEE, New Jersey, 2019), pp. 675–683.
  3. L. Zhang, J. Priestley, J. DeMaio, S. Ni, and X. Tian, Measuring customer similarity and identifying cross-selling products by community detection, Big Data 9, 132 (2021).
  4. B. Szalkai, C. Kerepesi, B. Varga, and V. Grolmusz, The Budapest reference connectome server v2.0, Neurosci. Lett. 595, 60 (2015).
  5. M. Mokhtaridoost, J. J. Chalmers, M. Soleimanpoor, B. J. McMurray, D. F. Lato, S. C. Nguyen, V. Musienko, J. O. Nash, S. Espeso-Gil, S. Ahmed, K. Delfosse, J. W. L. Browning, A. R. Barutcu, M. D. Wilson, T. Liehr, A. Shlien, S. Aref, E. F. Joyce, A. Weise, and P. G. Maass, Inter-chromosomal contacts demarcate genome topology along a spatial gradient, Nat. Commun. 15, 9813 (2024).
  6. S. A. Quinodoz, N. Ollikainen, B. Tabak, A. Palla, J. M. Schmidt, E. Detmar, M. M. Lai, A. A. Shishkin, P. Bhat, Y. Takei, et al., Higher-order inter-chromosomal hubs shape 3D genome organization in the nucleus, Cell 174, 744 (2018).
  7. J. Dekker, F. Alber, S. Aufmkolk, B. J. Beliveau, B. G. Bruneau, A. S. Belmont, L. Bintu, A. Boettiger, R. Calandrelli, C. M. Disteche, et al., Spatial and temporal organization of the genome: Current state and future aims of the 4D nucleome project, Mol. Cell 83, 2624 (2023).
  8. M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004).
  9. S. Aref and M. Mostajabdaveh, Analyzing modularity maximization in approximation, heuristic, and graph neural network algorithms for community detection, J. Comput. Sci. 78, 102283 (2024).
  10. M. E. J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA 103, 8577 (2006).
  11. S. Fortunato and D. Hric, Community detection in networks: A user guide, Phys. Rep. 659, 1 (2016).
  12. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner, On modularity clustering IEEE Trans. Knowl. Data Eng. 20, 172 (2007).
  13. G. Agarwal and D. Kempe, Modularity-maximizing graph communities via mathematical programming, Eur. Phys. J. B 66, 409 (2008).
  14. T. N. Dinh and M. T. Thai, Toward optimal community detection: From trees to general weighted networks, Internet Mathematics 11, 181 (2015).
  15. S. Aref, M. Mostajabdaveh, and H. Chheda, in Computational Science–ICCS 2023, edited by J. Mikyška, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. Sloot (Springer Nature, Switzerland, Cham, 2023), pp. 612–626.
  16. S. Aref, M. Mostajabdaveh, and H. Chheda, Bayan algorithm: Detecting communities in networks through exact and approximate optimization of modularity, Phys. Rev. E 110, 044315 (2024).
  17. Gurobi Optimization, Inc., Gurobi optimizer reference manual, (2026), https://docs.gurobi.com/current/index.html.
  18. N. Karmarkar, in Proceedings of The Sixteenth Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, NY, 1984), pp. 302–311.
  19. N. X. Vinh, J. Epps, and J. Bailey, Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance, J. Mach. Learn. Res. 11, 2837 (2010).
  20. M. Jerdee, A. Kirkley, and M. Newman, Normalized mutual information is a biased measure for classification and community detection, Nat. Commun. 16, 11268 (2025).
  21. A. Condon and R. M. Karp, Algorithms for graph partitioning on the planted partition model, Random Struct. Algorithms 18, 116 (2001).
  22. A. Ghasemian, P. Zhang, A. Clauset, C. Moore, and L. Peel, Detectability thresholds and optimal algorithms for community structure in dynamic networks, Phys. Rev. X 6, 031005 (2016).
  23. A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms, Phys. Rev. E 78, 046110 (2008).
  24. B. T. Thomas Yeo, F. M. Krienen, J. Sepulcre, M. R. Sabuncu, D. Lashkari, M. Hollinshead, J. L. Roffman, J. W. Smoller, L. Zöllei, J. R. Polimeni, B. Fischl, H. Liu, and R. L. Buckner, The organization of the human cerebral cortex estimated by intrinsic functional connectivity, J. Neurophysiol. 106, 1125 (2011).
  25. L. Fan, H. Li, J. Zhuo, Y. Zhang, J. Wang, L. Chen, Z. Yang, C. Chu, S. Xie, A. R. Laird, et al., The human Brainnetome atlas: A new brain atlas based on connectional architecture, Cereb. Cortex 26, 3508 (2016).
  26. A. Schaefer, R. Kong, E. M. Gordon, T. O. Laumann, X.-N. Zuo, A. J. Holmes, S. B. Eickhoff, and B. T. Yeo, Local-global parcellation of the human cerebral cortex from intrinsic functional connectivity MRI, Cereb. Cortex 28, 3095 (2018).
  27. V. A. Traag, P. Van Dooren, and Y. Nesterov, Narrow scope for resolution-limit-free community detection Phys. Rev. E 84, 016114 (2011).
  28. M. Gösgens, Detecting small and large communities in networks, Ph.D. thesis, Eindhoven University of Technology, 2024.
  29. T. P. Peixoto, The Netzschleuder network catalogue and repository [Computer software], Zenodo, 2020, https://doi.org/10.5281/zenodo.7839981.
  30. GitHub Repository leidenalg, https://github.com/vtraag/leidenalg.
  31. GitHub Repository libleidenalg, https://github.com/vtraag/libleidenalg.
  32. GitHub Repository constrainedmodularity, https://github.com/filipinascimento/constrainedmodularity.

Outline

Information

Phys. Rev. E 114, 044314– Published 13 October, 2026
  • Received 24 May 2026
  • Accepted 11 September 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation