  An efficient MCMC algorithm is presented to cluster the nodes of a network
such that nodes with similar role in the network are clustered together. This
is known as block-modelling or block-clustering. The model is the stochastic
blockmodel (SBM) with block parameters integrated out. The resulting marginal
distribution defines a posterior over the number of clusters and cluster
memberships. Sampling from this posterior is simpler than from the original SBM
as transdimensional MCMC can be avoided. The algorithm is based on the
allocation sampler. It requires a prior to be placed on the number of clusters,
thereby allowing the number of clusters to be directly estimated by the
algorithm, rather than being given as an input parameter. Synthetic and real
data are used to test the speed and accuracy of the model and algorithm,
including the ability to estimate the number of clusters. The algorithm can
scale to networks with up to ten thousand nodes and tens of millions of edges.
