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

Physical Review E

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access
  • Access by Xinjiang University

Community detection with the canonical ensemble

Rudy Arthur*

  • *Contact author: R.Arthur@exeter.ac.uk
PDF

Phys. Rev. E 114, 034302 – Published 2 September, 2026

DOI: https://doi.org/10.1103/rt96-mb8q

Abstract

Network community detection is usually considered as an unsupervised learning problem. Given a network, the aim is to partition it using some general-purpose algorithm. In this paper, we instead treat community detection as a hypothesis testing problem. Given a network, we examine the evidence for community structure in the observed network compared to a network generated by a null model. To do this, we define an appropriate test statistic, analogous to a z-score, and discuss several null models derived from maximizing entropy under different constraints. These constraints are imposed in expectation, giving a canonical ensemble rather than the usual microcanonical ensemble. We demonstrate the application of this method on real and synthetic data and contrast our method to Bayesian approaches based on the stochastic block model. We demonstrate that this method gives rigorous answers to concrete questions, which can be more useful to analysts than the output of a generic algorithm.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (64)

  1. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Defining and identifying communities in networks, Proc. Natl. Acad. Sci. USA 101, 2658 (2004).
  2. S. Kojaku and N. Masuda, Finding multiple core-periphery pairs in networks, Phys. Rev. E 96, 052313 (2017).
  3. L. Chen, Q. Yu, and B. Chen, Anti-modularity and anti-community detecting in complex networks, Inf. Sci. 275, 293 (2014).
  4. R. Arthur, Detectability constraints on meso-scale structure in complex networks, PLoS ONE 20, e0317670 (2025).
  5. C. X. Liu, T. J. Alexander, and E. G. Altmann, Nonassortative relationships between groups of nodes are typical in complex networks, PNAS nexus 2, pgad364 (2023).
  6. T. P. Peixoto, Hierarchical block structures and high-resolution model selection in large networks, Phys. Rev. X 4, 011047 (2014).
  7. U. von Luxburg, A tutorial on spectral clustering, Stat. Comput. 17, 395 (2007).
  8. S. White and P. Smyth, A spectral clustering approach to finding communities in graphs, in Proceedings of the 2005 SIAM International Conference on Data Mining (SDM) (SIAM, Philadelphia, PA, 2005), pp. 274–285.
  9. J. Kleinberg, An impossibility theorem for clustering, in Proceedings of the 16th International Conference on Neural Information Processing Systems, NIPS'02 (MIT Press, Cambridge, MA, 2002), pp. 463–470.
  10. U. Von Luxburg, R. C. Williamson, and I. Guyon, Clustering: Science or art? JMLR: Workshop Conf. Proc. 27, 65 (2012).
  11. S. Kojaku and N. Masuda, A generalised significance test for individual communities in networks, Sci. Rep. 8, 7351 (2018).
  12. A. Lancichinetti, F. Radicchi, and J. J. Ramasco, Statistical significance of communities in networks, Phys. Rev. E 81, 046110 (2010).
  13. A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, Finding statistically significant communities in networks, PLoS ONE 6, e18961 (2011).
  14. M. E. J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA 103, 8577 (2006).
  15. C. P. Massen and J. P. K. Doye, Thermodynamics of community structure, arXiv:cond-mat/0610077.
  16. E. Yanchenko and S. Sengupta, A generalized hypothesis test for community structure in networks, Net. Sci. 12, 122 (2024).
  17. J. Zhang and Y. Chen, A hypothesis testing framework for modularity based network community detection, Stat. Sin. 27, 437 (2017).
  18. M. Ankerst, M. M. Breunig, H. P. Kriegel, and J. Sander, OPTICS: Ordering points to identify the clustering structure, ACM Sigmod Record 28, 49 (1999).
  19. R. J. G. B. Campello, D. Moulavi, and J. Sander, Density-based clustering based on hierarchical density estimates, in Pacific-Asia Conference on Knowledge Discovery and Data Mining (Springer, Berlin, 2013), pp. 160–172.
  20. M. Ester, H. P. Kriegel, J. Sander, and X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) (AAAI Press, Reston, VA, 1996), pp. 226–231.
  21. T. Squartini, J. De Mol, F. Den Hollander, and D. Garlaschelli, Breaking of ensemble equivalence in networks, Phys. Rev. Lett. 115, 268701 (2015).
  22. T. P. Peixoto, Descriptive vs. Inferential Community Detection in Networks: Pitfalls, Myths and Half-Truths (Cambridge University Press, Cambridge, 2023).
  23. D. Garlaschelli, F. Den Hollander, and A. Roccaverde, Ensemble nonequivalence in random graphs with modular structure, J. Phys. A: Math. Theor. 50, 015001 (2017).
  24. J. Park and M. E. J. Newman, Statistical mechanics of networks, Phys. Rev. E 70, 066117 (2004).
  25. D. Garlaschelli and M. I. Loffredo, Fitness-dependent topological properties of the world trade web, Phys. Rev. Lett. 93, 188701 (2004).
  26. S. J. Young and E. R. Scheinerman, Random dot product graph models for social networks, in International Workshop on Algorithms and Models for the Web-Graph (Springer, Berlin, 2007), pp. 138–149.
  27. R. Arthur, Discovering block structure in networks, Physica A 613, 128527 (2023).
  28. R. Arthur, Exploring network structure with the density of states, Physica A 674, 130742 (2025).
  29. A. Miyauchi and Y. Kawase, Z-score-based modularity for community detection in networks, PLoS ONE 11, e0147805 (2016).
  30. A. B. Owen, Karl Pearson's meta-analysis revisited, Ann. Stat. 37, 3867 (2009).
  31. J. Reichardt and S. Bornholdt, When are networks truly modular? Physica D 224, 20 (2006).
  32. G. Bianconi, Entropy of network ensembles, Phys. Rev. E 79, 036114 (2009).
  33. G. Bianconi, Maximum entropy models for complex networks, lecture slides, London Taught Course Centre (Queen Mary University of London, 2022).
  34. L. J. O'Connor, M. Medard, and S. Feizi, Maximum likelihood embedding of logistic random dot product graphs, in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI Press, Reston, VA, 2020), pp. 5289–5297.
  35. M. Di Vece, D. Garlaschelli, and T. Squartini, Gravity models of networks: Integrating maximum-entropy and econometric approaches, Phys. Rev. Res. 4, 033105 (2022).
  36. P. Expert, T. S. Evans, V. D. Blondel, and R. Lambiotte, Uncovering space-independent communities in spatial networks, Proc. Natl. Acad. Sci. USA 108, 7663 (2011).
  37. T. Squartini, R. Mastrandrea, and D. Garlaschelli, Unbiased sampling of network ensembles, New J. Phys. 17, 023052 (2015).
  38. D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Math. Program. 45, 503 (1989).
  39. https://lbfgspp.statr.me
  40. Seconds to minutes on Intel(R) Core(TM) i5-1145G7 @ 2.60 GHz.
  41. A. Condon and R. M. Karp, Algorithms for graph partitioning on the planted partition model, Random Struct. Alg. 18, 116 (2001).
  42. B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83, 016107 (2011).
  43. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Phys. Rev. E 84, 066106 (2011).
  44. H. Kesten and B. P. Stigum, A limit theorem for multidimensional Galton-Watson processes, Ann. Math. Stat. 37, 1211 (1966).
  45. L. Gulikers, M. Lelarge, and L. Massoulié, An impossibility result for reconstruction in the degree-corrected stochastic block model, Ann. Appl. Probab. 28, 3002 (2018).
  46. L. Peel, T. P. Peixoto, and M. De Domenico, Statistical inference links data and theory in network science, Nat. Commun. 13, 6794 (2022).
  47. T. P. Peixoto, Bayesian stochastic blockmodeling, in Advances in Network Clustering and Blockmodeling, edited by P. Doreian, V. Batagelj, and A. Ferligoj (Wiley, New York, 2019), pp. 289–332.
  48. J. Rissanen, A universal prior for integers and estimation by minimum description length, Ann. Stat. 11, 416 (1983).
  49. T. P. Peixoto, Nonparametric Bayesian inference of the microcanonical stochastic block model, Phys. Rev. E 95, 012317 (2017).
  50. F. Giuffrida, T. Squartini, P. Grünwald, and D. Garlaschelli, Description length of canonical and microcanonical models, Phys. Rev. Res. 7, 043057 (2025).
  51. W. W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res. 33, 452 (1977).
  52. L. A. Adamic and N. Glance, The political blogosphere and the 2004 US election: Divided they blog, in Proceedings of the 3rd International Workshop on Link Discovery, KDD'05 (ACM Press, New York, NY, 2005), pp. 36–43.
  53. J. B. Tenenbaum, V. de Silva, and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science 290, 2319 (2000).
  54. S. Emmons and P. J. Mucha, Map equation with metadata: Varying the role of attributes in community detection, Phys. Rev. E 100, 022301 (2019).
  55. L. Peel, D. B. Larremore, and A. Clauset, The ground truth about metadata and community detection in networks, Sci. Adv. 3, e1602548 (2017).
  56. M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004).
  57. M. Rosvall and C. T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA 105, 1118 (2008).
  58. J. P. A. Ioannidis, Why most published research findings are false, PLoS Med. 2, e124 (2005).
  59. J. P. Simmons, L. D. Nelson, and U. Simonsohn, False-positive psychology: Undisclosed flexibility in data collection and analysis allows presenting anything as significant, Psychol. Sci. 22, 1359 (2011).
  60. O. J. Dunn, Multiple comparisons among means, J. Am. Stat. Assoc. 56, 52 (1961).
  61. Y. Benjamini and Y. Hochberg, Controlling the false discovery rate: A practical and powerful approach to multiple testing, J. R. Stat. Soc. B 57, 289 (1995).
  62. L. Anselin, An introduction to spatial data science with GeoDa, in Exploring Spatial Data (Chapman and Hall/CRC Press, Boca Raton, FL, 2024), Vol. 1.
  63. R. Arthur, Correlation and autocorrelation of data on complex networks, EPJ Data Sci. 14, 6 (2025).
  64. B. Efron and T. Hastie, Computer Age Statistical Inference, Student Edition: Algorithms, Evidence, and Data Science (Cambridge University Press, Cambridge, 2021), Vol. 6.

Outline

Information

Phys. Rev. E 114, 034302– Published 2 September, 2026
  • Received 8 May 2026
  • Accepted 18 August 2026
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation