3小时入门Spark之Graphx

由于事物之间普遍联系的哲学原理，网络结构无处不在。例如，微信用户之间的好友关系形成社群网络，科学论文间的相互引用关系形成文献网络，城市之间的道路连接形成交通网络 …… 可以说，万事万物都处在一个复杂网络当中。马克思·韦伯也说：人是悬挂在自己编织的意义之网上的动物。网太重要了，所以我们每次到一个新的地方，我们都会问：老板，有网吗？wifi密码是什么？

扯远了，总之，事物之间的普遍联系导致了网络的无处不在。而图是表达这种网络关系最直观最普适的数据结构。利用图，你可以研究网络中各个节点的重要程度，找到网络中的两个节点间的最短路径，以及发现网络的聚类结构。如果网络较大，单机跑不动，那么你需要Spark Graphx 来帮助你在集群上分布式实现图算法。

总之，图提供了研究事物间关系非常重要的工具，而Spark Graphx 可以帮助你实现大规模并行图算法。

一，图的基本概念

图(graph)有时候又被称为网络(network), 是一种适合表现事物之间关联关系的数据结构。

1，图的组成

图的基本组成是顶点(vertex)和边(edge).

2，图的分类

有向图和无向图：根据边是否有方向，图可以分成为有向图和无向图。有向图的边从源顶点出发，指向目标顶点。在无向图中，一个顶点上的边的数量叫做这个顶点的度。在有向图中，一个顶点上出发的边的数量叫做这个顶点的出度，汇集到一个顶点上的边的数量叫做这个顶点的入度。

有环图和无环图：如果有向图中存在一些边构成闭合的环，称为有环图，反之为无环图。有环图上设计算法需要考虑终止条件，否则算法可能会沿着环永远循环下去。

多重图和伪图：如果两个顶点之间可以有多条平行边，称为多重图。如果存在自环，即由一个顶点指向自己的边，则称为伪图。Graphx的图都是伪图。

属性图和非属性图：如果顶点和边是包括属性的，称为属性图，否则是非属性图。非属性图作用不大。通常顶点和边至少有一个是包括属性的，Graphx的图都是属性图。

二分图：如果图的顶点被分成两个不同的子集，边的源顶点始终来自其中一个子集，目标顶点始终来自另外一个子集。这种图称为二分图。二分图可用于交友网站，源顶点来自男性集合，目标顶点来自女性集合。二分图也可以用于推荐系统，源顶点来自用户，目标顶点来自商品。

3，图的表示

如果图的边是没有属性的，可以用稀疏的邻接矩阵进行表示。

在Graphx中，用顶点属性表VertexRDD和边属性表EdgeRDD联合来表示图。

4，图的算法

图的著名算法包括：用于衡量顶点重要性的PageRank算法，用于计算顶点之间距离的最短路径算法，用于社区发现的标签传播算法，用于路径规划的最小生成树算法……

5，图的应用

图的应用主要包括网站排名，社交网络分析，金融欺诈检测，推荐系统等等。

二，图的创建

有3类常用的创建图的方法。

第一种是通过Graph的构造函数进行创建。

第二种是通过GraphLoader.edgeListFile从文件读入EdgeRDD进行创建。

第三种是使用util.GraphGenerators生成一些简单的图用于测试算法。

1，通过Graph构造函数创建

Graph类有3个不同的构造函数，它们的签名如下，用法也是一目了然。

2，从文件读入EdgeRDD进行创建

data/paperCite.edges是一些论文之间的引用关系，其格式如下所示。

#FromNodeId ToNodeId 1 2 1 3 1 4 1 5 2 6 2 7

3，使用util.GraphGenerators生成测试用图

三，图的可视化

可以使用Python中的Networkx库，或者Gephi开源软件对图进行可视化，此外使用Zepplin也可以对Graphx的图进行可视化。

此处我们演示通过调用Networkx库中对Graphx图的可视化。

plot_graph.py 文件中的代码如下。

四，Graph的常用方法

Graph的各种接口方法的签名如下所示，大概有9组30多个方法。

其中pregel迭代接口和aggregateMessages合并消息接口是较为重要而灵活的方法。

使用pregel和aggregateMessages方法的精妙之处在于只需要考虑每个顶点的更新函数即可，让框架在遍历顶点时进行调用，而无需考虑并行分布计算的细节。

这种图计算编程模式叫做"像顶点一样思考"(Think Like A Vertex)。

1，图的信息

degrees既包括inDegrees和outDegrees之和。

2，图的视图

edges和vertices必须包括属性，如果没有，一般给每个顶点和边填充一个1作为属性。

可以从triplets中同时获取边的属性，以及与之关联的顶点属性。

3，图的缓存和分区

如果图要多次被使用，应当使用persist缓存进行。如果确认图不再用到，推荐使用unpersist清理缓存以减轻内存压力。

