改善的图聚类
研究了随机块模型中谱聚类在社区提取中的性能表现,并表明在最大期望度数的阶数为 $log~n$ 时,谱聚类应用于网络的邻接矩阵时,即使度数很小,也可以一致地恢复出隐藏的社区。
Dec, 2013
通过统计学的角度研究了有向图聚类问题,将聚类问题建模为有向随机块模型(DSBM)中估计底层社区的过程,并通过最大似然估计(MLE)推断出给定观察到的图结构的最可能的社区分配。此外,还建立了该 MLE 公式与新型流优化启发式算法之间的等价关系,该算法同时考虑了两个重要的有向图统计量:边密度和边方向。在此基础上,提出了两种高效且可解释的有向聚类算法,即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法,从而进一步验证了我们的理论贡献。
Mar, 2024
在无监督学习中,图聚类是一个重要的主题,也有很多实际应用。最近,多视图图聚类因其适用于可访问多个数据源的现实世界实例而受到关注。本文我们正式提出了一种新的模型族,称为 “多视图随机块模型”,用于捕捉这种情况。对于该模型,我们首先研究了在多个图的并集上有效的算法。然后,通过分析每个图的结构,引入了一种新的高效算法,证明其优于先前的方法。此外,我们通过信息理论的下界研究了在该模型中可以实现的极限,并通过实验评估结果证实了我们的结果。
Jun, 2024
本文研究了部分观测加权图的聚类问题,通过凸优化算法找到最小化不一致性的聚类结果,并在 Planted Partition/Stochastic Block Model 上进行了评估。
Apr, 2011
本文研究了基于矩阵浓度不等式的谱超图划分算法的误差边界,研究了一种广义的随机非均匀超图种子分区模型,并证明了这个算法与该模型的一致性结果,为对超图分区理论的了解提供了新的观点。
May, 2015
研究插入聚类和子矩阵定位问题,提出四个算法,每个算法都在困难度更大的情况下无法成功。研究表明,机器学习和统计推断等算法之间的权衡,以及极小化恢复限制可能无法通过多项式时间算法实现。
Feb, 2014
本文研究在通用随机块模型下的实际网络社区层次结构,使用基于非标准化图拉普拉斯矩阵的菲德勒向量的标准递归双分割算法,并在广泛的模型参数范围内证明了该方法的强一致性,包括节点度数 $O (log n)$ 的稀疏网络和连接概率相差几个数量级的多尺度网络。此外,论文通过对合成数据和现实世界例子的演示,展示了算法的性能问题。
Apr, 2020
在统计学中称为 “块模型”,在理论计算机科学中称为 “种植分区模型” 的随机图模型被研究,研究者在此基础上提出了一个关于稀疏种植分区模型的算法阈值的精确预测,并提供了一种与真实分区相关的高效聚类算法,完善了该猜想的证明。
Nov, 2013