Uniqueness of communities in regular stochastic block models

Abstract

This paper studies the regular stochastic block model comprising \emph{several} communities: each of the $k$ non-overlapping communities, for $k⩾3$, possesses $n$ vertices, each of which has total degree $d$. The values of the intra-cluster degrees (i.e.\ the number of neighbours of a vertex inside the cluster it belongs to) and the inter-cluster degrees (i.e.\ the number of neighbours of a vertex inside a cluster different from its own) are allowed to vary across clusters. We discuss two main results: the first compares the probability measure induced by our model with the uniform measure on the space of $d$-regular graphs on $kn$ vertices, and the second establishes that the clusters, under rather weak assumptions, are unique asymptotically almost surely as $n\to \infty$.

arXiv comment17 pages, 15 without bibliography

References in corpus (13)

• Community structure in social and biological networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Stochastic Block Models and Reconstruction
• Model Selection for Degree-corrected Block Models
• Community Detection in the Labelled Stochastic Block Model
• Equitable random graphs
• Spectral gap in random bipartite biregular graphs and applications
• Spectral partitioning in equitable graphs