Technical Program

Paper Detail

Paper Title Exact Recovery for a Family of Community-Detection Generative Models
Paper IdentifierMO3.R5.4
Authors Luca Corinzia, Paolo Penna, Luca Mondada, Joachim M. Buhmann, ETH Zürich, Switzerland
Session Community Detection and Graphical Models
Location Saint Victor, Level 3
Session Time Monday, 08 July, 14:30 - 16:10
Presentation Time Monday, 08 July, 15:30 - 15:50
Manuscript  Click here to download the manuscript
Abstract Generative models for networks with communities have been studied extensively for being a fertile ground to establish information-theoretic and computational thresholds. In this paper we propose a new simplistic model for planted generative models called planted Random Energy Model (REM), inspired by Derrida's REM. For this model we provide the asymptotic behaviour of the probability of error for the maximum likelihood estimator and hence the exact recovery threshold. As an application of it, we further consider the 2 non-equally sized community Weighted Stochastic Block Model (2-WSBM) on $h$-uniform hypergraphs, that is equivalent to the planted-REM on both sides of the spectrum, for high and low edge cardinality $h$. We provide upper and lower bounds for the exact recoverability for any $h$, mapping these problems to the aforementioned planted-REM. To the best of our knowledge these are the first consistency results for the 2-WSBM with non-equally sized community and for the 2-WSBM on hypergraphs.