分布式草图缩放图聚类
通过改进的谱聚类方法,利用节点协变量帮助揭示图中的潜在社区,该方法综合考虑了节点上的上下文信息,应用于在大脑扩散 MRI 数据中的大脑图研究中,得到了更易于在神经学上进行解释的社区聚类效果。
Nov, 2014
该研究提出了基于稀疏线性系统和两阶段阈值和压缩感知算法的社区检测问题解决方案,在较小计算量内有效地在 Stochastic Block Model 模型的随机图数据以及真实数据集上实现图的划分。
Aug, 2017
本研究旨在探究超级叠加随机块模型 (SupSBM) 在解决复杂网络社区检测问题中的作用。研究者提出使用新模型可以更精确地捕获局部聚类、短平均路径和社区结构等更真实的网络现象,并进一步证明多个高阶谱聚类方法的性能在该模型下是满足特定的误分类错误率上界的。
Dec, 2018
本文介绍了一种在带符号图中进行$k$路分簇的原则性和理论上可靠的谱方法。我们的方法受到社会平衡理论的启发,旨在将网络分解为不相交的群体,使得同一组中的个体通过尽可能多的正边相连接,而不同组中的个体则尽可能多地连接负边。我们的算法依靠广义特征问题公式,为带符号的随机块模型提供了理论保证。数值实验表明,我们的方法在带符号聚类中比现有方法表现得更好,特别是在大量簇和稀疏测量图的情况下。
Apr, 2019
本研究分析并探讨了基于单节点低维度向量嵌入模型的无监督图表示学习方法在节点对社群标记任务方面的表现,发现相对于经典的基于结构特征的模型,该类模型表现较差且在实践中结果不够稳定,因而在捕获社群结构方面存在局限性。
Jan, 2022
基于非负矩阵分解的概率模型统一了节点聚类和图简化,提供了建模任意图结构的框架。通过将硬聚类放松为软聚类,我们的算法将潜在的困难聚类问题转化为易处理的问题。
Aug, 2023
本研究提出了一种基于顶点嵌入的简单谱聚类算法,通过幂法计算的向量,在接近线性时间内计算顶点嵌入,并在输入图形的自然假设下,算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现,该算法与其他聚类算法相比,具有显著更快的速度,并且产生的聚类准确度基本相同。
Oct, 2023
通过统计学的角度研究了有向图聚类问题,将聚类问题建模为有向随机块模型(DSBM)中估计底层社区的过程,并通过最大似然估计(MLE)推断出给定观察到的图结构的最可能的社区分配。此外,还建立了该MLE公式与新型流优化启发式算法之间的等价关系,该算法同时考虑了两个重要的有向图统计量:边密度和边方向。在此基础上,提出了两种高效且可解释的有向聚类算法,即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法,从而进一步验证了我们的理论贡献。
Mar, 2024
该论文提出了一种集成粗化和模块化最大化的方法,通过有效利用邻接性和节点特征提高聚类准确性,从而在图聚类中克服了当前方法在捕捉真实社区结构和集群内关系、计算效率和识别较小社区方面存在的困难。
Jul, 2024
本研究针对现有属性图聚类方法在大规模图上的高计算成本和内存使用问题,提出了一种无需参数学习的简单聚类方法——可扩展和自适应谱嵌入(SASE)。SASE通过平滑节点特征、使用随机傅里叶特征进行可扩展谱聚类以及自适应选择顺序,有效捕捉全局聚类结构,并在图大小上表现出线性时间和空间复杂度。实验证明,SASE在处理大规模数据集时显著提高了准确率和速度。
Aug, 2024