本研究通过渐近分析证明,若随机块模型中连接概率符合一定条件,则节点标签的真实估计无法与真实标签正相关,这一结论适用于固定连接概率以及随着节点数增加而连接概率下降的情况。
Sep, 2016
本文研究了稀疏种植分区模型(即随机块模型)中的聚类阈值问题,证明了在某些情况下聚类是不可能的,并提供一种简单高效的算法来估计模型参数。
Feb, 2012
利用半随机模型在社区检测中的效果,展示了一个关于信息论界限的惊人结果,这一结果表明,基于半正定规划的算法比达到信息论界限的任何算法都要健壮。
Nov, 2015
本文考虑二元随机块模型,研究平均误分类顶点的最小分数,结果表明,当群集大小平衡且 μ≠ν 时,平均误分类顶点数量的最小分数由 Q(sqrt(v *))给出,并由局部算法(即置信传播)在边数线性时间内实现,证明技巧基于将群集恢复问题与树重建问题相连,分析置信传播在具有高斯近似的树上的密度演化。
Sep, 2015
研究了随机块模型中谱聚类在社区提取中的性能表现,并表明在最大期望度数的阶数为 $log~n$ 时,谱聚类应用于网络的邻接矩阵时,即使度数很小,也可以一致地恢复出隐藏的社区。
Dec, 2013
本文讨论了随机块模型的精确恢复问题,提出了一个基于半定规划松弛的高效算法,并找到了一个能成功恢复社区的尖锐阈值现象,该算法可以在该阈值上成功地进行聚类。
May, 2014
本文提出了一种算法,用于在恶意干扰下检测包含损坏节点的随机模型中的社区结构,并在 $Z_2$ 同步问题中实现了最优恢复阈值。借助关键的可识别性证明和 Grothendieck 范数的推动效应,该算法突破了 Kesten-Stigum 阈值的技术瓶颈。
May, 2023
在统计学中称为 “块模型”,在理论计算机科学中称为 “种植分区模型” 的随机图模型被研究,研究者在此基础上提出了一个关于稀疏种植分区模型的算法阈值的精确预测,并提供了一种与真实分区相关的高效聚类算法,完善了该猜想的证明。
Nov, 2013
该研究利用稀疏的随机块模型,探究了节点和网络信息的相互作用,证明了一定的阈值可实现高效的局部聚类,而节点信息对恢复性能的影响在阈值以下是很小的。
Apr, 2014
论文提出了信息论阈值的上下界,并进一步证明了当组数较大且特定参数取值时,物理条件下的凝聚阈值是具有严格界限的,若邻居间与组间边缘概率不同,则分配问题可以解决,否则无算法可优于随机。
Jan, 2016