Uncertainty quantification for community detection
Abstract: We study the frequentist properties of Bayesian statistical inference for the stochastic block model, with an unknown number of classes of varying sizes. We equip the space of vertex labellings with a prior on the number of classes and, conditionally, a prior on the labels. The number of classes may grow to infinity as a function of the number of vertices, depending on the sparsity of the graph. We derive non-asymptotic posterior contraction rates of the form Pθ0,nΠn(Bn∣Xn)≤ϵn, where Xn is the observed graph, generated according to Pθ0,n, Bn is either {θ0,n} or, in the very sparse case, a ball around θ0,n of known extent, and ϵn is an explicit rate of convergence. These results enable conversion of credible sets to confidence sets. In the sparse case, credible tests are shown to be confidence sets. In the very sparse case, credible sets are enlarged to form confidence sets. Confidence levels are explicit, for each n, as a function of the credible level and the rate of convergence. Hypothesis testing between the number of classes is considered with the help of posterior odds, and is shown to be consistent. Explicit upper bounds on errors of the first and second type and an explicit lower bound on the power of the tests are given. Authors: J. van Waaij, B.J.K. Kleijn (University of Padova, University of Amsterdam)