Bayesian model selection of Stochastic Blockmodels for random graphs

A way of solving the problem of which model explains an observation better is Bayesian model selection. In this paper, we applied Bayesian model selection for the simplest graph models: the Erdös-Rényi and Stochastoc Blockmodel graphs. Given the adjacency matrix of a graph, we compared its´ marginal likelihood under different models using direct computation, variational methods and Monte Carlo methods. We compared the success of the methods according to their ability to estimate the correct model order. Both methods gave qualitatively similar results but the Monte Carlo method estimated the true Marginal likelihood more accurately.