  We study the computational complexity of a Metropolis-Hastings algorithm for
Bayesian community detection. We first establish a posterior strong consistency
result for a natural prior distribution on stochastic block models under the
optimal signal-to-noise ratio condition in the literature. We then give a set
of conditions that guarantee rapid mixing of a simple Metropolis-Hastings
algorithm. The mixing time analysis is based on a careful study of posterior
ratios and a canonical path argument to control the spectral gap of the Markov
chain.
