A large deviation principle for block models

Abstract We initiate a study of large deviations for block model random graphs in the dense regime. Following 14, we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a ‘symmetric’ phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a ‘symmetry breaking’ regime, where the conditional structure is not a block model with compatible dimensions. This identifies a ‘reentrant phase transition’ phenomenon for this problem – analogous to one established for Erdős–Rényi random graphs 13, 14. Finally, extending the analysis of 34, we identify the precise boundary between the symmetry and symmetry breaking regimes for homomorphism densities of regular graphs and the operator norm on Erdős–Rényi bipartite graphs.