Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01pv63g3347
DC FieldValueLanguage
dc.contributor.authorChin, Byron-
dc.date.accessioned2021-07-27T17:35:20Z-
dc.date.available2021-07-27T17:35:20Z-
dc.date.created2021-04-30-
dc.date.issued2021-07-27-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp01pv63g3347-
dc.description.abstractThis paper is motivated by the reconstruction problem on the sparse stochastic block model. The paper “Belief Propagation, Robust Reconstruction and Optimal Recovery of Block Models” by Mossel, Neeman, and Sly provided and proved a reconstruction algorithm that recovers an optimal fraction of the communities in the symmetric, 2-community case. The main contribution of their proof is to show that when the signal to noise ratio is sufficiently large, in particular λ^2d > C, the reconstruction accuracy on a tree with or without noise on the leaves is asymptotically the same. This paper will generalize their results, including the main step, to a general class of the sparse stochastic block model with any number of communities that are not necessarily symmetric, proving that an algorithm closely related to Belief Propagation recovers an optimal fraction of community labels.en_US
dc.format.mimetypeapplication/pdf
dc.language.isoenen_US
dc.titleOptimal Reconstruction of General Sparse Stochastic Block Modelsen_US
dc.typePrinceton University Senior Theses
pu.date.classyear2021en_US
pu.departmentMathematicsen_US
pu.pdf.coverpageSeniorThesisCoverPage
pu.contributor.authorid920151089
pu.mudd.walkinNoen_US
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat