博弈论(研究生课程)期末作业 (3)
https://ieeexplore.ieee.org/abstract/document/8598984
2. 相关工作（RELATED WORK）
2.1. 理解（Comprehension）
在“相关工作”这一部分，作者提到了过去一些图划分策略的研究。图划分在并行和分布式图计算应用中起着关键作用，因为数据布局对于这些应用的性能有显著影响，包括通信成本和工作负载平衡。由于图划分的固有难度，许多启发式划分策略已经被提出。
现有的启发式划分策略大致可以分为离线基础和流式基础两类。METIS是一种广受好评的离线启发式，它结合了许多启发式，比如著名的Kergnighan-Lin启发式。然而，离线基础的启发式需要关于图的全部信息，这对于大规模图和动态图可能是不切实际的。在Powerlyra中提出了一种混合启发式，该启发式将顶点划分和边划分方案结合在一起。这种混合启发式被称为Ginger，在原始划分之后，需要对高度顶点进行额外的重新分配阶段。
在流式设置中首次引入了平衡图划分问题的是Stanton。他提出了几种贪婪策略，这些策略根据负载平衡和每个分割中承载的邻居数量来分配当前顶点。Fennel是另一种顶点划分方案，它结合了两种启发式：将新到达的顶点放在承载最多邻居或承载最少非邻居的分割中。请注意，作者在另一项研究中实现了Fennel的边划分版本。
对于特定的顶点划分问题，提出了一种基于博弈论的解决方案，这与传统的流式图顶点划分在设置和优化目标上都有很大的不同。流式边划分的启发式首次在另一项研究中被提出，其中证明了边划分方案对于幂律图比顶点划分方案更有效。另外两种流式边划分方案，DBH和HDRF利用了自然图的偏度分布特性。关于图划分启发式的调查可以在另一项研究中找到。
这一部分提供了图划分领域的一个背景，让读者了解到过去的研究以及他们的局限性，从而强调了他们提出的新方法的重要性和贡献。
2.2. 翻译（Translation）
图分割在并行和分布式图计算应用中起着关键作用，因为数据布局对这些应用在通信成本和工作负载平衡方面的性能有着显著影响。由于图分割的内在难度[1]，[8]，实践中提出了许多启发式分割策略。最先进的启发式分割策略可以分为离线和流式两种。METIS[20]是一种广受好评的离线启发式方法，它结合了大量的启发式方法，如众所周知的Kergnighan-Lin[12]启发式方法。然而，离线的启发式方法[11]需要对图的全部知识，这对大规模图和动态图可能是不切实际的。Powerlyra[7]提出了一种混合启发式方法，将顶点分割和边分割方案结合在一起。这种混合启发式方法被称为Ginger，在原始分割后，高度顶点需要进行额外的重新分配阶段。
在流设置中首次引入了平衡图分割问题的是Stanton[21]。在他的工作[21]中提出了几种贪婪策略，根据负载平衡和每个分割中承载的邻居数量来将当前顶点分配到分割。Fennel[23]是另一种顶点分割方案，它结合了两种启发式方法：将新到达的顶点放在持有最多邻居或持有最少非邻居的分割中。请注意，作者在他们的工作[5]中实现了Fennel的边分割版本。在他们的工作[2]中提出了一种基于博弈论的特定顶点分割问题的解决方案，这在设置和优化目标方面与传统的流图顶点分割[21]完全不同。
首次提出流式边分割的启发式方法是在工作[9]中，其中已经证明，对于幂律图，基于边分割的方案比基于顶点分割的方案更有效[9]。另外两种流式边分割方案，DBH[24]和HDRF[18]，利用了自然图的偏度分布特性。关于图分割启发式的调查可以在工作[6]中找到。