本文考虑二元随机块模型，研究平均误分类顶点的最小分数，结果表明，当群集大小平衡且 μ≠ν 时，平均误分类顶点数量的最小分数由 Q（sqrt（v *））给出，并由局部算法（即置信传播）在边数线性时间内实现，证明技巧基于将群集恢复问题与树重建问题相连，分析置信传播在具有高斯近似的树上的密度演化。

Sep, 2015

研究对称数据矩阵中的隐藏社区的恢复问题，聚焦于两种渐近恢复保证类型：弱恢复和精确恢复，并推导出恢复的充分条件和必要条件。结果表明，算法提供弱恢复时，可以通过简单的投票程序在额外线性时间内升级以实现精确恢复。

Sep, 2015

本文提出了一种算法，用于在恶意干扰下检测包含损坏节点的随机模型中的社区结构，并在 $Z_2$ 同步问题中实现了最优恢复阈值。借助关键的可识别性证明和 Grothendieck 范数的推动效应，该算法突破了 Kesten-Stigum 阈值的技术瓶颈。

May, 2023

本研究考虑在具有二元社区标签和 R^d 值位置标签的欧几里得随机几何图上进行社区检测问题，其中边缘概率依赖于社区和位置标签。我们针对稀疏和对数度规则建立了相变现象，并给出了阈值的约束。此外，我们还展示了在我们的模型与没有社区标签的空模型之间进行测试的可区分性问题的阈值没有相变现象，并且特别地与 SBM 不同。

Jun, 2017

在这篇论文中，我们研究了在一般的二元博弈和高斯矩阵模型中的精确社区恢复问题，这两种模型分别捕捉了随机块模型、子矩阵定位和 Z2 同步作为特例。我们还研究了有关社区分配标签的智能信息可用的情况，将其建模为通过噪声通道传递真实标签：二进制擦除通道（其中某些社区标签已知而其他被抹去）或二进制对称通道（其中某些标签被翻转）。我们对智能信息对精确恢复的信息论极限的影响提供了统一的分析，扩展了之前的研究并拓展到新的设定。此外，我们设计了一个简单但最优的谱算法，将智能信息（如有）与矩阵观测的特征向量结合起来。利用入元素特征向量分析的强大工具 [Abbe, Fan, Wang, Zhong 2020]，我们表明我们的谱算法可以模仿所谓的 “精灵辅助估计器”，其中第 i 个精灵辅助估计器在精灵揭示其他标签的情况下，最优计算第 i 个标签的估计。这一观点为最近的一系列工作中各种精确恢复问题的谱算法的最优性提供了统一的理解。

Jun, 2024

论文提出了信息论阈值的上下界，并进一步证明了当组数较大且特定参数取值时，物理条件下的凝聚阈值是具有严格界限的，若邻居间与组间边缘概率不同，则分配问题可以解决，否则无算法可优于随机。

Jan, 2016

本文讨论了随机块模型的精确恢复问题，提出了一个基于半定规划松弛的高效算法，并找到了一个能成功恢复社区的尖锐阈值现象，该算法可以在该阈值上成功地进行聚类。

May, 2014

该研究考虑处理从（少量）被审查的边缘权重观察到的隐藏二进制变量的问题，并描述了两个基于非回溯和 Bethe Hessian 算法的谱算法，在部分恢复问题中表现出渐近最优的特点，一旦可以从信息理论角度进行的时候，便会侦测隐藏分配。

Jan, 2015

通过对 Semidefinite Programming（SDP）放松的最大似然估计进行研究，本文论证了 SDP 放松技术在社区检测中的可行性和通用性。

Feb, 2015

本文研究随机块模型中社区的分割和恢复问题，通过新的分歧函数来确定恢复阈值并提出了一个复杂度为准线性的算法来恢复社区，即使带有重叠部分的多个社区也可以进行恢复和检测。

Mar, 2015