麻省理工420页博士论文《现代机器的可扩展和高效的图算法和分析技术》

快速增长的现实世界网络，拥有数十亿个顶点，需要可扩展的、快速的和高效的图算法。幸运的是，商业化的多核、多处理器和多机环境可以处理如此大量的数据。不幸的是，尽管有这样的资源，许多目前的图算法并没有充分利用这些并行和分布式环境，或者有非最佳的理论保证，在实践中转化为更慢和更不有效的算法。本论文的目的是在理论上改进现代机器中以前的图算法。我们通过实验证明，这种理论上的改进也会转化为实际的收益。

为了实现这一目标，本论文采取了双管齐下的方法。首先，我们在模仿大规模数据处理环境的计算模型中制定算法。这种模型中的算法利用了机器集群和一个机器的多个核和处理器的优势。第二，我们在设计算法时使用了现实世界网络的特殊属性。退化就是这样一个特性；虽然一个网络可能有数十亿个顶点，但其退化可能只有几百个。

本论文由三部分组成。

第一部分介绍了静态图算法。我们首先介绍了一套新的编辑算法，该框架通过将图编辑成所需的结构化类别，针对难以解决的优化问题来逼近其解决方案。然后，我们提出了新的小子图计数算法，在大规模并行计算模型中具有更好的理论空间和回合保证；我们的实验证实了我们的理论成果，并显示在现实世界的图中，与以前的最先进的算法相比，回合数和近似系数都有所改善。在这一部分的最后，我们提出了一个近乎线性的时间调度算法，用于在具有通信延迟的相同机器上进行调度，其中优先权受限的工作被建模为有向无环图。

第二部分主要讨论动态图算法。我们首先展示了一个𝑂(1)的摊销时间，高概率的(∆+1)-顶点着色的动态算法。然后，我们为批量动态更新下的𝑘核分解问题提供了一个新的并行级数据结构（其中动态边缘更新是分批进行的）。我们表明，我们的数据结构可以证明对每个顶点的核心性提供了(2+𝜀)的近似值，改进了以前已知的(4+𝜀)的最佳约束。最后，我们提出了新的三角形和团计数的并行、高效批处理动态算法。我们对批处理动态算法的广泛实验，结果表明，在现实世界的网络中，我们的性能比以前最好的多核算法实现了数量级的提高。

最后一部分是关于下限的结论。我们通过硬实例展示了在外部存储器模型中，在有向无环计算图上获得最优计算时间表的困难性。然后，我们证明这种图可以用来构建静态-内存-硬哈希函数，使用磁盘内存来阻止大规模密码破解攻击。