多聚类随机块模型中的检测：实现猜想的证明，无环 BP 和信息计算差距

Dec, 2015

多聚类随机块模型中的检测：实现猜想的证明，无环 BP 和信息计算差距

Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap

PDF

Emmanuel Abbe, Colin Sandon

TL;DR该论文证明了随机块模型的一个猜想，提出了一种非对称的社区检测算法，并将其与信念传播和谱方法联系起来，同时展示了信息论计算差距在其中的应用。

Abstract

In a paper that initiated the modern study of the stochastic block model, Decelle et al., backed by Mossel et al., made the following conjecture: Denote by $k$ the number of balanced communities, $a/n$ the probability of connecting inside communities and $b/n$ across, and set $\mathrm{

stochastic block model community detection belief propagation spectral methods information-theoretic

发现论文，激发创造

一般随机块模型下的社区发现：基本限制和高效恢复算法

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

Mar, 2015

社群检测与随机块模型

这份论文调查了随机块模型在社群检测中的基本极限，研究其信息理论和计算统计学等问题，列举了几种主要算法用于实现这些极限，并探讨了其他块模型以及一些待解决的问题。

Mar, 2017

多视角随机块模型中的社区检测

该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型 (MVSBM)，我们得出了一个信息论的上界和下界，当 MVSBM 的模型参数超过某个阈值时可以实现准确的社区恢复，否则期望的错误分类节点数将大于一。

Jan, 2024

基于随机块模型的超图：统计极限和半定规划方法

该文章探讨了在随机超图模型中用于社区检测的随机块模型问题（k-SBM），研究了正确定位问题并表明其存在阈值现象：在阈值以下不可能以非零概率找回社区，而在阈值之上，有一个估计器几乎可以确定性地找回社区。作者还考虑了一种基于半定松弛技术的精确恢复问题的简单有效算法。

Jul, 2018

贝叶斯推断问题中的相变类型学

本文通过对稀疏图上的推理问题的描述和分析，研究了随机块模型的相变以及在信息论上最优化问题变得容易但是在计算上仍具挑战性的的混合硬相位，并阐明了消息传递算法的贝叶斯最优性及其在这些问题中的作用，并通过数值模拟验证了该方法的有效性。

Jun, 2018

社区检测重建门槛的稳健性如何？

利用半随机模型在社区检测中的效果，展示了一个关于信息论界限的惊人结果，这一结果表明，基于半正定规划的算法比达到信息论界限的任何算法都要健壮。

Nov, 2015

随机块模型中的精确恢复

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

May, 2014

随机块模型中社群变化的测试

针对随机块模型 (SBM) 中的社区适配性和两样本检验问题以及稀疏模式、信息理论下限等问题，我们提出了计算效率高、能够成功解决这些问题的测试方法。

Nov, 2018

稀疏网络社区检测的信息论门限

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

Jan, 2016

随机块模型中的社区检测主动学习

本文主要研究了随机块模型的聚类问题和主动学习的应用，发现在一定条件下，即使在聚类阈值以下，仅仅采样少量的节点标签，也能高概率地完成完整的社区检测，所提供的高效学习算法能够很好地验证这一理论，并通过数值实验进行了验证。

May, 2016