  In a sparse stochastic block model with two communities of unequal sizes we
derive two posterior concentration inequalities, that imply (1) posterior
(almost-)exact recovery of the community structure under sparsity bounds
comparable to well-known sharp bounds in the planted bi-section model; (2) a
construction of confidence sets for the community assignment from credible
sets, with finite graph sizes. The latter enables exact frequentist uncertain
quantification with Bayesian credible sets at non-asymptotic graph sizes, where
posteriors can be simulated well. There turns out to be no proportionality
between credible and confidence levels: for given edge probabilities and a
desired confidence level, there exists a critical graph size where the required
credible level drops sharply from close to one to close to zero. At such graph
sizes the frequentist decides to include not most of the posterior support for
the construction of his confidence set, but only a small subset of community
assignments containing the highest amounts of posterior probability (like the
maximum-a-posteriori estimator). It is argued that for the proposed
construction of confidence sets, a form of early stopping applies to MCMC
sampling of the posterior, which would enable the computation of confidence
sets at larger graph sizes.
