Sep, 2008

大规模图的本地聚类算法及其在近似线性时间图分割中的应用

PDF
TL;DR本文研究了大规模图的本地算法设计并提出了一种本地聚类算法，该算法可在几乎线性的时间内找到较好的簇，并基于该聚类算法提出了一种划分算法，进而设计了求解对称对角占优矩阵中线性系统的近线性算法，还提出了其他相关结果。
发现论文，激发创造
  • 分布式图聚类与稀疏化

    本文提出了一个简单的分布式算法，基于采样方案将输入的密集图转化为稀疏的子图，并在多项式对数回合内完成图的聚类，同时具有高效的实现和处理大数据集的广泛应用。

    Nov, 2017

  • 近似扩张剖面和几乎最优局部图聚类

    本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

    Apr, 2012

  • 寻找密集连接聚类的本地算法

    本文研究了一种基于局部算法的图聚类方法，通过引入新的缩减技术来分析多个集合间的相互关系，并在多个实际数据集上通过恢复密集连接簇来展示算法的有效性。

    Jun, 2021

  • 有效局部搜索增强平衡图边划分

    本文研究了图分区中的边划分问题，提出了可调节的边和块的两个新概念，基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法，可以大幅度提高图分区的质量和近似比。

    Dec, 2020

  • 稀疏随机图上本地算法的限制

    本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小，而且通过聚类属性，我们强调了在随机图上的局部算法存在局限性。

    Apr, 2013

  • 一种用于图形的本地频谱方法：在改善图划分和本地探索数据图中的应用

    本文介绍了拉普拉斯矩阵的第二特征值和相关特征向量在无向图中的基本特征，并提出了第二特征向量的局部偏差模型，用于半监督方式下确定数据图的本地性质和优化问题，从而可以在近线性时间内计算最优解，并提供了在社交和信息网络中找到具有局部偏差的稀疏线性切割的详细实证评价。

    Dec, 2009

  • 寻找密集子图的本地算法

    本文提出一种用于寻找二分图中密集子图的本地算法，通过 Kannan 和 Vinay 提出的密度定义来衡量，在最多 O (Dk^2) 个顶点上，在密度 theta / O (log n) 的情况下找到最接近指定起始点的密集子图，算法的时间复杂度为 O (Dk^2)，与图中的顶点数无关。

    Feb, 2007

  • 基于流的局部图聚类算法

    本文介绍了一种名为 LocalImprove 的算法，应用于设计更好的本地图分区算法，该算法是首个切割改进算法，具有局部性质，可以在更短的时间内运行，同时与 Andersen 和 Lang 的全局算法具有相同的理论保证，解决了先前基于随机行走算法的图谱划分局部算法存在的问题。

    Jul, 2013

  • 一种超出最坏情况的图聚类的近线性时间逼近算法

    在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。

    Jun, 2024

  • 图分割、图稀疏化和解线性系统的近线性时间算法

    这篇论文分为三篇，分别为 arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105。

    Oct, 2003