Spectral Detection on Sparse Hypergraphs
arXiv:1507.04113 · doi:10.1109/ALLERTON.2015.7446987
Abstract
We consider the problem of the assignment of nodes into communities from a set of hyperedges, where every hyperedge is a noisy observation of the community assignment of the adjacent nodes. We focus in particular on the sparse regime where the number of edges is of the same order as the number of vertices. We propose a spectral method based on a generalization of the non-backtracking Hashimoto matrix into hypergraphs. We analyze its performance on a planted generative model and compare it with other spectral methods and with Bayesian belief propagation (which was conjectured to be asymptotically optimal for this model). We conclude that the proposed spectral method detects communities whenever belief propagation does, while having the important advantages to be simpler, entirely nonparametric, and to be able to learn the rule according to which the hyperedges were generated without prior information.
arXiv comment8 pages, 5 figures
References in corpus (9)
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Algorithmic barriers from phase transitions
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Constraint satisfaction problems with isolated solutions are hard
- Quiet Planting in the Locked Constraint Satisfaction Problems
- A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
Cited by in corpus (12)
- What are higher-order networks?
- Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
- Community Detection in Large Hypergraphs
- Mapping flows on hypergraphs
- Community detection in the sparse hypergraph stochastic block model
- Spectra of random regular hypergraphs
- Sparse random tensors: Concentration, regularization and applications
- Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
- Community detection in hypergraphs through hyperedge percolation
- Flow-based Community Detection in Hypergraphs
- Multilayer hypergraph clustering using the aggregate similarity matrix
- Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model