第7章 Spark GraphX-圖計算框架

SparkGraphX

——圖計算框架每個人對自己的人生都會有自己的價值定位和人生追求，生命雖然有限，但用生命所創(chuàng)造的價值，卻可以與世長存。人生的價值在于勞動、創(chuàng)造與貢獻。社會需要我們創(chuàng)造價值，體現的價值越高，人生才會越有意義。對于網頁而言，網頁也是存在價值的，對網頁價值進行分析，可以節(jié)省網站建設的時間成本，將更多的精力和資源集中在高價值網頁的設計上。PageRank即網頁排名，又稱網頁級別或佩奇排名，是用于標識網頁的等級或重要性的一種算法，也是衡量網站好壞的一種標準。通過PageRank算法可以計算網頁的價值，使等級更高、更重要的網頁在搜索結果中更容易被查找到，從而提高搜索結果的相關性和質量。任務背景現有兩份關于某資訊網站的數據，一份為網頁信息數據文件news_vertices.csv，包含3個數據字段，數據字段說明如下表。另一份為網頁之間的鏈接關系數據文件news_edges.csv，包含兩個數據字段，數據字段說明如下表。兩份文件的數據字段均使用“,”（逗號）進行分隔。任務背景字段名稱說明示例id自定義的簡化的網頁ID1network_id網頁ID191000000000page_type網頁類型，包括4種類型，分別為人才招聘、社區(qū)論壇、教育文化和新聞媒體社區(qū)論壇字段名稱說明示例id_1簡化的起始網頁ID1id_2簡化的連接網頁ID2由于網頁之間是有鏈接的，而PageRank是一個通過網頁鏈接計算網頁得分以進行網頁排名的算法，因此，為了探究網頁的熱度和網頁之間的相關性，并實現網頁價值排名，可以通過圖計算的方法進行分析。本章任務如下。首先介紹圖與圖計算的基本概念、SparkGraphX圖計算框架及其發(fā)展歷程；并詳細介紹GraphX中圖計算的基礎操作的方法；最后使用GraphX對某資訊網站數據進行分析，并使用GraphX內置的PageRank算法實現網頁的價值排名。任務背景1了解GraphX常用API目錄認識SparkGraphX2統計網頁價值排名前10的網頁3學習GraphX常用的圖計算基礎操作前，需要先了解圖與圖計算的基本概念，并對SparkGraphX圖計算框架有基礎的了解。本節(jié)的任務如下。了解圖和圖計算的基本概念；了解SparkGraphX的基礎概念和發(fā)展歷程為GraphX框架的使用奠定理論基礎。任務描述圖是由一個有窮非空頂點集合和一個描述頂點之間多對多關系的邊集合組成的數據結構。圖的結構通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。圖是一種數據元素間為多對多關系的數據結構，加上一組基本操作構成的抽象數據類型。圖（Graph）是一種復雜的非線性結構，在圖結構中，每個元素都可以有零個或多個前驅，也可以有零個或多個后繼，也就是說，元素之間的關系是任意的。圖可以按照無方向和有方向分為無向圖和有向圖。如果任意兩個頂點之間都存在邊叫完全圖，有向的邊叫有向完全圖；如果無重復的邊或者頂點到自身的邊叫簡單圖。了解圖的基本概念淘寶圖譜計算平臺如何將各種圖的指標精細化和規(guī)范化，對于產品和運營的構思進行數據上的預研指導，提供科學決策的依據，是圖譜計算平臺設計的初衷和出發(fā)點?；谶@樣的出發(fā)點，淘寶借助GraphX豐富的接口和工具包，針對淘寶內部林林總總的圖業(yè)務需求，開發(fā)了一個圖譜計算平臺。新浪微博社交網絡分析社交網絡本身就是一個復雜的圖關系結構的網絡，最適合用圖來表達和計算了，圖的“頂點”表示社交中的人，“邊”表示人與人之間的關系。如新浪微博社交網絡分析，通過用戶之間的關注、轉發(fā)等行為建立了用戶之間的社交網絡關系圖，根據用戶在社交網絡中所占位置為用戶進行分析和應用。了解圖計算的應用淘寶、騰訊的推薦應用如淘寶推薦商品，騰訊推薦好友等等，將商品之間的交互做成一張大的網絡圖，騰訊用戶之間的關系做成一張社交網絡圖，在應用過程中就可以通過點與點之間的關系將與某商品相關的其他商品推薦給用戶，或將朋友的朋友也推薦給你作為可能認識的人。了解圖計算的應用Spark的每一個子框架都有一種抽象數據結構，SparkGraphX框架的核心抽象數據結構是彈性分布式屬性圖（ResilientDistributePropertyGraph，簡稱Graph）。Graph，一種點和邊都帶屬性的有向多重圖，邊有起點和目的節(jié)點，頂點間可以有多重關系。它擴展了SparkRDD的抽象，有Table和Graph兩種視圖，而只需要一份物理存儲。兩種視圖都有自己獨有的操作符，從而獲得了靈活操作和執(zhí)行效率。了解GraphX的基礎概念SparkGraphX是一個分布式圖處理框架，是一個基于Spark平臺提供圖計算和圖挖掘的簡潔易用且豐富多彩的接口，極大地方便了大家對分布式圖處理的需求。GraphX的分布式或者并行處理其實是把圖拆分成很多的子圖，然后分別對這些子圖進行計算，計算的時候可以分別迭代進行分階段的計算。SparkGraphX中包含了對圖的一系列操作方法（例如，subgraph，joinvertices和aggregatemessages）以及優(yōu)化的變種的PregelAPI。了解GraphX的基礎概念GraphX的發(fā)展歷程了解GraphX的發(fā)展歷程1了解GraphX常用API目錄認識SparkGraphX2統計網頁價值排名前10的網頁3SparkGraphX是圖計算的利器，利用了Spark的分布式系統架構完成分布式圖計算。為了使用GraphX構建網頁結構圖并進行網頁價值排名計算，本節(jié)的任務如下。了解GraphX中的專業(yè)名稱；學習在GraphX中創(chuàng)建和計算圖的方法。任務描述Edge：邊對象，存有srcId,dstId,attr三個字段，以及一些操作Edge的方法，例：Edge(srcId,dstId,attr)RDD[Edge]：存放著Edge對象的RDDEdgeRDD：完整提供邊的各種操作類RDD[(VertexId,VD)]：存放頂點的RDD，頂點有VertexId和VD兩個字段，第一個是頂點Id，第二個是頂點屬性。定義一個頂點例如：（VertexId,VD）VertexRDD：提供頂點的各種操作方法的對象創(chuàng)建與存儲圖圖的創(chuàng)建是進行圖計算的重要步驟，在SparkGraphX中創(chuàng)建圖的方式很多，根據不同的數據集有不同的方法。GraphX有一個類Graph，Graph對象是用戶的操作入口，主要包含邊屬性edge（邊）、頂點屬性vertex（頂點）、圖的創(chuàng)建方法、查詢方法和其他轉換方法等。創(chuàng)建與存儲圖1．圖的創(chuàng)建用戶信息vertices.txt，有3個字段，分別為用戶Id，姓名和職業(yè)另一份數據“edges.txt”是用戶之間的關系數據，有3個字段，第1、2個是用戶Id，第3個是第1個用戶對于第2個用戶的關系，如“37Collaborator”表示3是7的合作伙伴。根據頂點數據和邊數據，可以構建如圖所示的用戶關系網絡圖，頂點包含用戶Id和用戶屬性，邊有起點和目標點，并且有邊屬性和指向。創(chuàng)建與存儲圖在使用SparkGraphX進行操作時，需要先將指定的包導入。創(chuàng)建與存儲圖創(chuàng)建圖的3種方法創(chuàng)建與存儲圖方法描述Graph(vertices,edges,defaultVertexAttr)根據分開存放的頂點數據和邊數據創(chuàng)建圖，適用于有頂點數據和邊數據的情況Graph.fromEdges(RDD[Edge[ED]],defaultValue)根據邊數據創(chuàng)建圖，數據需要轉換成RDD[Edge[ED]]類型，適用于邊數據有邊屬性的的情況Graph.fromEdgeTuples(rawEdges:RDD[(VertexId,VertexId)],defaultValue)根據邊數據創(chuàng)建圖，邊數據需要加載為二元組，可以選擇是否對邊分區(qū)，適用于邊數據只有起點和目標點的情況根據有屬性的頂點和邊構建圖（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的建立并沒有區(qū)別，但是頂點Id要求是Long類型。了解GraphX常用API查詢創(chuàng)建完成的圖graph_urelate，可以使用graph_urelate.vertices查看頂點信息，用graph_urelate.edges查看邊信息。了解GraphX常用API根據邊創(chuàng)建圖（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創(chuàng)建圖只需要邊的數據。僅根據“edges.txt”

