本文介绍了一种名为 LocalImprove 的算法,应用于设计更好的本地图分区算法,该算法是首个切割改进算法,具有局部性质,可以在更短的时间内运行,同时与 Andersen 和 Lang 的全局算法具有相同的理论保证,解决了先前基于随机行走算法的图谱划分局部算法存在的问题。
Jul, 2013
本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法,解决了设计拥有近似保证的局部图聚类算法的开放性问题,并且其近似保证与 Cheeger 不等式相当。
Apr, 2012
本文介绍了一种使用谱算法的简单多项式时间用于进行图分割的方法,旨在寻找具有网络传导性和诱导子图的低导纳集合,并且提出了一种找到最佳 k 聚类的方法,其中 k 是一个整数,而且这种方法与 Cheeger's inequality 有所不同。
Sep, 2013
本文研究了图分区中的边划分问题,提出了可调节的边和块的两个新概念,基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法,可以大幅度提高图分区的质量和近似比。
Dec, 2020
该论文研究了通过 Laplacian 矩阵中的特征值来优化图的分割,提出了基于谱投影和随机取整的多项式时间算法,并证明得到的上限是最优的。
Nov, 2011
本文提出了一种基于随机游走的局部聚类算法,通过将内部连接性参数考虑入内,改进了先前结果,得到更优秀的聚类精度和 conductance,并探讨了其与全局谱算法之间的联系。
Apr, 2013
本文研究了大规模图的本地算法设计并提出了一种本地聚类算法,该算法可在几乎线性的时间内找到较好的簇,并基于该聚类算法提出了一种划分算法,进而设计了求解对称对角占优矩阵中线性系统的近线性算法,还提出了其他相关结果。
Sep, 2008
该研究证明了基于谱的划分算法可以在保证性能的同时,实现稀疏切割,同时将分析扩展到其他图划分问题中。
Jan, 2013
在半随机图模型中,我们研究了平衡切割问题的精确性和时间复杂度,并且提出了第一个近似线性时间算法,以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。
Jun, 2024
通过提出一种基于正则化 Gromov-Wasserstein 问题的加速近端梯度下降算法,我们解决了图切割问题,并实现了稀疏解,相较于经典谱聚类算法,额外的复杂度仅为 O (log (n)),但效率更高。
Feb, 2024