Nov, 2022

可扩展和有效的基于传导度的图聚类

PDF
TL;DR本文提出了一个基于 peeling 的图聚类框架 PCon ，并使用该框架提出了两个线性时间和空间复杂度的算法 PCon_core 和 PCon_de ，可以在处理十亿级别的图数据时实现高准确度的聚类效果，而且 PCon_de 的近似度理论上提升到了常数级，相较于基线算法可以在速度上提升 5~42 倍且更节省内存。
conductance-based graph clusteringpeeling-based graph clustering frameworklinear time and space complexityapproximation ratioclustering accuracy
发现论文，激发创造
  • 可扩展的基于模式的图聚类

    本研究基于图形图案研究了新的图聚类方法，特别是针对三角形图案的发现，扩展了已有的聚类方法，包括谱聚类，以最小化由聚类划分而不是由边缘切割的三角形数量。研究结果表明，我们的方法在机器学习和图形挖掘中具有良好的现实效果。

    Jun, 2016

  • 超越 Cheeger 不等式的本地图聚类

    本文提出了一种基于随机游走的局部聚类算法，通过将内部连接性参数考虑入内，改进了先前结果，得到更优秀的聚类精度和 conductance，并探讨了其与全局谱算法之间的联系。

    Apr, 2013

  • 通过图导电性理解正则化谱聚类

    通过研究图导纳与谱聚类之间的关系，本文探讨了谱聚类的缺陷和正则化带来的好处。结果表明，正则化可以修正谱聚类在稀疏随机图中的过度拟合问题，提高计算速度。

    Jun, 2018

  • 测试图的聚类能力：算法和下限

    本文提出了一种利用角度信息和奇异值分解的子线性时间图聚类算法，并在其基础上给出了测试聚类可行性的查询复杂度下界，并且通过这些技术，也实现了新的子线性时间下界近似最大割价值的问题。

    Aug, 2018

  • 改进预处理时间的次线性时间谱聚类预测模型

    我们设计了一个次线性时间的谱聚类预处理方法来解决在具有强聚类性的图中的问题。我们的算法通过在次线性时间内进行预处理和查询回答，得到与实际聚类接近的 $k$-partition。我们的实验证明了我们的理论性能。

    Oct, 2023

  • 局部收缩算法实现大规模连通性分量

    该研究设计了一个分布式算法用于计算连接组件问题，并在 MapReduce 中提供了可扩展的实现。该算法在所有图形上显示 O (log n) 收敛，并对某些随机图形类具有高概率 O (log log n) 并行运行时间。在实践方面，该算法优于现有的 MapReduce 算法，并且在拥有数万亿边缘的图形上具有可扩展性。

    Jul, 2018

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

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

    Jul, 2013

  • 利用有效电阻进行图聚类

    设计了一种多项式时间算法，可将任何加权无向图划分为子集并使子图的有效电阻直径不超过平均加权度的倒数，证明了有效阻抗与低电导集之间的新联系，并提出该联系可能对算法设计独立地产生兴趣。

    Nov, 2017

  • 克服图聚类中的小簇障碍

    在图聚类中，小集群不会妨碍大集群的恢复，并且设计了一个迭代算法通过削片策略从而几乎恢复出所有集群，同时也给出了针对较小集群邻近边更有针对性地探测的主动学习算法。

    Feb, 2013

  • 扩张图的划分

    本文介绍了一种使用谱算法的简单多项式时间用于进行图分割的方法，旨在寻找具有网络传导性和诱导子图的低导纳集合，并且提出了一种找到最佳 k 聚类的方法，其中 k 是一个整数，而且这种方法与 Cheeger's inequality 有所不同。

    Sep, 2013