大数据导论 第十一章
CONTENTS
目录
PART 01 分布式图计算 PART 02 Spark Graphx简介 PART 03 Graphx实现 PART 04 Graphx实例
PART 05 Spark Graphx的优势 PART 06 作业
PART 01 分布式图计算
分布式图计算
数据并行与图并行计算 1.数据并行系统，像 MapReduce和Spark等计算 框架，主要用于对数据集进行 各种运算，在数据内部之间关 联度不高的计算场景下能够进 行很高效的处理。 2.图并行计算对存在较高关联 度的数据处理非常合适
指定不同的划分策略
Spark GraphX简介
GraphX的设计要点
Property Graph
3
rxin stu.
Advisor
5
franklin, prof.
Colleague Collab.
PART 02 Spark GraphX简介
Spark GraphX是一个分布式图处理框架， 它是基于Spark平台提供对图计算和图挖掘 简洁易用的而丰富的接口，极大的方便了对 分布式图处理的需求
Spark GraphX简介
GraphX的应用背景
在社交网络中人与人之间存在
有很多关系链，例如微博、微 信、QQ、Twitter、Facebook、
Table View
GraphX Unified Representation
Graph View
Spark GraphX简介
GraphX的框架
算法
PageRank
SVDPlusPlus
TriangleCount
ConnectedCom ponents
操作
GraphOps
Pregel Graph
GraphImpl
Pregel框架以顶点为中心，对边进行切割，将图数据分成若干个分区，
每一个分区包含一组顶点以及由这组顶点为源顶点构成的边，并不断在
顶点上进行算法迭代和数据同步
B P2 A
A 连接B P1
C 连接D
P1 C
D P3
B 连接C
P2
D 连接B
P3
分布式图计算
Pregel计算过程
读取输入数据，初始化图数据，
GAS模型是以节点为中心的图计算编程模型，某个顶点可能被部署到多台
机器上，其中一台机器上的为主顶点（Master），其余机器上的为镜像
顶点（Mirror），与主顶点的数据保持同步，将边唯一部署在某一台机器
上
B
A
B
P1
A
C
P1
P2
D
B P2
C P3
D
C
D P3
分布式图计算
GAS模型计算阶段划分 ➢ 收集阶段：工作顶点的边，可以是出边或入边，也可以同时包含入边
实现 PartitionStrategy
VertexRDD
MessageToPartition VertexPartition
EdgeRDD Edge
EdgePartition
RDD{EdgeTripl et}
EdgeTriplet
RoutingTablePartit ReplicatedVertexVi
就是一个分布式的图处理系统。
Hyperlinks
PageRank
Top 20 Page Title PR.
Top Communities
Com. PR.
Editor Graph
Community Detection
User Community
User Com.
Spark GraphX简介
GraphX的框架 GraphX的核心抽象是Resilient Distributed Property Graph，一种点 和边都带属性的有向多重图。它扩展了Spark RDD的抽象，具有Table 和Graph两种视图，而只需要一份物理存储
分布式图计算
图存储模式 1.边分割：每个顶点都存储一次，但有的边会被打断分到两台机器上。 2.点分割：每条边只存储一次，都只会出现在一台机器上。邻居多的点 会被复制到多台机器上
A
B2
A
B
A
1
1
C
C
ห้องสมุดไป่ตู้D3
C
D
C
B2 D3
A
1
B
C
D
3
A
B
C
B
C
D
（a）Edge-Cut
（b）Vertex-Cut
分布式图计算
A 3
在图数据上运行一系列的超步
运算直至整个计算结束，输出
结果。当一个节点结束计算之
6
后，该节点停止运行，如果有
新任务分配，则又重新开始运
6
行，然后再次停止。当所有节
点全部停止运行，并且没有新
任务分配的时候，整个算法停
6
止
B
C
6
2
6
2
6
6
6
6
D
1
超步0
6
超步1
6
超步2
6
超步3
分布式图计算
GAS模型：邻居更新模型
图计算模式
1.图计算框架基本上都遵循BSP（Bulk Synchronous Parallell）计算模式。
2.在BSP中，一次计算过程由一系列全局超步组成
3.超步分为三个阶段：
处理 器
➢ 本地执行阶段 ➢ 全局通信阶段
局部 计算
➢ 栅栏同步阶段
通讯
栅栏 同步
分布式图计算
Pregel模型：像顶点一样思考
Link Table Title Link
Linkedin等，这些都是大数据
产生的地方，都需要图计算。
Raw Wikipedia
因为图的结构复杂、数据量大， </>
只有分布式的图处理才能胜任。 XML
Editor Table
Editor Title
由 于 Spark GraphX 底 层 是 基
于 Spark 来 处 理 的 ， 所 以 天 然
ion
ew
Spark GraphX简介
GraphX的设计要点 ➢ 1.对GraphX视图的所有操作，最终都会转换成其关联的Table视图的
RDD操作来完成 ➢ 2.两种视图底层共用的物理数据，由RDD[VertexPartition]和
RDD[EdgePartition]这两个RDD组成 ➢ 3.图的分布式存储采用点分割模式，而且使用partitionBy方法，由用户
和出边，从邻接顶点和自身收集数据，并对收集的数据使用用户定义 的函数进行运算。这一阶段对顶点和边都是只读的。 ➢ 执行阶段：镜像顶点将收集阶段的计算结果发送给主顶点，主顶点对 从各个镜像顶点收集的数据进行聚集运算，并利用聚集结果和上一步 的顶点数据，按照用户定义的更新函数进行计算，更新主顶点的数据， 并同步给镜像顶点。在执行阶段中，工作顶点可修改，边不可修改。 ➢ 分发阶段：工作顶点更新完成之后，更新边上的数据，通知对其有依 赖的邻接边更新状态。在分发阶段，工作顶点只读，边上数据可写。