Community detection with the canonical ensemble

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.