论文标题
稀疏的随机超图：非背带光谱和社区检测
Sparse random hypergraphs: Non-backtracking spectra and community detection
论文作者
论文摘要
假设$ g $是根据HyperGraph随机块模型（HSBM）产生的，我们将考虑稀疏$ Q $均匀的HyperGraph $ G $中的社区检测问题。我们证明，基于超图的非折线操作员的光谱方法具有很高的概率，降低了Angelini等人猜想的广义kesten-Stigum检测阈值。 （2015）。我们表征了稀疏HSBM的非折线操作员的频谱，并使用Ihara-Bass公式为超图提供有效的尺寸降低程序。结果，可以将稀疏HSBM的社区检测减少为$ 2N \ times 2n $非正态矩阵的特征向量问题，该矩阵由邻接矩阵和超级格言的度矩阵构建。据我们所知，这是第一种可证明，有效的光谱算法，它可以根据一般对称的概率张量生成$ r $ $块的HSBMS阈值。
We consider the community detection problem in a sparse $q$-uniform hypergraph $G$, assuming that $G$ is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs works with high probability down to the generalized Kesten-Stigum detection threshold conjectured by Angelini et al. (2015). We characterize the spectrum of the non-backtracking operator for the sparse HSBM and provide an efficient dimension reduction procedure using the Ihara-Bass formula for hypergraphs. As a result, community detection for the sparse HSBM on $n$ vertices can be reduced to an eigenvector problem of a $2n\times 2n$ non-normal matrix constructed from the adjacency matrix and the degree matrix of the hypergraph. To the best of our knowledge, this is the first provable and efficient spectral algorithm that achieves the conjectured threshold for HSBMs with $r$ blocks generated according to a general symmetric probability tensor.
