动态随机块模型的谱聚类:稀疏平滑性的改进保证
本文介绍了一种基于 Dynamic Stochastic Block Model(DSBM)的方法,使用核函数估计边缘概率张量并进行谱聚类,可适应未知的连续时间点连接概率平滑度、群体成员转换率和聚类数目,并伴随着对估计精度和聚类结果的非渐进性保证。
May, 2017
研究了随机块模型中谱聚类在社区提取中的性能表现,并表明在最大期望度数的阶数为 $log~n$ 时,谱聚类应用于网络的邻接矩阵时,即使度数很小,也可以一致地恢复出隐藏的社区。
Dec, 2013
本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题,进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响,并在模型的一些扩展,包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。
Mar, 2018
通过统计学的角度研究了有向图聚类问题,将聚类问题建模为有向随机块模型(DSBM)中估计底层社区的过程,并通过最大似然估计(MLE)推断出给定观察到的图结构的最可能的社区分配。此外,还建立了该 MLE 公式与新型流优化启发式算法之间的等价关系,该算法同时考虑了两个重要的有向图统计量:边密度和边方向。在此基础上,提出了两种高效且可解释的有向聚类算法,即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法,从而进一步验证了我们的理论贡献。
Mar, 2024
通过对随机块模型和其延伸的研究,我们表明,通过正规化可以显著提高谱聚类的性能,并且证明了利用正规化参数估计的数据驱动技术 DKest 可以很好地应用于实际数据集和仿真数据集。
Dec, 2013
本文提出了一种基于凸规划松弛和新的双重加权 $k$- 中位数方法的凸化模块化最大化方法,用于估算 DCSBM 下的隐藏社群,通过实验结果表明本方法相对于文献中现有的最先进方法具有竞争力的性能表现。
Dec, 2015
本文研究在通用随机块模型下的实际网络社区层次结构,使用基于非标准化图拉普拉斯矩阵的菲德勒向量的标准递归双分割算法,并在广泛的模型参数范围内证明了该方法的强一致性,包括节点度数 $O (log n)$ 的稀疏网络和连接概率相差几个数量级的多尺度网络。此外,论文通过对合成数据和现实世界例子的演示,展示了算法的性能问题。
Apr, 2020