Skip navigation
Please use this identifier to cite or link to this item:
Title: Community Detection in the Hypergraph Stochastic Block Model
Authors: Stoica, Ana Andrea
Advisors: Abbe, Emmanuel
Contributors: Fickenscher, Jon
Department: Mathematics
Class Year: 2016
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.
Extent: 49 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2016

Files in This Item:
File SizeFormat 
Stoica_Ana_Andrea_thesis.pdf395.54 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.