研究随机图中将顶点划分为块的谱技术,通过修改邻接谱分区算法,只需估计通信概率矩阵的秩上限,从而在模型错配的情况下实现一致性,也适用于具有多种模态的邻接表以及有向或无向的图。
May, 2012
本文基于之前的研究,在计算机视觉中解决超图分割的问题,并提出可以证明的高效分割算法,同时对各种超图分割方案进行了详细的实证比较。
Feb, 2016
本文研究在通用随机块模型下的实际网络社区层次结构,使用基于非标准化图拉普拉斯矩阵的菲德勒向量的标准递归双分割算法,并在广泛的模型参数范围内证明了该方法的强一致性,包括节点度数 $O (log n)$ 的稀疏网络和连接概率相差几个数量级的多尺度网络。此外,论文通过对合成数据和现实世界例子的演示,展示了算法的性能问题。
Apr, 2020
本文提出了一种新算法 —— 最大似然凸化版本,用于解决在随机块模型环境下的社交网络图聚类问题,相较于目前已有算法,本文算法在允许普遍规模的簇大小时的表现高出多项式因子。
Oct, 2012
本文研究了稀疏种植分区模型(即随机块模型)中的聚类阈值问题,证明了在某些情况下聚类是不可能的,并提供一种简单高效的算法来估计模型参数。
Feb, 2012
本文提出了一种基于广义非回旋 Hashimoto 矩阵的谱方法,用于从超边集合中的节点分配到社区的问题,并在稀疏区域分析其性能,结果表明此方法能够检测到社区,同时具有更简单、完全非参数化的重要优点,并且能够在不事先知道超边生成规则的情况下进行学习。
Jul, 2015
探索仅具有多向相似性度量的多向测量设置,开发两种算法:Hypergraph Spectral Clustering(HSC)和 Hypergraph Spectral Clustering with Local Refinement(HSCLR),并取得在二元加权边缘情况下的优异结果。
May, 2018
研究了随机块模型中谱聚类在社区提取中的性能表现,并表明在最大期望度数的阶数为 $log~n$ 时,谱聚类应用于网络的邻接矩阵时,即使度数很小,也可以一致地恢复出隐藏的社区。
Dec, 2013
本文介绍一种通过嵌入过程估算随机块模型中节点的块成员资格的方法,并证明了该方法的一致性和可靠性,可用于大规模图形和参与虚拟谱聚类等应用。
Aug, 2011
提出了一种新的超图聚类技术,称为不均匀超图划分,其将不同的代价分配给不同的超图切割,证明了如果不均匀代价满足次模性约束,则不均匀划分产生了最优解的二次近似,并证明了在许多应用中可以获得显着的性能改进。
Sep, 2017