论文阅读：Streaming Graph Partitionin

论文阅读：Streaming Graph Partitioning: An Experimental Study

论文标题：Streaming Graph Partitioning: An Experimental Study
发表：PVLDB, 11(11): 1590-1603, 2018
作者：Zainab Abbas、Vasiliki Kalavri、Paris Carbone、Vladimir Vlassov

原文连接
作者详细介绍：

Zainab Abbas

姓名：Zainab Abbas
院校：皇家理工学院（瑞典）的研究生

Vasiliki Kalavri

姓名：Vasiliki Kalavri
院校：皇家理工学院（瑞典）的博士
研究方向：分布式数据处理和大规模图形分析

Paris Carbone

姓名：Paris Carbone
院校：皇家理工学院（瑞典）的博士
研究方向：分布式系统、数据管理

Vladimir Vlassov

姓名：Vladimir Vlassov
院校：皇家理工学院（瑞典）的教授
研究方向：数据密集型计算和流处理; 云资源管理; 基于云的服务和应用程序

1.前言
现实世界数据量十分巨大，而这些数据大多都是用图来表示的（如下图所示），所以处理图的数据，对现实世界是至关重要的。而在计算中，图的分布式计算是重要的，分布式计算，必然带来图的分区。

社交信息 神经信息

在进行分区之前，我们来看看完整的处理图数据的过程

图数据处理流程

大致上分为三步， 首先将图数据加载，然年后进行分区，最后是计算过程。在分区之前，通用图分区方法扫描完整图以获得结构特征。 然而，对低延迟，连续图形分析的新兴需求导致了在线分区方法的发展。 在线方法将边或顶点作为流摄取，而不是提前完整的加载。

在图处理过程中一般的图分区方法

一般的图分区方法

分为两种，也就是Edge-cut和Vertex-cut，Edge-cut的意思就是切边，对结点进行分区，让边跨越各个分区，这种方法不需要构造其他结点。Vertex-cut就是切结点，对边进行分区，会判断每条边应属于哪一个区，显然不同的边有可能连接着同一个结点，并且这些边也分在不同的区，所以结点要进行复制，跟着边走，边在哪里，结点就在哪里。如图所示，复制了z结点，以及d结点。

流图分区
所以对于这篇论文所讲的流图分区来说，主要也是这两种方法。
流图分区中的流，分为两种，一种是边流，一种是结点流。边流就是不断有边数据流入，然后对其判断边属于哪个分区。结点流就是以结点的形式流入。

流图分区

2.Streaming Graph Partitioning
本文所讲的流图分区，大致分为三类

1. Vertex Partitioning Methods（结点流，对结点进行分区）
2. Edge Partitioning Methods （边流，对边进行分区）
3. Model-Agnostic (其他方法，混合各种方法使用)

• Vertex Partitioning Methods(按结点的分区方法)
  按结点分区的大致过程如下图所示，左边表示原始图形，共有6个结点（0，1，2，3，4，5），上面的表格表示图的输入顺序，（0：1）表示输入的是0号节点，同时记录和它相邻的结点1号。这里输入的顺序是随机的。结点的分区共有三个，分区数量是提前确定的。最后生成右下角的分区图形。
  Vertex Partitioning Methods

这个分区方法所使用的原理就是Linear Deterministic Greedy (LDG)

线性确定性贪婪分区（LDG）尝试将相邻顶点放置到同一分区，以减少边缘切割。在满足容量约束的同时，将一个顶点分配给包含大多数邻居的分区。

如下图所示，在某个分区中存在1号和4号结点，我们现在要判断2号节点所在分区，根据LDG我们会选择2号结点邻居最多的分区，所以最后会将1，2，4三个结点放在同一个分区。

Linear Deterministic Greedy (LDG)

不过这样会存在问题，就是所有的结点可能都会在同一个区里。（比如说放置了第一个结点，第二个是它的邻居会放在一起，之后也是如此）

聚集到一个分区

