Ilkka Norros (VTT Technical Research Centre of Finland): Regular Decomposition: an information and graph theoretic approach to stochastic block models

A method for compression of large graphs and matrices to a block structure is proposed. Szemerédi's regularity lemma is used as a generic motivation of the significance of stochastic block models. Another ingredient of the method is Rissanen's minimum description length principle (MDL). We propose practical algorithms and provide theoretical results on the accuracy and consistency of the method.