Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model

arXiv:2112.11671v3 Announce Type: replace-cross
Abstract: We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a $\gamma$ fraction of the vertices classified correctly, where $\gamma\in (0.5,1)$ depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly …

abstract algorithm arxiv block community detection general hypergraph interactions math.pr math.st networks random recovery stat.ml stat.th stochastic type uniform