论文标题
用$ Q $社区对模型的最佳恢复
Optimal Recovery of Block Models with $q$ Communities
论文作者
论文摘要
本文是由稀疏随机块模型上的重建问题激发的。 Mossel，Neeman和Sly提供的“信念繁殖，强大的重建和最佳回收模型”提供并证明并证明了一种重建算法，该算法在2个社区案例中恢复了社区的最佳部分。他们证明的主要步骤是表明，当信号与噪声比足够大，尤其是$θ^2d> c $时，则在常规树上的重建精度有或在叶子上没有噪声的情况相同。本文将把他们的结果（包括主要步骤）推广到任何数量的社区，提供与信仰传播有关的算法，该算法恢复了社区标签的最佳部分。
This paper is motivated by the reconstruction problem on the sparse stochastic block model. The paper "Belief Propagation, robust reconstruction and optimal recovery of block models" by Mossel, Neeman, and Sly provided and proved a reconstruction algorithm that recovers an optimal fraction of the communities in the 2 community case. The main step in their proof was to show that when the signal to noise ratio is sufficiently large, in particular $θ^2d > C$, the reconstruction accuracy on a regular tree with or without noise on the leaves is the same. This paper will generalize their results, including the main step, to any number of communities, providing an algorithm related to Belief Propagation that recovers a provably optimal fraction of community labels.
