欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Community detection for sparse random hypergraphs
时间  Datetime
2018-12-11 16:00 — 17:00 
地点  Venue
Middle Lecture Room
报告人  Speaker
Yizhe Zhu (朱亦哲)
单位  Affiliation
University of Washington
邀请人  Host
Yaokun Wu
报告摘要  Abstract

The stochastic block model (SBM) is a generative model for random graphs, which has been one of the most fruitful research topics in community detection and clustering. A phase transition behavior for detection was conjecured by Decelle el al. (2011) at the Kesten-Stigum threshold, and was confirmed by Mossel et al. (2012,2013) and Massoulié (2014). Angelini et al. (2015) conjectured the existence of a similar sharp threshold behavior for community detection in random hypergraphs. We solved the positive part of the conjecture: the detection is possible above the threshold, and there is a spectral algorithm which constructs a correlated partition with high probability. We introduced a modified adjacency matrix which counts self-avoiding walks on hypergraphs, whose leading eigenvectors give us a reconstruction of the community structure. In the course of proving our main result, we constructed a coupling between the local neighborhood of random hypergraphs and multitype Poisson Galton-Watson hypertrees, and obtained a weak Ramanujan property for sparse random hypergraphs. This is joint work with Soumik Pal.