基于图数据流的图分割算法研究文献综述

1. 选题背景和意义：

图是一种普遍存在的数据结构。同时在现实世界中,在很多领域,都有着广泛的应用,无论是在生物信息、电力部署等方面,还是在如今蓬勃发展的社交网络上等等。而这些领域中的很多结构都可以抽象为计算机学科数据结构中的图。随着应用需求的日益扩大,图的规模也不多扩大,这就产生了大规模的图。那么如何有效将图分割成不同子图,以减少模块间的信息交互,是一个具有重大意义的工作。同时随着图规模的扩大,单机上的分割算法已经满足不了应用的需求,那么如何在分布式环境下进行有效的分割则成为一个很重要的问题。现有的图分割算法大多都是集中式算法,虽然分割技术已经相对成熟,但是在分布式环境下的分割研究相对薄弱。

图分割对于分布式图处理系统中的大规模图形的高效分析起着关键性作用。图分割的目的是将输入图划分为若干部分，使得分布式进程之间的通信开销最小，同时保持分布式负载平衡。现有的图分割算法往往需要获得完整的静态图，即在算法执行之前将图数据完全导入本地内存。该类算法需要大内存空间，对于处理大规模图数据缺乏适用性。针对此问题，我们考虑在线算法并以“流”的形式处理大规模数据。流式图分割在2012年KDD的一篇文章中给出了定义。有别于传统的图分割，流式图分割一次处理部分图数据，并对于拿到的部分图数据分配到各个节点当中，之后不再迁移已经分配好的数据。所以流式图分割有几个优点：1）可以处理很大的图，理论上只要集群可以容纳，那么就可以处理多大的图。2）一般只加载一次图。3）相比于基于哈希的分配方式，可以有效的保留部分图的性质，进而提升算法性能。

由于图表数据过大且不断增长，许多图相关的应用程序必须利用分布式存储系统，同时面临着分布式环境中的数据管理的挑战。分布图数据库，分布式图模型元数据管理系统是这些应用程序的典型示例。这些应用程序中图形的大小不仅很大，而且随着时间的推移而增长。 因此，有必要考虑图分区算法，将图数据分布到多台机器通过进入分布式系统的数据，换言之，输入图形数据的放置需要立即确定。

作为最难解决的NP难问题题之一，图分区问题已经得到了很好的研究。有许多图划分算法被提出来解决图划分问题。但是，并非所有这些算法都可以应用于动态图，这种图总是随着时间变化。离线图划分算法可以评估整个图形，以实现最小的切边比例和平衡分区大小。但是，由于它们需要加载整个静态图进入内存并进行图分区由于复杂的计算多次迭代有限的内存空间和繁重的计算工作量，这些算法无法在对动态图进行分区的方面取得飞跃性进展。我们的研究旨在解决这样的动态图分区问题。

1. 课题关键问题及难点：

关键问题：

1. 阅读并理解基于图数据流的图分割算法原理
2. 实现适用于该场景下的图分割算法
3. 测试并分析现有算法的不足。

难点：

1. 基于图数据流的图分割算法的实现
2. 尝试对现有算法进行一定的优化

1. 文献综述（或调研报告）：

流式处理相关：

文献[1]介绍了许多与图相关的应用程序都面临着在分布式环境中管理过多且不断增长的图形数据的挑战。因此，有必要考虑图分区算法，现有图分区算法要么无法处理流工作负载，要么切边率有待进一步完善。这篇文章介绍了一种分布式系统中的图分区算法AKIN，这种算法可进一步降低边切率的同时在所有分区之间保持大致平衡。文献[2]介绍了现有的图分区方法在大型图上会导致较高的计算和通信成本，有时甚至会与将来的计算本身一样高。观察到必须将图加载到集群中后，这篇文章提出可以使用轻量级流算法同时完成分区并将其与哈希和METIS进行比较，通过实验证明其运算速度具有巨大进步。文献[5]介绍了流设置中的平衡图分区是一个关键问题，它能够对海量图数据进行可扩展且高效的计算。这篇文章推导了一种新颖的单程流图分区算法，并表明与使用大量实物图和合成图的先前方法相比，它可以显着提高性能。文献[6]介绍了一种新的方法，称为S-PowerGraph，用于通过顶点切割对自然图进行流图形分区。大多数流图形分区方法都采用边切，但很少有人提出针对流图形分区的顶点切方法。但是，切角策略比切边策略是更好的选择，因为自然图的程度通常遵循高度偏斜的幂律分布。文献[8]提出了一种算法来解决不平衡集群（cpu速度内存大小等不同）上的流图分区问题，并通过使用这种方法来解决大型真实世界的World-Wide-Web链接图上的标准PageRank计算，来评估不平衡群集中的性能提升。文献[9]提出了一种有效的基于窗口的流图分割算法，称为WStream。 WStream算法是一种边缘切割分区算法，可在各个分区之间分配顶点。实验的结果表明，WStream算法能够有效地对大型图形数据进行分区，同时在不同分区之间保持负载平衡，并将通信量降至最低。

非流式处理相关：

文献[3]介绍了XtraPuLP，这是一种新的分布式内存图分区程序，基于可扩展的标签传播社区检测技术，该技术已被证明是一种以最少的计算时间来生产高质量分区的可行方法。这篇文章提出并证明了使用XtraPuLP分区进行分布式内存图分析可以显着减少端到端的执行时间。文献[4]介绍了分布式图形处理系统中的分区策略之间进行选择的问题。在各种流行的分布式图处理系统，应用程序，输入图和执行环境下，评估并表征了不同分区策略的性能和资源使用情况。通过实验发现没有一个分区策略最适合所有情况，并且分区策略的选择对资源使用和应用程序运行时间有重大影响。分区策略的选择取决于（1）输入图的程度分布（2）应用程序的类型和持续时间以及（3）集群大小。文献[7]针对边缘分割问题提出了一种准流分割模型和一种基于博弈论的解决方案。将整个边缘流分成一系列批次，其中批次大小是分区数的恒定倍数。在每批中，将图形边缘分区问题建模为一个游戏过程，其中边缘的分区选择被视为游戏中玩家的理性策略选择。结果，边缘划分问题被分解为在一系列游戏过程中找到纳什均衡。我们用数学方法证明了这种博弈过程中纳什均衡的存在，并分析了收敛到纳什均衡所需的回合数。