该研究提出了一种基于谱聚类算法的新方法,可在 Bipartite 随机块模型中使用多项式时间算法实现精确和几乎全面的节点分区恢复,并改进了条件以使用现有算法进行近乎完全恢复,以及使用种植可满足问题与 BSBM(Bipartite 随机块模型)之间的联系进行研究以完全恢复种植任务。
Nov, 2019
通过对 Semidefinite Programming(SDP)放松的最大似然估计进行研究,本文论证了 SDP 放松技术在社区检测中的可行性和通用性。
Feb, 2015
本文讨论了随机块模型的精确恢复问题,提出了一个基于半定规划松弛的高效算法,并找到了一个能成功恢复社区的尖锐阈值现象,该算法可以在该阈值上成功地进行聚类。
May, 2014
本文针对标记随机块模型中的社群检测或聚类问题研究了一种基于谱方法的算法,通过观察随机标签,找到至多 s 个错误分类项的聚类算法,并给出了该算法的时间复杂度为 O (npolylog (n))。
Oct, 2015
在图聚类中,小集群不会妨碍大集群的恢复,并且设计了一个迭代算法通过削片策略从而几乎恢复出所有集群,同时也给出了针对较小集群邻近边更有针对性地探测的主动学习算法。
Feb, 2013
本文研究了学习社区并提供了鲁棒性恢复算法来解决 SBM 中建模误差的问题,SBM 广泛用于各个领域中的社区检测和图划分。我们考虑了两种 adversarial error,并回答了一个开放性问题,证明了我们的算法即使在 k>2 的情况下也可以实现几乎精确的恢复,并证明了我们的算法不仅适用于 SBM 生成的图,还应用于与 SBM 在 Kullback-Leibler 散度上相似的任何图分布。
Nov, 2015
本研究将随机块模型扩展到广义随机块模型,提出了一种使用凸优化和 k 均值算法的程序,用于在存在离群节点的情况下,准确检测社区的聚类。
Apr, 2014
本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题,进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响,并在模型的一些扩展,包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。
Mar, 2018
该文章探讨了在随机超图模型中用于社区检测的随机块模型问题(k-SBM),研究了正确定位问题并表明其存在阈值现象:在阈值以下不可能以非零概率找回社区,而在阈值之上,有一个估计器几乎可以确定性地找回社区。作者还考虑了一种基于半定松弛技术的精确恢复问题的简单有效算法。
Jul, 2018
这份论文调查了随机块模型在社群检测中的基本极限,研究其信息理论和计算统计学等问题,列举了几种主要算法用于实现这些极限,并探讨了其他块模型以及一些待解决的问题。
Mar, 2017