Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp015q47rr19x
 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 URI: http://arks.princeton.edu/ark:/88435/dsp015q47rr19x 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

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