Community Detection in the Hypergraph Stochastic Block Model

Abstract

In analyzing social networks, the stochastic block model has been the object of study of recent prolific literature, due to its complex structure that splits individuals into communities based on the likelihood of their interaction. Of particular interest is the problem of community detection in the hypergraph stochastic block model, where the assignment of vertices is recovered by observing the unlabeled graph, in which new phase transition phenomena have been discovered. In the general stochastic block model G k,m(n,p,Q), n vertices are split into m communities of size pi, and each k vertices connect independently with a specific probability based on their community assignment, captured in the m of m connectivity matrix Q. In this thesis, we investigate the problem of exact recovery in the logarithmic degree regime, characterizing the phase transition phenomenon and adapting previously dis- covered tools from the stochastic block model with simple edges. More specifically, we first present previous results on the stochastic block model with simple edges and arbitrary number of communities. We then provide an alternate proof for the case of two communities, which will be used in the hypergraph case. We then provide an alternate algorithm for exact recovery for the general model with arbitrary number of communities. In the second half of the paper we define the hypergraph stochastic block model and we generalize previous results, obtaining a new phase transition threshold, from a theoretical point of view. We provide an overview of possible algorithms for exact recovery, and we conclude by linking it to existing algorithms for hypergraph partition, such as NCut and spectral clustering.