如果设计迭代算法，推荐使用pregel迭代接口，它能够正确地释放不再使用的中间计算结果。

graphx对图的默认分区策略是切割Vertex而非切割Edge，这种设计更有利于减少存储和分区间的通信压力。

在切割Vertex策略下，可以保证不同的分区是不同的边，但是有些Vertex可能会在多个分区存在。

graphx提供了4种按照Vertex进行切割的具体策略。

• RandomVertexCut：以边的srcId和dstId来作Hash，这样两个顶点之间相同方向的边会分配到同一个分区。
• CanonicalRandomVertexCut：对srcId和dstId的排序结果来作Hash，这样两个顶点之间所有的边都会分配到同一个分区，而不管方向如何。
• EdgePartition1D：对srcId来作Hash, 同一个vertex出来的edge会被切到同一个分区, supernode问题得不到任何缓解, 仅仅适用于比较稀疏的图.
• EdgePartition2D：把整个图看成一个稀疏的矩阵, 然后对这个矩阵的行和列进行切分，从而保证顶点的备份数不大于2*sqrt(numParts)的限制。

4，修改属性创建新图

这几个方法的使用相对简单，都是进行一次map操作后生成新的VertexRDD或EdgeRDD替换掉已有Graph的对应部分，得到新的Graph。

我们首先构造如下一个社交关系图，然后利用mapTriplets给边添加属性值。

如果边属性为"is_friends_with"，并且其源顶点属性中包含字母"a"，则添加属性值 true,否则添加属性值false。

5，修改图结构创建新图

这4个方法的作用简单总结如下：

reverse最简单，将每条边的方向反向。

subgraph过滤一些符合条件的边和顶点构造子图。

mask返回和另外一个graph的公共子图。

groupEdges可以对平行边进行merge，但要求平行边位于相同的分区。

6，连接其它RDD

7，收集邻居消息

aggregateMessages在图结构中实现了一个基本的map/reduce编程模型。

sendMsg是map过程，每条边向其src或dst发送一个消息。其输入参数为EdgeContext类型。EdgeContext类型比Triplet类型多了sendToSrc和sendToDst两个方法，用于发送消息。

mergeMsg是reduce过程，每个顶点收集其收到的消息，并做合并处理。

aggregateMessages的返回值是一个VetexRDD。

大部分算法中都包括多轮迭代，我们可以通过构建循环反复调用aggregateMessages方法进行实现。

我们考虑使用迭代算法计算每个顶点和离它最远的源顶点的距离。假设图是无环图。

算法基本过程如下：

1，给每个顶点赋初始属性值0。

2，每条边向其目标顶点发送消息，消息值为该边源顶点的属性值+1。

3，每个顶点收集所有消息，取消息中的最大值。

4，重复执行第2，3步骤，直到图中每个顶点的属性值都不再发生改变。

8，pregel迭代接口

上述使用aggregateMessages进行迭代的方法尽管已经非常简短了，但是其迭代过程中中间结果的缓存问题可能会给程序的性能造成影响。

使用pregel迭代接口能够很好地进行缓存优化。

pregel迭代接口基于Graphx的基础API实现，实现方式相当简洁，其代码不过20多行。

它主要使用了mapVertices，GraphXUtils.mapReduceTriplets，以及joinVertices这3个基础API进行实现。

其中mapReduceTriplets和aggregateMessages作用非常相似，都是一个map/reduce操作，

主要差异是其参数方法sendMsg的输入输出类型不太一样。

pregel迭代接口有2个参数列表。

第一个参数列表完成了一些配置工作，三个参数分别是initialMsg、maxIter和activeDirection。

分别设置了初始消息，最大迭代次数和边激活的条件。

第二个参数列表有三个函数参数：vprog、sendMsg和mergeMsg.

vprog是顶点更新函数，它在每轮迭代的最后一步用mergeMsg的结果更新顶点属性，并在初始化时用initialMsg初始化图。

sengMsg是消息发送函数。其输入参数类型为EdgeTriplet，输出参数类型为一个Iterator，与aggregateMessages中的sengMsg有所不同。

需要注意的是，为了让算法结束迭代，需要在合适的时候让其返回一个空的Iterator

mergeMsg是消息合并函数。与aggregateMessages中的mergeMsg一样。

pregel在迭代的每一步都会生成一个新的图，直到没有新的消息产生或达到最大迭代次数退出。

重点讲解一下activeDirection，它是边的活跃状态的控制参数。在一轮迭代后，所有收到消息的顶点都是活跃的顶点。活跃顶点将状态传递给边的方式由activeDirection控制，activeDirection有4个候选取值。