中的邊數據創(chuàng)建圖，頂點由邊數據中出現的頂點決定。了解GraphX常用API對圖的頂點和邊進行查詢如下圖，文件中的邊和邊屬性都加載到圖中，頂點則根據邊的數據提取了起點和目標點作為頂點，頂點屬性默認值1。了解GraphX常用API根據邊的兩個頂點的元組創(chuàng)建圖（Graph.fromEdgeTuples()）Graph.fromEdgeTuples()通過邊的兩個頂點ID組成的二元組創(chuàng)建圖，將一條邊的起點與目標點放在一個二元組中，通過邊的二元組RDD創(chuàng)建圖。rawEdges:RDD[(VertexId,VertexId)]：其中的數據類型是一個起點與目標點的元組defaultValue:VD：默認屬性值。uniqueEdges:Option[PartitionStrategy]=None：是否對邊進行分區(qū)選項，可選可不選，默認不分區(qū)了解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圖創(chuàng)建之后，對所創(chuàng)建的圖進行查詢。查詢內容包括頂點與邊的個數，頂點與邊的視圖，出度數（以當前頂點為起點的邊的數量），入度數（以當前頂點為目標點的邊的數量）?；镜姆椒ㄈ缦卤?。查詢與轉換數據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）度分布計算度分布計算：度分布檢測的目的，主要是了解圖中“超級節(jié)點”

