Exact Recovery of Stochastic Block Model by Ising Model

In this paper, we study the phase transition property of an Ising model defined on a special random graph-the stochastic block model (SBM). Based on the Ising model, we propose a stochastic estimator to achieve the exact recovery for the SBM. The stochastic algorithm can be transformed into an optimization problem, which includes the special case of maximum likelihood and maximum modularity. Additionally, we give an unbiased convergent estimator for the model parameters of the SBM, which can be computed in constant time. Finally, we use metropolis sampling to realize the stochastic estimator and verify the phase transition phenomenon thfough experiments.

Automated summary

This paper studies the phase transition property of an Ising model on a stochastic block model, proposing a stochastic estimator for exact recovery and an unbiased convergent estimator for model parameters that can be computed in constant time. The stochastic algorithm can be transformed into an optimization problem, including special cases like maximum likelihood and maximum modularity. Metropolis sampling is used to verify the phase transition phenomenon through experiments.