Mar, 2024

基于最大似然估计的有向图聚类中的随机块模型

PDF
TL;DR通过统计学的角度研究了有向图聚类问题，将聚类问题建模为有向随机块模型（DSBM）中估计底层社区的过程，并通过最大似然估计（MLE）推断出给定观察到的图结构的最可能的社区分配。此外，还建立了该 MLE 公式与新型流优化启发式算法之间的等价关系，该算法同时考虑了两个重要的有向图统计量：边密度和边方向。在此基础上，提出了两种高效且可解释的有向聚类算法，即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法，从而进一步验证了我们的理论贡献。
发现论文，激发创造
  • 动态随机块模型中的谱聚类

    本文介绍了一种基于 Dynamic Stochastic Block Model（DSBM）的方法，使用核函数估计边缘概率张量并进行谱聚类，可适应未知的连续时间点连接概率平滑度、群体成员转换率和聚类数目，并伴随着对估计精度和聚类结果的非渐进性保证。

    May, 2017

  • 随机块模型中谱聚类的一致性

    研究了随机块模型中谱聚类在社区提取中的性能表现，并表明在最大期望度数的阶数为 $log~n$ 时，谱聚类应用于网络的邻接矩阵时，即使度数很小，也可以一致地恢复出隐藏的社区。

    Dec, 2013

  • 多视角随机块模型中的社区检测

    该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型 (MVSBM)，我们得出了一个信息论的上界和下界，当 MVSBM 的模型参数超过某个阈值时可以实现准确的社区恢复，否则期望的错误分类节点数将大于一。

    Jan, 2024

  • 基于凸化的修正度量随机块模型最大化

    本文提出了一种基于凸规划松弛和新的双重加权 $k$- 中位数方法的凸化模块化最大化方法，用于估算 DCSBM 下的隐藏社群，通过实验结果表明本方法相对于文献中现有的最先进方法具有竞争力的性能表现。

    Dec, 2015

  • 动态随机块模型的谱聚类：稀疏平滑性的改进保证

    该论文分析了动态随机块模型下的经典谱聚类算法，提出了更加精细的 DSGB 的稀疏性和平滑度之间的关系描述，同时将保证扩展到了归一化拉普拉斯算子，从而提高了矩阵谱集中度误差下界的精度。

    Feb, 2020

  • 改善的图聚类

    本文提出了一种新算法 —— 最大似然凸化版本，用于解决在随机块模型环境下的社交网络图聚类问题，相较于目前已有算法，本文算法在允许普遍规模的簇大小时的表现高出多项式因子。

    Oct, 2012

  • 标记随机块模型中的最优簇恢复

    本文针对标记随机块模型中的社群检测或聚类问题研究了一种基于谱方法的算法，通过观察随机标签，找到至多 s 个错误分类项的聚类算法，并给出了该算法的时间复杂度为 O (npolylog (n))。

    Oct, 2015

  • 基于谱聚类算法的社区检测分析：一般二分图情形

    本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题，进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响，并在模型的一些扩展，包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。

    Mar, 2018

  • 有向加权网络的社区发现

    本文介绍了一种用于建模有向加权网络的方法 ——Directed Distribution-Free model，它可以更好地解释在多个领域中出现的块状结构，并使用带有理论保证的谱算法来识别社区。

    Sep, 2021

  • 光谱聚类和高维随机块模型

    本文提出了用于网络中的聚类分析的一种新方法，利用谱聚类在随机块模型中发现社区和研究潜在空间模型下的特征向量。

    Jul, 2010