What question did this study set out to answer?

Investigate the community detection problem in sparse random hypergraphs with non-uniform hyperedge sizes and bounded expected degrees under the hypergraph stochastic block model.

October 9, 2024Combinatorics Probability ComputingOpen Access

Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model

View Full Paper

Ask AI

Bookmark

Investigate the community detection problem in sparse random hypergraphs with non-uniform hyperedge sizes and bounded expected degrees under the hypergraph stochastic block model.
Designed a three-step spectral algorithm consisting of hyperedge selection to maximize the signal-to-noise ratio, spectral partitioning via a regularized adjacency matrix, and correction using adjacency tensors.
Conducted theoretical analyses relying on the concentration and regularization of adjacency matrices for sparse non-uniform random hypergraphs.
Demonstrated that for bounded expected degrees, the algorithm outputs a partition with at least a gamma fraction of vertices classified correctly, with gamma ranging in (0.5, 1) depending on the signal-to-noise ratio.
Proved that the algorithm achieves weak consistency as the signal-to-noise ratio grows slowly with the number of vertices, improving upon prior recovery guarantees.

Discussion

No takes yet. Share an insight, caveat, or question.

Implication

Theoretical analysis reveals a spectral algorithm achieving partial recovery and weak consistency in sparse hypergraphs, indicating improved community detection under low signal-to-noise ratios.

Cite This Study

Dumitriu et al. (2024) studied this question.

synapsesocial.com/papers/6a0fdf5101be78fe81601f39 https://doi.org/10.1017/s0963548324000166

View Full Paper

Ask AI

Bookmark

Implication

Theoretical analysis reveals a spectral algorithm achieving partial recovery and weak consistency in sparse hypergraphs, indicating improved community detection under low signal-to-noise ratios.

Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model

Key Points

Discussion

Implication

Cite This Study

Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model

Key Points

Discussion

Implication

Cite This Study

Also Consider

Also Consider