块模型的信念传播、鲁棒重构和最优恢复

Sep, 2013

块模型的信念传播、鲁棒重构和最优恢复

Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly

TL;DR用置信传播的变体提出一种重建算法，可以最大化节点正确标记的比例，使用该算法可以重建在正则和泊松树上的 Ising 模型的鲁棒性重构结果，专注于考虑两个块和连接概率为 $a/n$ 和 $b/n$ 的稀疏对称块模型问题。

Abstract

We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities $a/n$ and $b/n$ for inter- and intra-block edge probabilities, respectively. It was recently shown that one can do better than a random guess if and only if $(a-b)^2>2(a

sparse symmetric block models belief propagation reconstruction algorithm ising model poisson trees

发现论文，激发创造

针对种植分区模型的连续性和非重构结果：密集案例

本研究通过渐近分析证明，若随机块模型中连接概率符合一定条件，则节点标签的真实估计无法与真实标签正相关，这一结论适用于固定连接概率以及随着节点数增加而连接概率下降的情况。

Sep, 2016

度相关随机块模型中的密度演化

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

Sep, 2015

随机块模型与重构

本文研究了稀疏种植分区模型（即随机块模型）中的聚类阈值问题，证明了在某些情况下聚类是不可能的，并提供一种简单高效的算法来估计模型参数。

Feb, 2012

区块模型阈值猜想的证明

在统计学中称为 “块模型”，在理论计算机科学中称为 “种植分区模型” 的随机图模型被研究，研究者在此基础上提出了一个关于稀疏种植分区模型的算法阈值的精确预测，并提供了一种与真实分区相关的高效聚类算法，完善了该猜想的证明。

Nov, 2013

随机块模型中的精确恢复

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

May, 2014

从受审查的边缘测量中解码二进制节点标签：相变和高效恢复

利用半定规划及二元变量，针对含有噪声的观测变量和图的边缘矩阵进行数据重构和分析，可以对图中两个社区及其相关性进行分析与检测。

Apr, 2014

随机块模型中的不可重构性

在平均度数不变的情况下，考虑了随机块模型中聚类（或重构）的问题。通过新的非重新构建和块模型与具有相同平均度数的 Erdős-Rényi 模型的不可区分性之间的联系，给出了聚类不可能的充分条件。

Apr, 2014

标记随机块模型中的最优簇恢复

本文针对标记随机块模型中的社群检测或聚类问题研究了一种基于谱方法的算法，通过观察随机标签，找到至多 s 个错误分类项的聚类算法，并给出了该算法的时间复杂度为 O (npolylog (n))。

Oct, 2015

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

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

Dec, 2015

聚类标记块模型中的全局和局部信息

该研究利用稀疏的随机块模型，探究了节点和网络信息的相互作用，证明了一定的阈值可实现高效的局部聚类，而节点信息对恢复性能的影响在阈值以下是很小的。

Apr, 2014