为了解决这个问题，我们会给每个分区里的结点数量进行限制，其中C就是最大的容量，根据结点个数以及分区的个数计算出来。所以这种方法需要知道图的全局信息，比如结点数量。

容量的限制

• Edge Partitioning Methods(按边的分区方法)
  这种方法就是判断每条边，应该属于哪一个分区里面，过程如下图。
  上面的表格就是输入流，（3，2）表示从结点3指向结点2的边。按照箭头顺序输入，这里是随机输入。黄色结点是复制的结点。
  Edge Partitioning Methods

显然对于按边分区的方法来说，复制结点越多，就代表着这种分区是不好的，所以我们在进行按边分区的时候，应该尽可能的减少结点的复制，于是解决的办法就是首先复制那些度高的结点，比如说图中红色的结点，这样能减少总体的复制次数。

HDRF

那具体的过程是怎样的呢？首先我们输入边，并且边上的结点都不属于任何分区，如图所示，这里有三个分区，用三种颜射表示。在这种情况下，我们会将这条边放在负载最低的分区里，也就是边最少的分区里。

结点不属于任何分区
如果输入的边其中一个结点属于某个分区，另一个不属于任何分区的话，就将这条边放置在结点属于的那个分区里面，也就是下图中蓝色的区。
其中一个结点属于某个区

两个结点，其中一个属于多个分区，另一个也属于某个分区，并且有交集，那这条边就会放在有交集的区里，也就是下图橙色的区。

结点所在区有交集
如果这两个存在属于不同的分区，却没有交集，根据HDRF也就是先复制度高的，所以我们会复制下图中左边的结点。
结点所在区无交集
结果如下
根据HDRF分区结果

• Model-Agnostic (其他方法，混合各种方法使用)
  其他方法里面也有许多种，这里介绍一下哈希的方法。
  基于哈希的混合划分
  对于低度数的点，我们会对本身结点进行哈希，比如这里的4号结点，我们会对4进行哈希运算，然后将4号结点，以及所有的入边都分配到这个块中。 对于高度数的顶点，我们会对源节点进行哈希，比如这里的1号结点，我们会对2号和5号结点进行哈希，然后按照2号和5号的结果，分配到块中。 这种方法需要知道图的全局信息，还要知道机器数，比如这里的机器数是三，那么求哈希值的时候，就是除以3求余数。 这种方法是边分区和结点分区一起使用的，混合方法。
  高度顶点和低度顶点的区别是用给定的阈值来区分的，并且首先要确定好分区数量。
  3.Experiment
  这个实验中，我们设置的分区数是4
  分区性能就是指每秒钟的吞吐量，意思就是指每秒钟把多少结点或者边，分配到某一个区里面去。
  我们的结果表明Hash分区在吞吐量方面优于所有其他评估方法。 然而，性能的差异并不显着。 在这两个实验中，Hash显示的吞吐量最多比第二个最佳分区方法高2倍，并且随着图的增大，这个差异也在减小。
  Partitioning Performance

这里将Twitter和Friendster的分区数设置为16，剩下两个较小的分区数设置为4.
A good partitioning method is not only fast but also pro-duces high-quality partitions（不仅要分的快，还要分的好）所以要评判分区的质量。对于按结点的分区来说，我们用edge-cut指标来评判分区的质量，edge-cut越多，说明分区质量就不太高，因为通信成本大大增加了。入就是这个指标对于按边分区的方法来说，我们用结点的复制次数来评判分区的质量，如果复制的次数太多，说明分区的质量不太好。图b就是这个指标。在最后，我们还要考虑负载均衡的问题，也就是分布的较为平均的意思，不能所有的结点或者边，都在一个区里面。哈希的负载均衡是最好的，因为是完全随机的分配的。

Partitioning Quality

算法的性能也和输入的结点或者边的顺序有关，比如这里是使用随机输入，或者DFS输入，都对算法性能有着很大的影响。

Sensitivity to Order