Statistical Modelling 15 (6) (2015), 564–589
Model selection and clustering in stochastic block models based on the exact integrated complete data likelihood
Etienne Côme
Université Paris-Est,
IFSTTAR, GRETTIA,
Noisy-Le-Grand,
France
Pierre Latouche
Laboratoire SAMM,
Université Paris 1 Panthéon-Sorbonne,
France
e-mail: pierre.latouche@univ-paris1.fr
Abstract:
The stochastic block model (SBM) is a mixture model for the clustering of nodes in networks. The SBM has now been employed for more than a decade to analyze very different types of networks in many scientific fields, including biology and the social sciences. Recently, an analytical expression based on the collapsing of the SBM parameters has been proposed, in combination with a sampling procedure that allows the clustering of the vertices and the estimation of the number of clusters to be performed simultaneously. Although the corresponding algorithm can technically accommodate up to 10 000 nodes and millions of edges, the Markov chain, however, tends to exhibit poor mixing properties, that is, low acceptance rates, for large networks. Therefore, the number of clusters tends to be highly overestimated, even for a very large number of samples. In this article, we rely on a similar expression, which we call the integrated complete data log likelihood, and propose a greedy inference algorithm that focuses on maximizing this exact quantity. This algorithm incurs a smaller computational cost than existing inference techniques for the SBM and can be employed to analyze large networks (several tens of thousands of nodes and millions of edges) with no convergence problems. Using toy datasets, the algorithm exhibits improvements over existing strategies, both in terms of clustering and model selection. An application to a network of blogs related to illustrations and comics is also provided.
Keywords:
greedy inference; Integrated classification likelihood; networks; random graphs; stochastic block models.
Downloads:
Example data and code in
zipped archive
back