A Gibbs Sampler for Community Detection in Assortative Stochastic Block Model
摘要
Community detection is a classical problem in network analysis. It aims at clustering nodes so that the edge density is high within a group and low between groups. The stochastic block model (SBM) is a generative model well suited to this task. In SBM a community structure is obtained in the assortative case, that is when the probability of an edge between nodes of the same group exceeds that of nodes of different groups. The number k of communities is of pivotal importance and there are several methods to determine it. Recently there has been a surge of interest in full Bayesian approaches that consist of placing a prior on k and designing a Gibbs sampler that explores models of different dimensions. In this work, we focus on the simultaneous estimation of k and the node labels, including assortativity which is usually sacrificed to preserve the conjugacy of the prior distribution on the edge probabilities. In particular, we are after detection regimes where posterior inference benefits by imposing assortative SBM even at the cost of lack of conjugacy.