Towards an Occam Factor for Random Graphs

Abstract

The increasing ubiquity of network data in the digital age has demonstrated the necessity of statistical tools designed to estimate and infer from appropriate random graph models. We seek the eventual development of a model selection criterion --- the eponymous Occam factor --- for random graphs founded upon the evidence/flexibility paradigm due to Rougier and Priebe; such choice of model permits one to implement methods and procedures appropriate to that model as determined by its analytical properties. We demonstrate, in particular, how theoretical results for the stochastic blockmodel (SBM) lead to Expectation-Solution algorithms which take explicit advantage of the curved-Gaussian mixture limiting distributions of an observed graph's adjacency and Laplacian spectral embeddings; this method demonstrates improved clustering performance over established methods. We next demonstrate how the evidence/flexibility paradigm may be used to perform model selection in an idealized exponential family setting. Results therein motivate the development of a closed-form conjugate prior distribution for Gaussian models with compound-symmetric variance-covariance. We conclude with a prescripted means of extending the evidence/flexibility paradigm to random graphs.