的個數和規(guī)模，以及所有節(jié)點度的分布曲線。超級節(jié)點的存在對各種傳播算法都會有重大的影響（不論是正面助力還是反面阻力），因此要預先對這些數據量有個預估。借助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創(chuàng)建用戶社交網絡圖reverse:返回一個新的圖，這個圖的邊的方向與原圖相比都是反轉的。沒有修改頂點或者邊的屬性或者改變邊的數量，不需要輸入其他參數。轉換結構與關聯聚合數據對社交網絡圖graph進行結構轉換subgraph：創(chuàng)建子圖的方法。子圖是指節(jié)點集和邊集分別是某一圖的節(jié)點集的子集和邊集的子集的圖在graph.subgraph方法中需要輸入邊的過濾條件或頂點的過濾條件，頂點操作可以通過字段vpred匹配頂點屬性個數。對于邊屬性，可以通過epred字段匹配，其中的屬性可以通過默認屬性名獲取。轉換結構與關聯聚合數據對社交網絡圖graph進行結構轉換mask：合并兩個圖并且只保留兩個圖中都有的頂點和邊，在使用時需要輸入另一個圖作為參數。groupEdges：用來合并相同Id的邊。轉換結構與關聯聚合數據關聯轉換與聚合操作是圖計算的一個重點，通過關聯操作可以將頂點屬性值連接到圖中。而聚合操作可以發(fā)送信息給指定頂點并將數據聚集起來，達到指定的目的。關聯聚合的方法如下表。轉換結構與關聯聚合數據2．數據關聯聚合方法描述collectNeighbors(edgeDirection:EdgeDirection)收集鄰居頂點的頂點Id和頂點屬性collectNeighborIds(edgeDirection:EdgeDirection)收集鄰居頂點的頂點IdmapReduceTriplets向指定頂點發(fā)送信息并聚合信息aggregateMessages向指定頂點發(fā)送信息并聚合信息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，它主要功能是向鄰邊發(fā)消息，合并鄰邊收到的消息。aggregateMessages方法定義如下。defaggregateMessages[Msg:ClassTag]( sendMsg:EdgeContext[VD,ED,Msg]=>Unit, mergeMsg:(Msg,Msg)=>Msg, tripletFields:TripletFields=TripletFields.All):VertexRDD[A]轉換結構與關聯聚合數據aggregateMessagessendMsg：看做map-reduce過程中的map函數，向鄰邊發(fā)消息，應用到圖的每個邊三元組(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為探究某資訊網站內網頁的熱度和內容相關性，需要構建網頁結構圖，并使用圖計算的方法實現網頁排名。本節(jié)的任務如下。根據某資訊網站數據，使用SparkGraphX構建出網頁結構圖；使用GraphX內置的PageRank算法計算網頁得分；根據網頁得分降序排序找出排名前10的網頁。任務描述目前所獲得的某資訊網站數據有兩份。一份是網頁信息數據news_vertices.csv，可作為圖的頂點數據。另一份數據是網頁之間的鏈接關系數據news_edges.csv，可作為圖的邊數據。構建網頁結構圖的具體實現過程如下。將兩份數據上傳至HDFS中。在spark-shell中導入構建圖所需要的包。讀取news_vertices.csv文件的數據，并選擇第1個和第3個數據字段（即自定義的網頁簡化ID和網頁類型）作為頂點，讀取news_