标记随机块模型中的最佳实例聚类恢复
本文介绍了基于随机块模型的高效算法,可以检测出具有线性大小社区的最优信息论折衷,并且在需要知道模型参数或社区数量的情况下也能够实现社区检测。
Jun, 2015
本文针对标记随机块模型中的社群检测或聚类问题研究了一种基于谱方法的算法,通过观察随机标签,找到至多s个错误分类项的聚类算法,并给出了该算法的时间复杂度为O(npolylog(n))。
Oct, 2015
本文提出了一种基于凸规划松弛和新的双重加权$k$-中位数方法的凸化模块化最大化方法,用于估算DCSBM下的隐藏社群,通过实验结果表明本方法相对于文献中现有的最先进方法具有竞争力的性能表现。
Dec, 2015
本文主要研究了随机块模型的聚类问题和主动学习的应用,发现在一定条件下,即使在聚类阈值以下,仅仅采样少量的节点标签,也能高概率地完成完整的社区检测,所提供的高效学习算法能够很好地验证这一理论,并通过数值实验进行了验证。
May, 2016
我们研究了随机块模型(SBM)中具有大型簇和无法恢复的小型簇的图聚类。我们提出了一种基于半定规划(SDP)的算法,可以恢复大型簇而不受其余簇大小的影响。我们的研究结果在存在大量小簇的情况下,达到了更低的样本复杂度,并为递归聚类问题提供了改进的算法。
Aug, 2023
该研究论文以网络聚类为主题,探讨了基于节点属性和网络信息的高性能聚类算法,并通过信息理论准则建立了节点属性和网络信息交换的精确恢复标签的关系,提出了一种迭代聚类算法以最大化联合似然函数,并通过数值实验验证了该算法的优越性。
Oct, 2023
该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型(MVSBM),我们得出了一个信息论的上界和下界,当MVSBM的模型参数超过某个阈值时可以实现准确的社区恢复,否则期望的错误分类节点数将大于一。
Jan, 2024
通过统计学的角度研究了有向图聚类问题,将聚类问题建模为有向随机块模型(DSBM)中估计底层社区的过程,并通过最大似然估计(MLE)推断出给定观察到的图结构的最可能的社区分配。此外,还建立了该MLE公式与新型流优化启发式算法之间的等价关系,该算法同时考虑了两个重要的有向图统计量:边密度和边方向。在此基础上,提出了两种高效且可解释的有向聚类算法,即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法,从而进一步验证了我们的理论贡献。
Mar, 2024
在这篇论文中,我们研究了在一般的二元博弈和高斯矩阵模型中的精确社区恢复问题,这两种模型分别捕捉了随机块模型、子矩阵定位和Z2同步作为特例。我们还研究了有关社区分配标签的智能信息可用的情况,将其建模为通过噪声通道传递真实标签:二进制擦除通道(其中某些社区标签已知而其他被抹去)或二进制对称通道(其中某些标签被翻转)。我们对智能信息对精确恢复的信息论极限的影响提供了统一的分析,扩展了之前的研究并拓展到新的设定。此外,我们设计了一个简单但最优的谱算法,将智能信息(如有)与矩阵观测的特征向量结合起来。利用入元素特征向量分析的强大工具[Abbe, Fan, Wang, Zhong 2020],我们表明我们的谱算法可以模仿所谓的“精灵辅助估计器”,其中第i个精灵辅助估计器在精灵揭示其他标签的情况下,最优计算第i个标签的估计。这一观点为最近的一系列工作中各种精确恢复问题的谱算法的最优性提供了统一的理解。
Jun, 2024