ESTIMATION AND PREDICTION FOR STOCHASTIC BLOCKMODELS FOR GRAPHS WITH LATENT BLOCK STRUCTURE

A statistical approach to a posteriori blockmodeling for graphs is pro posed. The model assumes that the vertices of the graph are partitione d into two unknown blocks and that the probability of an edge between two vertices depends only on the blocks to which they belong. Statisti cal procedures are derived for estimating the probabilities of edges a nd for predicting the block structure from observations of the edge pa ttern only. ML estimators can be computed using the EM algorithm, but this strategy is practical only for small graphs. A Bayesian estimator , based on Gibbs sampling, is proposed. This estimator is practical al so for large graphs. When ML estimators are used, the block structure can be predicted based on predictive likelihood. When Gibbs sampling i s used, the block structure can be predicted from posterior predictive probabilities. A side result is that when the number of vertices tend s to infinity while the probabilities remain constant, the block struc ture can be recovered correctly with probability tending to 1.