第7章 Spark GraphX-图计算框架

SparkGraphX

——图计算框架每个人对自己的人生都会有自己的价值定位和人生追求，生命虽然有限，但用生命所创造的价值，却可以与世长存。人生的价值在于劳动、创造与贡献。社会需要我们创造价值，体现的价值越高，人生才会越有意义。对于网页而言，网页也是存在价值的，对网页价值进行分析，可以节省网站建设的时间成本，将更多的精力和资源集中在高价值网页的设计上。PageRank即网页排名，又称网页级别或佩奇排名，是用于标识网页的等级或重要性的一种算法，也是衡量网站好坏的一种标准。通过PageRank算法可以计算网页的价值，使等级更高、更重要的网页在搜索结果中更容易被查找到，从而提高搜索结果的相关性和质量。任务背景现有两份关于某资讯网站的数据，一份为网页信息数据文件news_vertices.csv，包含3个数据字段，数据字段说明如下表。另一份为网页之间的链接关系数据文件news_edges.csv，包含两个数据字段，数据字段说明如下表。两份文件的数据字段均使用“,”（逗号）进行分隔。任务背景字段名称说明示例id自定义的简化的网页ID1network_id网页ID191000000000page_type网页类型，包括4种类型，分别为人才招聘、社区论坛、教育文化和新闻媒体社区论坛字段名称说明示例id_1简化的起始网页ID1id_2简化的连接网页ID2由于网页之间是有链接的，而PageRank是一个通过网页链接计算网页得分以进行网页排名的算法，因此，为了探究网页的热度和网页之间的相关性，并实现网页价值排名，可以通过图计算的方法进行分析。本章任务如下。首先介绍图与图计算的基本概念、SparkGraphX图计算框架及其发展历程；并详细介绍GraphX中图计算的基础操作的方法；最后使用GraphX对某资讯网站数据进行分析，并使用GraphX内置的PageRank算法实现网页的价值排名。任务背景1了解GraphX常用API目录认识SparkGraphX2统计网页价值排名前10的网页3学习GraphX常用的图计算基础操作前，需要先了解图与图计算的基本概念，并对SparkGraphX图计算框架有基础的了解。本节的任务如下。了解图和图计算的基本概念；了解SparkGraphX的基础概念和发展历程为GraphX框架的使用奠定理论基础。任务描述图是由一个有穷非空顶点集合和一个描述顶点之间多对多关系的边集合组成的数据结构。图的结构通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。图可以按照无方向和有方向分为无向图和有向图。如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图；如果无重复的边或者顶点到自身的边叫简单图。了解图的基本概念淘宝图谱计算平台如何将各种图的指标精细化和规范化，对于产品和运营的构思进行数据上的预研指导，提供科学决策的依据，是图谱计算平台设计的初衷和出发点。基于这样的出发点，淘宝借助GraphX丰富的接口和工具包，针对淘宝内部林林总总的图业务需求，开发了一个图谱计算平台。新浪微博社交网络分析社交网络本身就是一个复杂的图关系结构的网络，最适合用图来表达和计算了，图的“顶点”表示社交中的人，“边”表示人与人之间的关系。如新浪微博社交网络分析，通过用户之间的关注、转发等行为建立了用户之间的社交网络关系图，根据用户在社交网络中所占位置为用户进行分析和应用。了解图计算的应用淘宝、腾讯的推荐应用如淘宝推荐商品，腾讯推荐好友等等，将商品之间的交互做成一张大的网络图，腾讯用户之间的关系做成一张社交网络图，在应用过程中就可以通过点与点之间的关系将与某商品相关的其他商品推荐给用户，或将朋友的朋友也推荐给你作为可能认识的人。了解图计算的应用Spark的每一个子框架都有一种抽象数据结构，SparkGraphX框架的核心抽象数据结构是弹性分布式属性图（ResilientDistributePropertyGraph，简称Graph）。Graph，一种点和边都带属性的有向多重图，边有起点和目的节点，顶点间可以有多重关系。它扩展了SparkRDD的抽象，有Table和Graph两种视图，而只需要一份物理存储。两种视图都有自己独有的操作符，从而获得了灵活操作和执行效率。了解GraphX的基础概念SparkGraphX是一个分布式图处理框架，是一个基于Spark平台提供图计算和图挖掘的简洁易用且丰富多彩的接口，极大地方便了大家对分布式图处理的需求。GraphX的分布式或者并行处理其实是把图拆分成很多的子图，然后分别对这些子图进行计算，计算的时候可以分别迭代进行分阶段的计算。SparkGraphX中包含了对图的一系列操作方法（例如，subgraph，joinvertices和aggregatemessages）以及优化的变种的PregelAPI。了解GraphX的基础概念GraphX的发展历程了解GraphX的发展历程1了解GraphX常用API目录认识SparkGraphX2统计网页价值排名前10的网页3SparkGraphX是图计算的利器，利用了Spark的分布式系统架构完成分布式图计算。为了使用GraphX构建网页结构图并进行网页价值排名计算，本节的任务如下。了解GraphX中的专业名称；学习在GraphX中创建和计算图的方法。任务描述Edge：边对象，存有srcId,dstId,attr三个字段，以及一些操作Edge的方法，例：Edge(srcId,dstId,attr)RDD[Edge]：存放着Edge对象的RDDEdgeRDD：完整提供边的各种操作类RDD[(VertexId,VD)]：存放顶点的RDD，顶点有VertexId和VD两个字段，第一个是顶点Id，第二个是顶点属性。定义一个顶点例如：（VertexId,VD）VertexRDD：提供顶点的各种操作方法的对象创建与存储图图的创建是进行图计算的重要步骤，在SparkGraphX中创建图的方式很多，根据不同的数据集有不同的方法。GraphX有一个类Graph，Graph对象是用户的操作入口，主要包含边属性edge（边）、顶点属性vertex（顶点）、图的创建方法、查询方法和其他转换方法等。创建与存储图1．图的创建用户信息vertices.txt，有3个字段，分别为用户Id，姓名和职业另一份数据“edges.txt”是用户之间的关系数据，有3个字段，第1、2个是用户Id，第3个是第1个用户对于第2个用户的关系，如“37Collaborator”表示3是7的合作伙伴。根据顶点数据和边数据，可以构建如图所示的用户关系网络图，顶点包含用户Id和用户属性，边有起点和目标点，并且有边属性和指向。创建与存储图在使用SparkGraphX进行操作时，需要先将指定的包导入。创建与存储图创建图的3种方法创建与存储图方法描述Graph(vertices,edges,defaultVertexAttr)根据分开存放的顶点数据和边数据创建图，适用于有顶点数据和边数据的情况Graph.fromEdges(RDD[Edge[ED]],defaultValue)根据边数据创建图，数据需要转换成RDD[Edge[ED]]类型，适用于边数据有边属性的的情况Graph.fromEdgeTuples(rawEdges:RDD[(VertexId,VertexId)],defaultValue)根据边数据创建图，边数据需要加载为二元组，可以选择是否对边分区，适用于边数据只有起点和目标点的情况根据有属性的顶点和边构建图（Graph(vertices,edges,defaultVertexAttr)）vertices:RDD[(VertexId,VD)]：“顶点”类型的RDD，其中VertexId为顶点ID（必须为Long类型），VD为顶点属性信息。edges:RDD[Edge[ED]]：

