Uniqueness of communities in regular stochastic block models

2020/02/13 by Sayar Karmakar, Karmakar, Sayar, Moumanti Podder +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2002.05577

openalex publication_date 2020/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper studies the regular stochastic block model comprising several communities: each of the k non-overlapping communities, for k \geqslant 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 → ∞.

Citations

• Community Detection in the Labelled Stochastic Block Model
• Stochastic Block Models and Reconstruction
• The Metropolis algorithm for graph bisection

Related

• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Determining the Number of Communities in Degree-corrected Stochastic Block Models
• Community Detection in the Multi-View Stochastic Block Model
• Exact Recovery in the Stochastic Block Model
• Algorithm independent bounds on community detection problems and associated transitions in stochastic block model graphs