这份论文调查了随机块模型在社群检测中的基本极限,研究其信息理论和计算统计学等问题,列举了几种主要算法用于实现这些极限,并探讨了其他块模型以及一些待解决的问题。
Mar, 2017
我们为随机块模型开发了一种适合性检验方法,采用残差矩阵中最大奇异值作为统计量,并使用随机矩阵理论获得渐进零分布。该检验可以充分检测非块对角结构的交错结构,进而获得一致的序贯检验估计方法来测试不同社区的数量。
Dec, 2014
本文研究随机块模型中社区的分割和恢复问题,通过新的分歧函数来确定恢复阈值并提出了一个复杂度为准线性的算法来恢复社区,即使带有重叠部分的多个社区也可以进行恢复和检测。
Mar, 2015
本文介绍了基于随机块模型的高效算法,可以检测出具有线性大小社区的最优信息论折衷,并且在需要知道模型参数或社区数量的情况下也能够实现社区检测。
Jun, 2015
本文讨论了随机块模型的精确恢复问题,提出了一个基于半定规划松弛的高效算法,并找到了一个能成功恢复社区的尖锐阈值现象,该算法可以在该阈值上成功地进行聚类。
May, 2014
对基于加权随机块模型生成的两个网络的社区成员资格是否相同进行测试,提出了一种基于奇异子空间距离的测试统计量并开发了该统计量的极限分布。在密集图形的加权随机块模型下,模拟结果表明该测试具有正确的第 1 型错误,并在经验功率上表现符合预期。测试的结果逐渐变化。
Nov, 2018
本文主要研究了随机块模型的聚类问题和主动学习的应用,发现在一定条件下,即使在聚类阈值以下,仅仅采样少量的节点标签,也能高概率地完成完整的社区检测,所提供的高效学习算法能够很好地验证这一理论,并通过数值实验进行了验证。
May, 2016
本文研究了学习社区并提供了鲁棒性恢复算法来解决 SBM 中建模误差的问题,SBM 广泛用于各个领域中的社区检测和图划分。我们考虑了两种 adversarial error,并回答了一个开放性问题,证明了我们的算法即使在 k>2 的情况下也可以实现几乎精确的恢复,并证明了我们的算法不仅适用于 SBM 生成的图,还应用于与 SBM 在 Kullback-Leibler 散度上相似的任何图分布。
Nov, 2015
该文章探讨了在随机超图模型中用于社区检测的随机块模型问题(k-SBM),研究了正确定位问题并表明其存在阈值现象:在阈值以下不可能以非零概率找回社区,而在阈值之上,有一个估计器几乎可以确定性地找回社区。作者还考虑了一种基于半定松弛技术的精确恢复问题的简单有效算法。
Jul, 2018
该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型 (MVSBM),我们得出了一个信息论的上界和下界,当 MVSBM 的模型参数超过某个阈值时可以实现准确的社区恢复,否则期望的错误分类节点数将大于一。
Jan, 2024