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

Jul, 2018

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

Connected Components at Scale via Local Contractions

Jakub Łącki, Vahab Mirrokni, Michał Włodarczyk

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

Abstract

As a fundamental tool in hierarchical graph clustering, computing connected components has been a central problem in large-scale data mining. While many known algorithms have been developed for this problem, they are either not scalable in practice or lack strong theoretical guarantees

connected components hierarchical graph clustering distributed algorithm mapreduce scalability

发现论文，激发创造

流处理和 MapReduce 中的最密子图

本文提出了针对流模型的新算法，用于发现图的局部密集组件，该算法在经过 O ((log n)/log (1+epsilon)) 次输入后，可以找到一个子图，其密度保证是最优解的 2 (1+epsilon) 倍。

Jan, 2012

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

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

Apr, 2013

对数直径轮并行图连通性

研究在 MPC 模型下对图连通性问题进行优化，通过图直径参数化时间复杂度，得到了对于直径为 D 的图的时间复杂度为 O (logDloglog (m/n) n)、总内存为 Θ(m) 的连通性算法，并扩展到生成森林、DFS 序列、最小生成森林和瓶颈生成森林等相关图问题，并指出这些问题的类似界限推导可以应用于更快的布尔矩阵乘法算法。

May, 2018

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

本文研究了大规模图的本地算法设计并提出了一种本地聚类算法，该算法可在几乎线性的时间内找到较好的簇，并基于该聚类算法提出了一种划分算法，进而设计了求解对称对角占优矩阵中线性系统的近线性算法，还提出了其他相关结果。

Sep, 2008

并行匹配算法的圆形压缩

该篇论文探讨了在大规模计算框架中对于最大匹配问题的解决方法，最终在机器拥有稍微低于线性内存的条件下，实现了近乎指数级的算法复杂度优化。

Jul, 2017

通过随机 $2$-Out 缩减加速边连通性算法

使用基于 2 出边采样的简单新的随机收缩方法解决全局最小割问题，进而获得更好的边连通性、分布式算法和并行计算等方面的表现。

Sep, 2019

分布式图聚类与稀疏化

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