Information-theoretic Limits for Community Detection in Network Models

We analyze the information-theoretic limits for the recovery of node labels in several network models, including the stochastic block model, as well as the latent space model. For the stochastic block model, the non-recoverability condition depends on the probabilities of having edges inside a community, and between different communities. For the latent space model, the non-recoverability condition depends on the dimension of the latent space, and how far and spread are the communities in the latent space. We also extend our analysis to dynamic models in which edges not only depend on their endpoints, but also on previously generated edges.