Spark GraphX 图算法的理解

Spark GraphX是一个分布式图处理框架，基于 Pregel 接口实现了常用的图算法。包括 PageRank、SVDPlusPlus、TriangleCount、 ConnectedComponents、LPA 等算法，以下通过具象化的图实例理解相应的算法用途。

Graphx图结构

Graphx中的Graph有两个RDD，一个是边RDD，一个是点RDD。

此外，三元组其实就是（点、边，点）一个有效组合，由triplets()接口获取，triplets()返回的结果是EdgeTriplet[VD,ED]。

1. 最短路径

最常见的路径搜索算法（例如DFS & BFS、最短路径、 最小生成树、随机游走等），最短路径是最容易理解的图算法，因为大家在生活中能够广泛接触到，如驾驶导航，外卖送餐路线等等。

路径搜索算法建立在图搜索算法的基础上，用来探索节点之间的路径。这些路径从一个节点开始，遍历关系，直到到达目的地，Graphx采用了最短路径算法Dijkstra的原理。

示例数据

// 输入一些边数据
val edgeSeq: Seq[(Int, Int)] = Seq((1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6),(6, 9),(9, 11)).flatMap(e => Seq(e, e.swap))
val edges = op.sc.parallelize(edgeSeq).map { case (v1, v2) => (v1.toLong, v2.toLong) }
1
2
3

可视化数据

这是上述数据的图形表示（双向边，无权）

计算最短路径

val graph_sp = Graph.fromEdgeTuples(edges, 1)
val landmarks = Seq(1, 11).map(_.toLong)
val results = ShortestPaths.run(graph
1
2