GraphX中已实现的图算法：连通体算法、三角形计数算法

GraphX包括一组图算法来简化分析任务，这些算法包含在org.apache.spark.graphx.lib包中，可以直接访问。下面对GraphX中已经实现的算法进行说明。

1.PageRank

PageRank度量一个图中每个顶点的重要程度，其中假定从u到v的一条边代表v的重要性标签。例如，一个Twitter用户被许多其他人添加关注，则该用户排名很高。GraphX带有静态和动态PageRank的实现方法，这些方法在PageRankobject中。静态的PageRank运行固定次数的迭代，而动态的PageRank一直运行，直到收敛。GraphOps允许直接调用这些算法作为图运算的方法。

GraphX包含一个可以运行PageRank的社交网络数据集的例子，用户集在graphx/data/users.txt中，用户之间的关系在graphx/data/followers.txt中。通过下面的方法计算每个用户的PageRank，如【例4-34】所示。

【例4-34】PageRank算法示例。

2.连通分支

连通体算法用ID标注图中的每个连通体，将连通体中序号最小的顶点的ID作为连通体的ID。例如，在社交网络中连通体可以近似为集群。GraphX在connectedComponents object中包含了一个算法的实现，可以通过下面的方法计算社交网络数据集中的连通体，如【例4-35】所示。

【例4-35】连通体算法示例。

2.连通分支(www.xing528.com)

连通体算法用ID标注图中的每个连通体，将连通体中序号最小的顶点的ID作为连通体的ID。例如，在社交网络中连通体可以近似为集群。GraphX在connectedComponents object中包含了一个算法的实现，可以通过下面的方法计算社交网络数据集中的连通体，如【例4-35】所示。

【例4-35】连通体算法示例。

3.三角计数

一个顶点有两个相邻的顶点以及相邻顶点之间的边时，这个顶点是一个三角形的一部分。GraphX在TriangleCount object中实现了一个三角形计数算法，它计算通过每个顶点的三角形的数量。需要注意的是，在计算社交网络数据集的三角形计数时，TriangleCount需要边的方向是规范的方向（即源顶点ID小于目标顶点ID），并且图通过Graph.partitionBy来分片。

【例4-36】三角形计数算法示例。

3.三角计数

一个顶点有两个相邻的顶点以及相邻顶点之间的边时，这个顶点是一个三角形的一部分。GraphX在TriangleCount object中实现了一个三角形计数算法，它计算通过每个顶点的三角形的数量。需要注意的是，在计算社交网络数据集的三角形计数时，TriangleCount需要边的方向是规范的方向（即源顶点ID小于目标顶点ID），并且图通过Graph.partitionBy来分片。

【例4-36】三角形计数算法示例。