Large deviations of connected components in the stochastic block model.

Abstract

We study the stochastic block model, which is often used to model community structures and study community-detection algorithms. We consider the case of two blocks in regard to its largest connected component and largest biconnected component, respectively. We are especially interested in the distributions of their sizes including the tails down to probabilities smaller than 10^{-800}. For this purpose we use sophisticated Markov chain Monte Carlo simulations to sample graphs from the stochastic block model ensemble. We use these data to study the large-deviation rate function and conjecture that the large-deviation principle holds. Further we compare the distribution to the well-known Erdős-Rényi ensemble, where we notice subtle differences at and above the percolation threshold.