Sep, 2015

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

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

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

    May, 2014

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

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

    Apr, 2014

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

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

    Jan, 2016

  • 区块模型阈值猜想的证明

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

    Nov, 2013

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

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

    Sep, 2016

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

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

    Mar, 2015

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

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

    Sep, 2013

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

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

    Apr, 2014

  • 在节点损坏下的随机块模型达到 Kesten-Stigum 阈值

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

    May, 2023

  • 随机块模型与重构

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

    Feb, 2012