A Block Model Suitable for Sparse Graphs

Abstract

We introduce a new generative block model for graphs. Vertices (nodes) have mixed memberships in margin components, and edges arise from a multinomial defined over the cartesian product of the margin com-ponents. The model is able to represent block structures of “non-community ” type, that is, it is able to model linkage between margin components. Compared to earlier mixed membership stochastic blockmodels which have a Bernoulli parameterization for the generation of links between each margin component pair, in the new model collapsed Gibbs samplers need to represent only those interactions with realized data in them, mak-ing possible large and sparse block models. 1.