考虑在稀疏随机网络中检测紧密社区的问题,将其形式化为在随机图中测试是否存在密集子图。在本文中,我们研究渐近稀疏情况下的信息理论下限,并比较了各种测试方法的性能,发现我们的检测边界是尖锐的。
Aug, 2013
利用半随机模型在社区检测中的效果,展示了一个关于信息论界限的惊人结果,这一结果表明,基于半正定规划的算法比达到信息论界限的任何算法都要健壮。
Nov, 2015
研究检测大型 Erdős-Rényi 随机图中种植的小型密集社区的问题,并探究其计算复杂性及相变现象,结果可应用于恢复密集社区和逼近最密 $K$- 子图。
Jun, 2014
在统计学中称为 “块模型”,在理论计算机科学中称为 “种植分区模型” 的随机图模型被研究,研究者在此基础上提出了一个关于稀疏种植分区模型的算法阈值的精确预测,并提供了一种与真实分区相关的高效聚类算法,完善了该猜想的证明。
Nov, 2013
该论文证明了随机块模型的一个猜想,提出了一种非对称的社区检测算法,并将其与信念传播和谱方法联系起来,同时展示了信息论计算差距在其中的应用。
Dec, 2015
本文考虑二元随机块模型,研究平均误分类顶点的最小分数,结果表明,当群集大小平衡且 μ≠ν 时,平均误分类顶点数量的最小分数由 Q(sqrt(v *))给出,并由局部算法(即置信传播)在边数线性时间内实现,证明技巧基于将群集恢复问题与树重建问题相连,分析置信传播在具有高斯近似的树上的密度演化。
Sep, 2015
本研究提出了一种新模型 —— 基于度量空间的几何随机图,用于替代传统的离散社区结构模型,并讨论了在稀疏情况下对该模型的位置恢复问题,同时对一种树的信息流模型进行了改进和定理研究。
Jun, 2020
通过邻域扩展构建的修改过的邻接矩阵,展现出弱的 Ramanujan 特性,从而在稀疏图中实现社区检测。
本文研究随机块模型中社区的分割和恢复问题,通过新的分歧函数来确定恢复阈值并提出了一个复杂度为准线性的算法来恢复社区,即使带有重叠部分的多个社区也可以进行恢复和检测。
Mar, 2015
利用标记的随机块模型来识别多种类型相互作用的社区检测问题,证明了检测阈值可以从信度传播的不敏感转换为敏感,进而进行模型推理的相关推理问题从不可能到可能的过渡,并得出了使用信度传播进行社区检测的结果,证明了理论假设的正确性。
Sep, 2012