“边”类型的RDD，Edge类包含srcId（起点，Long类型）、dstId（目标点，Long类型），attr（边属性）三个部分。defaultVertexAttr：一个固定的顶点信息，用于当数据中出现顶点缺失时使用。了解GraphX常用API“顶点”

和“边”

的RDD来自不同的数据源，与Spark中其他RDD的建立并没有区别，但是顶点Id要求是Long类型。了解GraphX常用API查询创建完成的图graph_urelate，可以使用graph_urelate.vertices查看顶点信息，用graph_urelate.edges查看边信息。了解GraphX常用API根据边创建图（Graph.fromEdges(RDD[Edge[ED]],defaultValue)）这种方法相对而言最为简单，只是由Edge类型RDD建立图，边的属性没有则设为一个固定值，由“边”RDD中出现所有顶点（无论是起始点src还是目标点dst）自动产生顶点vertextId，顶点的属性将被设置为一个默认值。fromEdges方法有两个参数值如下。RDD[Edge[ED]]：“边”类型的RDD，Edge包含（srcId，dstId，prop）defaultValue:VD：默认顶点属性值。了解GraphX常用APIGraph.fromEdges创建图只需要边的数据。仅根据“edges.txt”

中的边数据创建图，顶点由边数据中出现的顶点决定。了解GraphX常用API对图的顶点和边进行查询如下图，文件中的边和边属性都加载到图中，顶点则根据边的数据提取了起点和目标点作为顶点，顶点属性默认值1。了解GraphX常用API根据边的两个顶点的元组创建图（Graph.fromEdgeTuples()）Graph.fromEdgeTuples()通过边的两个顶点ID组成的二元组创建图，将一条边的起点与目标点放在一个二元组中，通过边的二元组RDD创建图。rawEdges:RDD[(VertexId,VertexId)]：其中的数据类型是一个起点与目标点的元组defaultValue:VD：默认属性值。uniqueEdges:Option[PartitionStrategy]=None：是否对边进行分区选项，可选可不选，默认不分区了解GraphX常用APIfromEdgeTuples仅需要边的起点和目标点，将数据“edges.txt”作为输入数据，通过fromEdgeTuples方法构造图。了解GraphX常用API对图的边和顶点进行查询了解GraphX常用API常见的图的缓存和释放缓存方法了解GraphX常用API图的缓存及释放方法描述cache()缓存整个图，默认存储在内存中persist(newLevel:StorageLevel=StorageLevel.MEMORY_ONLY)缓存整个图，可以指定存储级别unpersist()释放整个图的缓存unpersistVertices(blocking:Boolean=true)释放顶点缓存edges.unpersist(blocking:Boolean=true)释放边缓存（1）图的缓存在Spark中，RDD默认没有持久化在内存中。当多次使用某个变量时，为了避免重复计算，变量必须被明确缓存，GraphX中的图也是相同的方式。当一个图需要多次计算使用时，需要对图进行缓存，缓存有cache和persist两种方法。对于persist，如果想指定缓存类型为StorageLevel.MEMORY_ONLY，需要导入org.apache.spark.storage.StorageLevel包。了解GraphX常用API（2）释放缓存对于已经完成计算无需再使用的缓存内容可以进行释放，在迭代过程中无需再使用的缓存也可以释放。释放缓存方法有如下3种。Graph.unpersist(blocking=true)：释放整个图缓存Graph.unpersistVertices(blocking=true)：释放内存中缓存的vertices。Graph.edges.unpersist(blocking=true)：释放边缓存，使用对边进行修改，但会重复使用点进行运算的操作。了解GraphX常用API图创建之后，对所创建的图进行查询。查询内容包括顶点与边的个数，顶点与边的视图，出度数（以当前顶点为起点的边的数量），入度数（以当前顶点为目标点的边的数量）。基本的方法如下表。查询与转换数据1．数据查询方法描述numVertices查询顶点个数numEdges查询边数degrees(in/out)查询度数vertices查询顶点信息edges查询边信息（1）顶点查询和边查询numEdges：查询图中边的数量numEdge方法可以查询边的数量，不需要输入任何参数，直接通过Graph.numEdges查询，返回类型为Long类型。numVertices：查询图中顶点个数numVertices方法可以查询顶点个数，不需要输入任何参数，直接通过Graph.numVertices查询，返回类型为Long类型。查询与转换数据（2）视图操作SparkGraphX中有3种基本视图可以访问，包括顶点视图（Vertices）、边视图（Edges）和整体视图（Triplets），如下图。假设有一个Graph的实例graph，通过graph.vertices、graph.edges、graph.triplets即可访问3种视图。查询与转换数据顶点视图：顶点视图可以查看顶点的信息，通过graph.vertices可以返回一个VertexRDD[(VD]，VD为顶点属性，它继承于RDD[(VertexID,VD)]，所以可以看到顶点的ID和属性，也可以用Scala的case表达式解构这个元组直接查看顶点信息：graph.vertices.collect通过模式匹配解构元组：根据返回的顶点字段数，通过模式匹配返回的RDD类型元组查询与转换数据顶点视图增加过滤条件的顶点视图：通过filter方法增加过滤条件查询感兴趣的顶点信息通过下标查询：可以直接根据Spark元组的特性通过下标的方式访问返回的顶点信息查询与转换数据边视图：边视图只会返回边的信息。graph.edges返回一个包含Edge[ED]对象的EdgeRDD，ED表示边属性的类型。Edge有三个字段：起点Id、目标点Id、边属性。并且可以通过case类的类型构造器匹配返回的EdgeRDD。直接查看所有边信息：graph.edges.collect查询与转换数据边视图通过模式匹配解构并且添加过滤条件：用模式匹配Edge类型的返回结果，再利用filter进行过滤通过下标查询：通过下标查询时，由于Edge类中有三个属性srcId，dstId和attr，因此可以直接指定属性访问查询与转换数据顶点与边的三元组整体视图：三元视图逻辑上将顶点和边的属性保存为一个RDD[EdgeTriplet[VD,ED]]，它包含EdgeTriplet类的实例。EdgeTriplet类继承于Edge类，所以可以直接访问Edge类的三个属性，并且加入了srcAttr和dstAttr成员，这两个成员分别包含起点和目标点的属性。graph.triplets可以查看到边和顶点的所有信息，是一个完整的视图直接查询：graph.triplets.collect，查询用户关系网络图，返回结果包含顶点和边的所有信息，包括边的起点和目标点，起点属性，目标点属性，边属性。查询与转换数据顶点与边的三元组整体视图通过下标查询：通过新成员变量srcAttr，dstAttr可以访问起点属性和目标点属性，可以用边的字段访问边的属性。查询与转换数据（3）度分布计算度分布计算：度分布检测的目的，主要是了解图中“超级节点”

的个数和规模，以及所有节点度的分布曲线。超级节点的存在对各种传播算法都会有重大的影响（不论是正面助力还是反面阻力），因此要预先对这些数据量有个预估。借助GraphX最基本的图信息接口degrees:VertexRDD[Int]（包括inDegrees和outDegrees），这个指标可以轻松计算出来，并进行各种各样的统计。degrees：返回每个顶点的度inDegrees：计算每个顶点的入度数，不需要参数outDegrees：计算顶点的出度，不需要参数查询与转换数据自定义函数&内置函数：用户如果想要对图的度进行一些特别的计算，比如最大最小值，平均值一类的计算，可以通过自定义函数的方式，也可以通过RDD所内置的函数完成。利用自定义函数统计度的最大值，如下图。使用RDD自带的统计函数进行度分布分析，使用RDD内置min，max，sortByKey，top等等对度进行统计，graph.degrees返回的是VertexRDD[Int]，即（VertexID，Int），需要调换成RDD[(Int,VetexId)]，因为这些函数都是对第一个值也就是key操作的。查询与转换数据转换数据操作的重要特征是，允许所得图形重用原有图形的结构索引，即还能保存图的结构。SparkGraphX常见的数据转换方法主要如下表。查询与转换数据2.

数据转换方法描述mapVertices[VD2:ClassTag](map:(VertexId,VD)=>VD2)对顶点属性经过变换生成新的图mapEdges[ED2](map:Edge[ED]=>ED2)对边属性经过变换生成新的图mapTriplets[ED2:ClassTag](map:EdgeTriplet[VD,ED]=>ED2)对边属性经过变换生成新的图（1）mapVertices()mapVertices:通过graph.mapVertices直接对顶点进行map，返回按用户提供函数改变了图中顶点属性的值或类型之后的图。该方法主要需要一个函数，调用Spark中的map操作，更新顶点的属性值，由VD-->newVD。查询与转换数据（2）mapEdges()mapEdges：通过graph.mapEdges直接对边的属性进行操作，调用Spark中的map操作更新边的属性值，由ED-->newED，返回按用户提供函数改变图中边属性的值或类型之后的图。查询与转换数据（3）mapTriplets()mapTriplets：该方法的操作也是针对边的属性值，通过调用Spark中的map操作更新边的属性值，由ED-->newED。例如将边的属性用起点的属性的第一个值姓名替换。查询与转换数据结构转换是对整个图的结构进行操作，生成新的图。SparkGraphX中图的结构转化操作方法也是存放在类Graph中，主要方法如下表。转换结构与关联聚合数据1.结构转换方法描述reverse反转图中所有边的方向subgraph按照设定条件取出子图mask取两个图的公共顶点和边作为新图，并保持前一个图顶点与边的属性groupEdges合并边相同的属性通过user.txt和relate.txt创建用户社交网络图reverse:返回一个新的图，这个图的边的方向与原图相比都是反转的。没有修改顶点或者边的属性或者改变边的数量，不需要输入其他参数。转换结构与关联聚合数据对社交网络图graph进行结构转换subgraph：创建子图的方法。子图是指节点集和边集分别是某一图的节点集的子集和边集的子集的图在graph.subgraph方法中需要输入边的过滤条件或顶点的过滤条件，顶点操作可以通过字段vpred匹配顶点属性个数。对于边属性，可以通过epred字段匹配，其中的属性可以通过默认属性名获取。转换结构与关联聚合数据对社交网络图graph进行结构转换mask：合并两个图并且只保留两个图中都有的顶点和边，在使用时需要输入另一个图作为参数。groupEdges：用来合并相同Id的边。转换结构与关联聚合数据关联转换与聚合操作是图计算的一个重点，通过关联操作可以将顶点属性值连接到图中。而聚合操作可以发送信息给指定顶点并将数据聚集起来，达到指定的目的。关联聚合的方法如下表。转换结构与关联聚合数据2．数据关联聚合方法描述collectNeighbors(edgeDirection:EdgeDirection)收集邻居顶点的顶点Id和顶点属性collectNeighborIds(edgeDirection:EdgeDirection)收集邻居顶点的顶点IdmapReduceTriplets向指定顶点发送信息并聚合信息aggregateMessages向指定顶点发送信息并聚合信息joinVertices将顶点信息更新到图中outerJoinVertices将顶点信息更新到图中（1）collectNeighbors()collectNeighbors：该方法的作用是收集每个顶点的邻居顶点的顶点Id和顶点属性，邻居顶点为与该点直接相连的顶点。该方法需要输入一个参数，返回的结果是顶点Id和顶点属性的元组。参数只有以下几种类型。EdgeDirection.Out：表示只收集以该顶点为起点，邻居顶点为目标点的邻居顶点的顶点Id和顶点信息。EdgeDirection.In：表示只收集以邻居顶点作为起点，该点作为目标点的邻居顶点的顶点Id和顶点信息。EdgeDirection.Either：收集所有邻居顶点的顶点Id和顶点信息。转换结构与关联聚合数据（2）collectNeighborIds()collectNeighborIds：该方法与collectNeighbors方法一致，只是该方法只返回顶点Id，不返回顶点信息。转换结构与关联聚合数据（3）aggregateMessages()aggregateMessages:GraphX中的核心聚合操作是aggregateMessages，它主要功能是向邻边发消息，合并邻边收到的消息。aggregateMessages方法定义如下。defaggregateMessages[Msg:ClassTag]( sendMsg:EdgeContext[VD,ED,Msg]=>Unit, mergeMsg:(Msg,Msg)=>Msg, tripletFields:TripletFields=TripletFields.All):VertexRDD[A]转换结构与关联聚合数据aggregateMessagessendMsg：看做map-reduce过程中的map函数，向邻边发消息，应用到图的每个边三元组(edgetriplet)。mergeMsg：指定两个消息到相同的顶点并保存为一个消息。可以将mergeMsg函数看做map-reduce过程中的reduce函数。TripletFields可选项：它指出哪些数据将被访问（源顶点特征，目的顶点特征或者两者同时，即有三种可选择的值：TripletFields.Src，TripletFields.Dst，TripletFields.All。转换结构与关联聚合数据（4）joinVertices()joinVertices：joinVertices的功能是连接其他顶点，将其他顶点的顶点信息与图中的顶点信息处理后更新图的顶点信息，返回值的类型就是图结构顶点属性的类型，不能新增，也不可以减少（即不能改变原始图结构顶点属性类型和个数）。转换结构与关联聚合数据（5）outerJoinVertices()outerJoinVertices:与前面JoinVertices不同之处在于顶点属性更新后类型是VD2，不再是VD，因此不受原图graph顶点属性类型VD的限制，在outerJoinVertices中使用者可以随意定义自己想要的返回类型，从而可以完全改变图的顶点属性值的类型和属性的个数。转换结构与关联聚合数据1了解GraphX常用API目录认识SparkGraphX2统计网页价值排名前10的网页3为探究某资讯网站内网页的热度和内容相关性，需要构建网页结构图，并使用图计算的方法实现网页排名。本节的任务如下。根据某资讯网站数据，使用SparkGraphX构建出网页结构图；使用GraphX内置的PageRank算法计算网页得分；根据网页得分降序排序找出排名前10的网页。任务描述目前所获得的某资讯网站数据有两份。一份是网页信息数据news_vertices.csv，可作为图的顶点数据。另一份数据是网页之间的链接关系数据news_edges.csv，可作为图的边数据。构建网页结构图的具体实现过程如下。将两份数据上传至HDFS中。在spark-shell中导入构建图所需要的包。读取news_vertices.csv文件的数据，并选择第1个和第3个数据字段（即自定义的网页简化ID和网页类型）作为顶点，读取news_