• EdgeDirection.Out: 只有边的srcId的顶点在上一轮收到了消息，这条边才允许发送消息。即顶点活跃状态传递给它的出边。
• EdgeDirection.In: 只有边的dstId的顶点在上一轮收到了消息，这条边才允许发送消息。即顶点活跃状态传递给它的入边。
• EdgeDirection.Both: 只有边的srcId和desId两个顶点在上一轮都收到了消息，这条边才允许发送消息。即只有两个顶点都活跃，边才活跃。
• EdgeDirection.Either: 只要边的srcId或desId顶点在上一轮收到了消息，这条边就可以发送消息。即顶点活跃状态传递给它的入边和出边。这是默认值。

下面我们基于pregel接口来重新实现：计算每个顶点和离它最远的源顶点的距离。

五，VertexRDD和EdgeRDD类的补充方法

除了Graph类定义的这些方法，VertexRDD类和EdgeRDD类在继承了RDD类的方法的基础上，还有一些补充方法。

1，VertexRDD类的补充方法

2，EdgeRDD类的补充方法

六，Graphx内置常用图算法

Graphx内置的图算法一些作为GraphOps类的方法存在，另外一些在graphx.lib中。

Graph类和GraphOps类的关系就像RDD和PairRDD的关系，必要时候Graph对象可以通过隐式转换变成GraphOps对象。

这些内置图算法主要包括：

• PageRank: 可以由PageRank值衡量节点的重要程度，常用于网页排名，社区关键人物分析。
• personalizedPageRank: 个性化的PageRank值，可用于社交网站中推荐"你可能认识的人"。
• triangleCount: 三角形个数，可以衡量周围的节点的连通性，也可以用于衡量网络总体的联通性。
• ShortestPaths: 最小跳跃数，可以找到图中全部顶点和给定顶点的最小跳跃数。
• connectedComponents: 联通组件，可以在社交网络中找到社交圈子。
• stronglyConnectedComponents: 增强联通组件，针对有向图，可以找到社交圈子
• LabelPropagation: 标签传播算法，可以用于社区发现。但往往不收敛，不是特别推荐使用。

1，PageRank

PageRank网页排名算法由谷歌创始人拉里·佩奇和谢尔盖·布林在1998年提出。可用于搜索引擎页面排名，或者在论文引用关系网中找到最有影响力的论文。总之，它可以衡量一个顶点在一个网络中的"重要性"程度。

PageRank的基本思想是被其它网页通过超链接引用越多的网页就越重要，并且被越重要网页引用的网页也越重要。

PageRank值相当于在inDegrees的基础上，增加了引用来源网页的重要性作为权重因子。

PageRank值通过迭代方法进行计算，其物理含义可以用这样一个思想实验来说明。

假定有许许多多的用户在各个网页之间随机地通过超链接进行跳转，那么当达到动态均衡时，停留在某网页的用户数量占全部用户的比例就可以衡量为该网页的PageRank值。实际中的PageRank值还会做一些线性缩放。

PageRank的迭代公式如下：

其中resetProb 为重置概率，即用户不通过超链接，而是直接访问某个页面的概率，默认值为0.15。

重置概率可以防止某些只有出边没有入边的PageRank值衰减到零。

求和项为将所有有超链接指向i的网页的PageRank值根据这项网页的出度均分后转移到i。

在经过许多轮迭代后，各个网页的PageRank值基本稳定不变时，算法即宣告收敛。

2，personalizedPageRank

个性化PageRank是 PageRank的一个变种，可以用于在社交网站中给用户推荐"你可能认识的人"。

personalizedPageRank除了要设定一个迭代终止的条件，还要指定一个源顶点的srcId.

在PageRank原理中，有一个重置概率，即用户不通过超链接直接进入某个页面。

而在个性化的PageRank中，除了指定源顶点的重置概率不为零，其余顶点的重置概率都为0.

3，triangleCount

三角形数量可以衡量顶点周围网络连通性。graphx在计算三角形数量时，会忽略边的方向。

微信朋友圈的互动规则就是基于三角形关系的。如果A和B是好友，A和C也是好友，B和C却不是好友，那么如果A发了一个状态，B点了一个赞，C能看到A的状态，却看不到B的点赞。只有A和B是好友，A和C是好友，并且B和C也是好友，三个人构成了三角形关系的前提下，B和C才能在A的状态下看到彼此的点赞。

4，ShortestPaths

ShortestPaths虽然命名上是最短路径，但其实际含义是计算各个顶点到给定顶点的最小跳跃数。

5，connectedComponents

connectedComponents连通组件会将图划分成几个连通区域，每个顶点的属性值为其所在连通区域中顶点编号的最小值。

connectedComponents的一种巧妙用法是用来在spark上实现DBSCAN算法，可以用它来对临时聚类簇进行合并。

连通组件不关心边的方向。

6，stronglyConnectedComponents

stronglyConnectedComponents强连通组件和连通组件作用类似，但是它还关心边的方向。

在强连通组件中，每个顶点都可以通过其它顶点到达。

强连通组件由于边有方向，为了避免环的存在，需要设置最大迭代次数。

7，LabelPropagation

为了识别出图中紧密交织的群体，GraphX 提供了标签传播算法(LPA).

这个想法是让稠密连接的顶点组在一个唯一的标签上达成一致，所以这些顶点组被定义为一个社区。

不幸的是，LPA常常不是收敛的，所以需要指定一个最大迭代次数。

七，其它常用图算法

Graphx内置的一些图算法基本上是用pregel迭代API实现的。

还有一些非常经典的图算法不太适合使用pregel迭代API实现，因此它们在Graphx中没有对应的内置实现。这些算法本质上也是迭代算法，例如每次迭代添加一条边。本节我们将主要使用诸如mapVertices和函数outerJoinVertices函数来实现和并行化这些原本被设计为顺序执行的算法。

这些算法包括：

最短路径算法(Dijkstra)：找到图中各个顶点到给定顶点的最短路径。

旅行推销员问题(TSP)：在图中找到一条访问每个顶点一次并回到出发点的最短路径。

最小生成树算法(Kruskal)：在一个图中 ，找到一个生成树，其边权值之和小于任何其他生成树边权值之和。

1，最短路径算法(Dijkstra)

Dijkstra算法实际上是一种广度优先搜索算法，可以用pregel迭代API进行实现。

2，旅行推销员问题(TSP)

旅行推销员问题(TSP)是在一个无向图中找到一个经过每一个顶点的最短路径。假如有一个推销员，他要到某一地区的所有城市去推销，他想要走过的总路程最少。

旅行推销员问题是一个NP-Hard问题，没有一个有效的算法在多项式时间复杂度内得到确定的解。我们可以使用如下贪心算法得到近似解。

TSP问题的贪心算法：

• 1，从某些点开始
• 2，添加权重最小的邻边到路径中。
• 3，以该边的终点为新的起点，跳到第2步。

对于旅行推销员问题来说，贪心算法是最简单的，缺点是不会总是到达所有顶点。在这 个例子中，顶点 G 就没有到达。

贪心算法可在不用增加太多代码的情况下，用不同的起始顶点重新运行整个算法，不断迭代，挑选出一个到达所有顶点并且最短的解决方案。

3，最小生成树算法(Kruskal)

最小生成树问题是为了寻找包含图的每一个顶点的总边长度最小的子图。

由于这样的子图包括了原始图中的每一个顶点，并且其边之和是最短的，所以可以叫做最小生成子图。

这样总边之和最短的图必定不会形成环，否则的话，去掉环中的一段，新得到的子图依然包括了图中的每一个顶点，但其边之和却可以变短。

所以最小生成子图实际上是一个树结构，一般称之为最小生成树。

解决最小生成树问题的解法是Kruskal算法，这是一种贪心算法。

但是和TSP算法不同，可以从数学上用反证法证明Kruskal算法的解一定是最优的。

最小生成树的最直接应用是在路径规划工具方面(道路、电力、水等)，用来确保这些基础设施资源能在最小消耗的前提下到达所有城市(例如最短距离，路径图的边权值表示城市间的距离)。也有一些不太显著的应用，如在相似事物的集合上做分类，例如动物 (用于科学分类)或 报纸头条。

解决最小生成树的Kruskal算法可以表述如下：

• 1，初始化集合中的边，构建一个空的最小生成树。
• 2，找到图中最短的边，将其添加到结果集合中。其对应的两个顶点设置成已访问顶点。
• 3，找到连接已访问顶点和未访问顶点中的边的最短的那条，将其添加到结果集合中。对应的未访问顶点设置成已访问顶点。
• 4， 重复步骤3，直到所有顶点都已经被访问。

八，图和机器学习

大部分机器学习算法使用矩阵或者张量作为其数据结构，但也有一些算法使用图作为其数据结构，此外还有相当一部分算法的实现中用到了图。

一些常用的和图相关的机器学习算法简单介绍如下。

1，监督学习

SVDPLUSPLUS算法：这是一个商品推荐算法，使用EdgeRDD作为输入，可以通过graphx.lib.SVDPLUSPLUS进行调用。

2，非监督学习

LDA文本主题算法：LDA文本主题模型可以将文本映射为主题向量，从而对文档进行聚类。它属于mllib库，但其最大期望算法EM的实现可以用图来进行加速。

PIC聚类算法：幂迭代聚类算法可以用于图像分割。它可以通过mllib.clustering.PoweriterationClustering进行调用。

3，半监督学习

基于K近邻图的标签传播算法：可以利用图结构，将少量顶点的标签传递到其近邻的未知标签顶点上（可以按照边的权重倒数作概率加权)。得到较多的含有标签的顶点后，再利用K邻近的方式对未知顶点的标签进行预测。