这篇论文主要研究了重叠社区检测的问题,并提出了一种新的估计方法,以及建立了估计误差的下界。
Jul, 2023
本研究提供一个通用 minimax 理论来解决社区检测问题,在广泛的设置中给出了 mis-match ratio 的 minimax 速率,包括同质和非同质 SBMs,密集和稀疏网络,有限和不断增长的社区数量。研究使用了一系列的惩罚最大似然方法来获得一个上界,并通过交换性质将全局 mis-match ratio 降至一个本地聚类问题来实现一个下界。结果同时阐明了在强一致性(精确恢复)和弱一致性(部分恢复)方面的阈值现象。
Jul, 2015
研究了一种基于加权邻接矩阵的随机块模型, 并通过一种基于离散化的算法,利用 Renyi 散度来表征其误差率。
Jun, 2017
利用标记的随机块模型来识别多种类型相互作用的社区检测问题,证明了检测阈值可以从信度传播的不敏感转换为敏感,进而进行模型推理的相关推理问题从不可能到可能的过渡,并得出了使用信度传播进行社区检测的结果,证明了理论假设的正确性。
Sep, 2012
该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型 (MVSBM),我们得出了一个信息论的上界和下界,当 MVSBM 的模型参数超过某个阈值时可以实现准确的社区恢复,否则期望的错误分类节点数将大于一。
Jan, 2024
本研究在考虑顶点度数变化的情况下,提出了一种改进的目标函数用于复杂网络社区结构检测,并提出了一种针对此函数或其非度数校正版本的启发式算法,表明度数校正版本在真实和合成网络中的表现显著优于未校正版本。
Aug, 2010
本文利用统计物理的空穴方法,对社交和生物网络中的随机块模型进行了研究,从拓扑学的角度来推断功能群或社区。我们详细描述了一些性质,例如检测性 / 不可检测性的相变和社区检测问题的易于 / 困难的相变,并将分析自然翻译为信念传播算法。该算法在最优方式下推断节点的组成员资格,并学习该块模型的潜在参数,最后应用于两个真实世界的网络并讨论其性能。
Sep, 2011
本研究比较了标准随机块模型和修正度随机块模型下的几种社区检测准则,发现基于修正度随机块模型的方法在更广泛的模型和约束条件下具有一致性,但实际上它涉及到估计更多的参数,只有当社区内的节点度数确实高度变化时才值得使用。
Oct, 2011
本文针对标记随机块模型中的社群检测或聚类问题研究了一种基于谱方法的算法,通过观察随机标签,找到至多 s 个错误分类项的聚类算法,并给出了该算法的时间复杂度为 O (npolylog (n))。
Oct, 2015
这份论文调查了随机块模型在社群检测中的基本极限,研究其信息理论和计算统计学等问题,列举了几种主要算法用于实现这些极限,并探讨了其他块模型以及一些待解决的问题。
Mar, 2017