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 components. 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, making possible large and sparse block models.

This work was supported in part by the PASCAL2 Network of Excellence.