Spark GraphX怎么使用

本篇內(nèi)容介紹了“Spark GraphX怎么使用”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

GraphX簡(jiǎn)介

        在Spark年幼的時(shí)候，0.5版本就已經(jīng)帶了一個(gè)Bagel小模塊，提供了類(lèi)似Pregel的功能，當(dāng)然，這個(gè)版本還非常的原始，性能和功能都比較弱，屬于實(shí)驗(yàn)型產(chǎn)品。到0.8版本的時(shí)候，鑒于業(yè)界對(duì)分布式圖計(jì)算的需求日益見(jiàn)漲，Spark開(kāi)始獨(dú)立一個(gè)分支：Graphx-Branch，做為獨(dú)立的圖計(jì)算模塊，借鑒GraphLab，開(kāi)始設(shè)計(jì)開(kāi)發(fā)GraphX。在0.9版本中，這個(gè)模塊被正式集成到主干，雖然是alpha版本，但是已經(jīng)可以開(kāi)始進(jìn)行試用，小面包圈Bagel告別舞臺(tái)。1.0版本，GraphX正式投入生產(chǎn)使用。

        值得留意的是，GraphX目前依然處于快速發(fā)展中，從0.8的分支，到0.9和1.0，每個(gè)版本代碼都有不少的改進(jìn)和重構(gòu)，并根據(jù)觀察，在沒(méi)有改任何代碼邏輯和運(yùn)行環(huán)境，只是升級(jí)版本，切換接口和重新編譯的情況下，每個(gè)版本能夠有10-20%的性能提升。雖然和GraphLab的性能還有一定的差距，但是憑借著Spark整體的一體化流水線處理，社區(qū)熱烈的活躍度以及快速改進(jìn)速度，使得它具有強(qiáng)大的競(jìng)爭(zhēng)力。

分布式圖計(jì)算

        在正式介紹GraphX之前，先看看通用的分布式圖計(jì)算框架。簡(jiǎn)單來(lái)說(shuō)，分布式圖計(jì)算框架的目的，就是將對(duì)于巨型圖的各種操作，包裝為簡(jiǎn)單的接口，讓分布式存儲(chǔ)，并行計(jì)算等復(fù)雜問(wèn)題對(duì)上層透明。從而使得復(fù)雜網(wǎng)絡(luò)和圖算法的工程師，可以更加聚焦在圖相關(guān)的模型設(shè)計(jì)和使用上，而不用關(guān)心底層的分布式細(xì)節(jié)。為了實(shí)現(xiàn)該目的，需要解決兩個(gè)通用的問(wèn)題。

1. 圖存儲(chǔ)模式

巨型圖的存儲(chǔ)總體上有邊分割和點(diǎn)分割兩種存儲(chǔ)方式。2013年GraphLab2.0推出，將其存儲(chǔ)方式由邊分割變?yōu)辄c(diǎn)分割，在性能上取得重大提升，目前基本上被業(yè)界廣泛接受并使用。

• 邊分割（Edge Cut）

每個(gè)頂點(diǎn)都存儲(chǔ)一次，但是有的邊會(huì)被打斷，被分到了兩臺(tái)機(jī)器上。這樣做的好處是節(jié)省存儲(chǔ)空間，壞處是對(duì)于圖進(jìn)行基于邊的計(jì)算時(shí)，對(duì)于一條兩個(gè)頂點(diǎn)被分到不同機(jī)器上的邊來(lái)說(shuō)，要跨機(jī)器通信傳輸數(shù)據(jù)，內(nèi)網(wǎng)通信流量大。

• 點(diǎn)分割（Vertex Cut）

每個(gè)邊都只存儲(chǔ)一次，都只會(huì)出現(xiàn)在一臺(tái)機(jī)器上。鄰居多的點(diǎn)會(huì)被復(fù)制到多臺(tái)機(jī)器上，增加存儲(chǔ)開(kāi)銷(xiāo)，同時(shí)會(huì)引發(fā)數(shù)據(jù)同步的問(wèn)題。好處是可以大幅減少內(nèi)網(wǎng)通信量可以大大降低。

原本兩種方法互有利弊，但現(xiàn)在是點(diǎn)分割占上風(fēng)，各種分布式圖計(jì)算框架，都把自己底層的存儲(chǔ)形式變成了點(diǎn)分割。主要原因有2個(gè)：

1. 磁盤(pán)的價(jià)格下降，存儲(chǔ)空間不是問(wèn)題了，但是內(nèi)網(wǎng)的通信資源沒(méi)有突破性進(jìn)展，集群計(jì)算時(shí)內(nèi)網(wǎng)帶寬是寶貴的，時(shí)間比磁盤(pán)更珍貴，這點(diǎn)就類(lèi)似于常見(jiàn)的空間換時(shí)間的策略。

2. 在當(dāng)前的應(yīng)用場(chǎng)景中，絕大多數(shù)網(wǎng)絡(luò)都是“無(wú)尺度網(wǎng)絡(luò)”，遵循冪律分布，不同點(diǎn)的鄰居數(shù)量非常懸殊，邊分割會(huì)使得那些多鄰居的點(diǎn)所相連的邊大多數(shù)都會(huì)被分到不同的機(jī)器上，這樣的數(shù)據(jù)分布會(huì)使得內(nèi)網(wǎng)帶寬更加捉襟見(jiàn)肘，于是邊分割的存儲(chǔ)方式就被漸漸拋棄了

2. 圖計(jì)算模型

目前的圖計(jì)算框架，基本上都是遵循BSP計(jì)算模式。BSP全稱Bulk Synchronous Parallell，由哈佛大學(xué)Leslie Valiant和牛津大學(xué)Bill McColl提出。在BSP中，一次計(jì)算過(guò)程由一系列全局超步組成，每一個(gè)超步由并發(fā)計(jì)算，通訊， 柵欄同步三個(gè)步驟組成。同步完成，標(biāo)志著該一個(gè)超步的完成，以及下一個(gè)超步的開(kāi)始。

BSP模式很簡(jiǎn)潔，基于BSP模式，目前有2種比較成熟的圖計(jì)算模型：

• Pregel模型——“像頂點(diǎn)一樣思考”

2010年，Google的新的三架馬車(chē)Caffeine、Pregel、Dremel發(fā)布。伴隨著Pregel，BSP模型被廣為人知。據(jù)說(shuō)Pregel的名字是為了紀(jì)念歐拉的七橋問(wèn)題，那七座橋所在的河流，就是叫Pregel。

Pregel借鑒MapReduce的思想，提出了"像頂點(diǎn)一樣思考（Think Like A Vertex）"的圖計(jì)算模式，讓用戶無(wú)需考慮并行分布式計(jì)算的細(xì)節(jié)，只需要實(shí)現(xiàn)一個(gè)頂點(diǎn)更新函數(shù)，讓框架在遍歷頂點(diǎn)時(shí)進(jìn)行調(diào)用即可。

常見(jiàn)的代碼模板如下所示：

  void Compute(MessageIterator* msgs) {
      //遍歷由頂點(diǎn)入邊傳入的消息列表
      for (; !msgs->Done(); msgs->Next())
            doSomething()
      //生成新的頂點(diǎn)值
      *MutableVertexValue() = ...
      //生成沿頂點(diǎn)出邊發(fā)送的消息
    SendMessageToAllNeighbors(...);
  }

這個(gè)模型雖然簡(jiǎn)潔，但是很容易發(fā)現(xiàn)它的缺陷。對(duì)于鄰居數(shù)很多的頂點(diǎn)，它需要處理的消息非常龐大，而在這個(gè)模式下，它們是無(wú)法被并發(fā)處理的。所以對(duì)于符合冪律分布的自然圖，這種計(jì)算模型下，很容易發(fā)生假死或者崩潰。

• GAS模型——鄰居更新模型

相比于Pregel模型的消息通信范式，GraphLab的GAS模型更偏向共享內(nèi)存風(fēng)格。它允許用戶的自定義函數(shù)訪問(wèn)當(dāng)前頂點(diǎn)的整個(gè)鄰域，可以抽象成Gather，Apply，Scatter這三個(gè)階段，常被簡(jiǎn)稱為GAS。相應(yīng)用戶需要實(shí)現(xiàn)的三個(gè)獨(dú)立的函數(shù)：gather、apply和scatter。

常見(jiàn)的代碼模板如下所示：

  //從鄰居點(diǎn)和邊收集數(shù)據(jù)
  Message gather(Vertex u, Edge uv, Vertex v) {
      Message msg = ...
      return msg
  }
  //匯總函數(shù)
  Message sum(Message left, Message right) {
      return left+right
  }
  //更新頂點(diǎn)Master
  void apply(Vertex u, Message sum) {
      u.value = ...
  }
  //更新鄰邊和鄰居點(diǎn)  
  void scatter(Vertex u, Edge uv, Vertex v) {
      uv.value = ...
      if ((|u.delta|>ε) Active(v)
 }

由于gather/scatter函數(shù)是以單條邊為操作粒度，那么對(duì)于一個(gè)頂點(diǎn)的眾多鄰邊，可以分別由相應(yīng)的worker獨(dú)立地調(diào)用gather/scatter函數(shù)。這一設(shè)計(jì)主要是為了適應(yīng)點(diǎn)分割的圖存儲(chǔ)模式，從而避免Pregel模型會(huì)遇到的問(wèn)題。

GraphX的框架

        在GraphX設(shè)計(jì)的時(shí)候，點(diǎn)分割和GAS都已經(jīng)成熟了，所以GraphX一開(kāi)始就站在了巨人的肩膀上，并在設(shè)計(jì)和編碼中，針對(duì)這些問(wèn)題進(jìn)行了優(yōu)化，在功能和性能之間尋找最佳的平衡點(diǎn)。

        每個(gè)Spark子模塊，如同Spark本身一樣，都有一個(gè)核心的抽象。GraphX的核心抽象是Resilient Distributed Property Graph，一種點(diǎn)和邊都帶屬性的有向多重圖。它擴(kuò)展了Spark RDD的抽象，擁有Table和Graph兩種視圖，而只需要一份物理存儲(chǔ)。而兩種視圖都有自己的獨(dú)有的操作符，從而獲得靈活操作和執(zhí)行效率。

如同Spark一樣，GraphX的代碼依然非常簡(jiǎn)潔。核心的GraphX代碼只有3千多行，而在此之上實(shí)現(xiàn)的Pregel模型，只要短短的二十多行。GraphX的代碼結(jié)構(gòu)整體如下：

整體還是很清晰明了，其中大部分的impl包的實(shí)現(xiàn)，都是圍繞著Partition而優(yōu)化和進(jìn)行。這種某種程度上說(shuō)明了，點(diǎn)分割的存儲(chǔ)和相應(yīng)的計(jì)算優(yōu)化，的確是圖計(jì)算框架的重點(diǎn)和難點(diǎn)。

GraphX的設(shè)計(jì)要點(diǎn)

GraphX的底層設(shè)計(jì)有幾個(gè)關(guān)鍵點(diǎn)

1. 對(duì)Graph視圖的所有操作，最終都會(huì)被轉(zhuǎn)換成其關(guān)聯(lián)的Table視圖的RDD操作來(lái)完成。這樣對(duì)一個(gè)圖的計(jì)算，最終在邏輯上，等價(jià)于一系列RDD的轉(zhuǎn)換過(guò)程。因此，其實(shí)Graph最終是具備了的RDD的3個(gè)關(guān)鍵特性：Immutable，Distributed，F(xiàn)ault-Tolerant。其中最關(guān)鍵的是不可變（Immutable）性，所有圖的轉(zhuǎn)換和操作，邏輯上都是產(chǎn)生了一個(gè)新圖，物理上，Graphx會(huì)有一定程度的不變頂點(diǎn)和邊的復(fù)用優(yōu)化，對(duì)用戶透明。

2. 兩種視圖底層共用的物理數(shù)據(jù)，由RDD[VertexPartition]和RDD[EdgePartition]這兩個(gè)RDD組成。點(diǎn)和邊實(shí)際都不是以表Collection[tuple]的形式存儲(chǔ)的，而是由VertexPartition/EdgePartition，在內(nèi)部存儲(chǔ)一個(gè)帶索引結(jié)構(gòu)的分片數(shù)據(jù)塊，以加速不同視圖下的遍歷速度。不變的索引結(jié)構(gòu)在RDD轉(zhuǎn)換過(guò)程中是共用的，降低了計(jì)算和存儲(chǔ)開(kāi)銷(xiāo)。

3. 圖的分布式存儲(chǔ)采用點(diǎn)分割模式，而且使用partitionBy方法，由用戶指定不同的劃分策略（PartitionStrategy）。劃分策略會(huì)將邊分配到各個(gè)EdgePartition，頂點(diǎn)Master分配到各個(gè)VertexPartition，EdgePartition也會(huì)緩存本地邊的關(guān)聯(lián)點(diǎn)的Ghost副本。劃分策略的不同會(huì)影響到所需要緩存的Ghost副本數(shù)量，以及每個(gè)EdgePartition分配的邊的均衡程度，需要根據(jù)圖的結(jié)構(gòu)特征進(jìn)行選取最佳的Strategy。目前有EdgePartition2d，EdgePartition1d，RandomVertexCut，CanonicalRandomVertexCut這4種策略。目前試驗(yàn)的結(jié)果，在淘寶大部分場(chǎng)景下，EdgePartition2d效果最好。

GraphX的圖運(yùn)算符

如同Spark一樣，GraphX的Graph類(lèi)，提供了豐富的圖運(yùn)算符，大致結(jié)構(gòu)如下：

具體每個(gè)方法的說(shuō)明和用法，可以在官方的GraphX Programming Guide找到每個(gè)函數(shù)的詳細(xì)說(shuō)明，就不一一列舉。重點(diǎn)講幾個(gè)需要注意的方法：

圖的cache

由于一個(gè)圖，是由3個(gè)RDD組成的，所以會(huì)占用更多的內(nèi)存。相應(yīng)圖的cache，unpersist和checkpoint，更需要留意使用技巧。出于最大限度的復(fù)用邊的理念，GraphX的默認(rèn)接口，只提供了unpersistVertices的方法，如果要釋放邊，需要自己調(diào)用g.edges.unpersist()方法才能釋放，這個(gè)給用戶帶來(lái)了一定的不便，但是卻給GraphX的優(yōu)化，提供便利和空間。

參考Graphx的Pregel代碼，對(duì)一個(gè)大圖，目前最佳的實(shí)踐是：

    var g=...
    var prevG: Graph[VD, ED] = null

    while(...){
        prevG = g
        g = g.(………………)
        g.cache()
        prevG.unpersistVertices(blocking=false)
        prevG.edges.unpersist(blocking=false)
    }   

大體之意，就是根據(jù)GraphX中g(shù)raph的不變性，對(duì)g做了操作并賦回給g之后，g已經(jīng)不是原來(lái)的g了，而且會(huì)在下一輪迭代使用，所以必須cache。另外，你必須先用prevG，保留住對(duì)原來(lái)的圖的引用，并在新圖產(chǎn)生之后，快速的將舊圖徹底的釋放掉。否則一個(gè)大圖，幾輪迭代下來(lái)，就會(huì)有內(nèi)存泄漏的問(wèn)題，很快耗光作業(yè)內(nèi)存。

mrTriplet——鄰邊聚合

mrTriplets的全稱是mapReduceTriplets，它是GraphX中最核心和強(qiáng)大的一個(gè)接口。Pregel也基于它而來(lái)，所以對(duì)它的優(yōu)化，能很大程度上影響整個(gè)GraphX的性能。

mrTriplets運(yùn)算符的簡(jiǎn)化定義是：

def mapReduceTriplets[A](
      map: EdgeTriplet[VD, ED] => Iterator[(VertexId, A)],
      reduce: (A, A) => A)
    : VertexRDD[A]

它的計(jì)算過(guò)程如下：

1. map：應(yīng)用于每一個(gè)triplet上，生成一個(gè)或者多個(gè)消息， 消息以triplet關(guān)聯(lián)的兩個(gè)頂點(diǎn)中的任意一個(gè)或兩個(gè)為目標(biāo)頂點(diǎn)

2. reduce：應(yīng)用于每一個(gè)Vertex上，把發(fā)送給每一個(gè)頂點(diǎn)的消息合并起來(lái)

mrTriplets最后返回的是一個(gè)VertexRDD[A]， 它包含了每一個(gè)頂點(diǎn)聚合之后的消息（類(lèi)型為A）， 沒(méi)有接收到消息的頂點(diǎn)不會(huì)包含在返回的VertexRDD中。

在最近的版本，GraphX針對(duì)它進(jìn)行了如下幾個(gè)優(yōu)化，這些優(yōu)化，對(duì)于Pregel以及所有上層算法工具包的性能，都有著重大的影響。其中包括：

• Caching for Iterative mrTriplets & Incremental Updates for Iterative mrTriplets

  在很多圖分析算法中，不同點(diǎn)的收斂速度變化很大。在迭代的后期，只有很少的點(diǎn)會(huì)有更新。因此對(duì)于沒(méi)有更新的點(diǎn)，下一次mrTriplets計(jì)算時(shí)EdgeRDD無(wú)需更新相應(yīng)點(diǎn)值的本地緩存，能夠大幅降低通信開(kāi)銷(xiāo)。

• Indexing Active Edges

  沒(méi)有更新的頂點(diǎn)在下一輪迭代時(shí)就不需要向鄰居重新發(fā)送消息。因此mrTriplets遍歷邊時(shí)，如果一條邊的鄰居點(diǎn)值在上一輪迭代時(shí)沒(méi)有更新，可以直接跳過(guò)，避免了大量無(wú)用的計(jì)算和通信。

• Join Elimination

  一個(gè)triplet是由一條邊和其兩個(gè)鄰居點(diǎn)組成的三元組，操作triplet的map函數(shù)常常只需訪問(wèn)其兩個(gè)鄰居點(diǎn)值中的一個(gè)。例如在PageRank計(jì)算中，一個(gè)點(diǎn)值的更新只和其源頂點(diǎn)的值有關(guān)，而其所指向的目的頂點(diǎn)的值無(wú)關(guān)。那么在mrTriplets計(jì)算中，就不需要VertexRDD和EdgeRDD的3-way join，而只需要2-way join。

所有的這些優(yōu)化，都使得GraphX的性能，逐漸逼近GraphLab。雖然還有一定的差距，但是一體化的流水線服務(wù)，和豐富的編程接口，可以彌補(bǔ)性能的稍微差距。

進(jìn)化的Pregel計(jì)算模型

Graphx中的Pregel接口，并不嚴(yán)格遵循Pregel的模型，它是一個(gè)參考GAS改進(jìn)的Pregel模型。定義如下：

def pregel[A](initialMsg: A, maxIterations: Int, activeDirection: EdgeDirection)(
      vprog: (VertexID, VD, A) => VD,
      sendMsg: EdgeTriplet[VD, ED] => Iterator[(VertexID,A)],
      mergeMsg: (A, A) => A)
    : Graph[VD, ED]

這種基于mrTrilets方法的Pregel模型，和標(biāo)準(zhǔn)的Pregel的最大區(qū)別是，它的第2段參數(shù)體，接受的是3個(gè)函數(shù)參數(shù)，而不接受messageList。它不會(huì)在單個(gè)頂點(diǎn)上進(jìn)行消息遍歷，而是會(huì)將頂點(diǎn)的多個(gè)ghost副本收到的消息聚合后，發(fā)送給master副本，再使用vprog函數(shù)來(lái)更新點(diǎn)值。消息的接收和發(fā)送，都是被自動(dòng)并行化處理的，無(wú)需擔(dān)心超級(jí)節(jié)點(diǎn)的問(wèn)題。

常見(jiàn)的代碼模板如下所示：

    //更新頂點(diǎn)
    vprog(vid: Long, vert: Vertex, msg: Double): Vertex = {
       v.score = msg + (1 - ALPHA) * v.weight
    }
    //發(fā)送消息
    sendMsg(edgeTriplet: EdgeTriplet[…]): Iterator[(Long, Double)]
        (destId, ALPHA * edgeTriplet.srcAttr.score * edgeTriplet.attr.weight) 
    }
    //合并消息
    mergeMsg(v1: Double, v2: Double): Double = {
        v1+v2   
    }

可以看到，GraphX設(shè)計(jì)這個(gè)模型的用意。它綜合了Pregel和GAS兩者的優(yōu)點(diǎn)，即接口相對(duì)簡(jiǎn)單，又保證性能，可以應(yīng)對(duì)點(diǎn)分割的圖存儲(chǔ)模式，勝任符合冪律分布的自然圖的大型計(jì)算。另外值得注意的是，官方的Pregel版本是最簡(jiǎn)單的一個(gè)版本，對(duì)于復(fù)雜的業(yè)務(wù)場(chǎng)景，根據(jù)這個(gè)版本擴(kuò)展一個(gè)定制的Pregel，是很常見(jiàn)的做法。

圖算法工具包

        GraphX也提供了一套圖算法，方便用戶對(duì)圖進(jìn)行分析。目前最新版本，已經(jīng)支持PageRank，數(shù)三角形，最大連通圖，最短路徑等6種經(jīng)典的圖算法，這些算法的代碼實(shí)現(xiàn)，目的和重點(diǎn)在于通用性。如果要獲得最佳性能，可以參考其實(shí)現(xiàn)，進(jìn)行修改和擴(kuò)展，可以滿足業(yè)務(wù)需求。另外研讀這些代碼，也是理解GraphX編程的Best Practice的好方法，建議有興趣深入研究分布式圖算法開(kāi)發(fā)的同學(xué)都通讀一遍。

GraphX在淘寶

1. 圖譜體檢平臺(tái)

基本上，所有的關(guān)系，都可以從圖的角度來(lái)看待和處理，但是到底一個(gè)關(guān)系的價(jià)值多大？健康與否？適合用于什么場(chǎng)景？很多時(shí)候是靠運(yùn)營(yíng)和產(chǎn)品憑感覺(jué)來(lái)判斷和評(píng)估。如何將各種圖的指標(biāo)精細(xì)化，規(guī)范化，對(duì)于產(chǎn)品和運(yùn)營(yíng)的構(gòu)思進(jìn)行數(shù)據(jù)上的預(yù)研指導(dǎo)，提供科學(xué)決策的依據(jù)，是圖譜體檢平臺(tái)設(shè)計(jì)的初衷和出發(fā)點(diǎn)。

基于這樣的出發(fā)點(diǎn),借助GraphX豐富的接口和工具包,針對(duì)淘寶內(nèi)部林林總總的圖業(yè)務(wù)需求, 我們開(kāi)發(fā)一個(gè)圖譜體檢平臺(tái)。目前主要進(jìn)行下列指標(biāo)的檢查：

• 度分布

度分布是一個(gè)圖最基礎(chǔ)的指標(biāo)，也是非常重要的一個(gè)指標(biāo)。度分布檢測(cè)的目的，主要是了解圖中"超級(jí)節(jié)點(diǎn)"的個(gè)數(shù)和規(guī)模，以及所有節(jié)點(diǎn)度的分布曲線。超級(jí)節(jié)點(diǎn)的存在，對(duì)各種傳播算法，都會(huì)有重大的影響，不論是正面助力還是反面的阻力，所以要預(yù)先對(duì)于這些數(shù)據(jù)量有個(gè)預(yù)估。借助GraphX的最基本的圖信息接口：degrees: VertexRDD[Int]，包括inDegrees和outDegrees，這個(gè)指標(biāo)可以輕松地計(jì)算出來(lái)，并進(jìn)行各種各樣的統(tǒng)計(jì)。

• 二跳鄰居數(shù)

對(duì)于大部分社交關(guān)系來(lái)說(shuō)，只獲得一跳的度分布是遠(yuǎn)遠(yuǎn)不夠的，另一個(gè)重要的指標(biāo)是二跳鄰居數(shù)。例如秘密App中，好友的好友的秘密，傳播的范圍更廣，信息量更豐富。因此二跳鄰居數(shù)的統(tǒng)計(jì)，是圖譜體檢中很重要的一個(gè)指標(biāo)。二跳鄰居的計(jì)算GraphX沒(méi)有給出現(xiàn)成的接口，需要自己設(shè)計(jì)和開(kāi)發(fā)。目前使用的方法是：

• 第一次遍歷，所有點(diǎn)往鄰居點(diǎn)傳播一個(gè)帶自身Id，生命值為2的消息

• 第二次遍歷，所有點(diǎn)將收到的消息，往鄰居點(diǎn)再轉(zhuǎn)發(fā)一次，生命值為1

• 最終統(tǒng)計(jì)所有點(diǎn)上，接收到的生命值為1的Id，并進(jìn)行分組匯總，得到所有點(diǎn)的二跳鄰居

值得注意的是，進(jìn)行這個(gè)計(jì)算之前，需要借助度分布，將圖中的超級(jí)節(jié)點(diǎn)去掉，不納入二跳鄰居數(shù)的計(jì)算。否則這些超級(jí)節(jié)點(diǎn)一來(lái)會(huì)出現(xiàn)在第一輪傳播后，收到過(guò)多的消息而爆掉，二來(lái)它們參與計(jì)算，會(huì)影響和它們有一跳鄰居關(guān)系的頂點(diǎn)，導(dǎo)致它們不能得到真正有效的二跳鄰居數(shù)。所以必須先篩選掉。

• 連通圖

檢測(cè)連通圖的目的，是弄清一個(gè)圖有幾個(gè)連通部分，以及每個(gè)連通部分有多少頂點(diǎn)。這樣可以將一個(gè)大圖分割為多個(gè)小圖，并去掉零碎的連通部分，從而可以在多個(gè)小子圖上，進(jìn)行更加精細(xì)的操作。目前GraphX提供了ConnectedComponents和StronglyConnectedComponents算法，使用它們可以快速的計(jì)算出相應(yīng)的連通圖。

連通圖可以進(jìn)一步演化，變成社區(qū)發(fā)現(xiàn)算法，而該算法優(yōu)劣的評(píng)判標(biāo)準(zhǔn)之一，是計(jì)算模塊的Q值，來(lái)查看所謂的modularity情況。但是GraphX中還是沒(méi)有對(duì)于Q值計(jì)算的函數(shù)，我們已經(jīng)實(shí)現(xiàn)了一個(gè)，后續(xù)會(huì)將這個(gè)實(shí)現(xiàn)提交到社區(qū)。

更多的指標(biāo)，例如Triangle Count和K-Core，無(wú)論是借助GraphX已有的函數(shù)，還是自己從頭開(kāi)發(fā)，都陸續(xù)在進(jìn)行中。目前這個(gè)圖譜體檢平臺(tái)已經(jīng)初具規(guī)模，通過(guò)平臺(tái)的建立和推廣，圖相關(guān)的產(chǎn)品和業(yè)務(wù)，逐漸走上“無(wú)數(shù)據(jù)，不討論，用指標(biāo)來(lái)預(yù)估效果”的數(shù)據(jù)化運(yùn)營(yíng)之路，有效提高溝通效率，為各種圖相關(guān)的業(yè)務(wù)開(kāi)發(fā)走上科學(xué)化和系統(tǒng)化之路做好準(zhǔn)備。

2. 多圖合并工具

        在圖譜體檢平臺(tái)的基礎(chǔ)上，我們可以了解到各種各樣關(guān)系的特點(diǎn)。不同的關(guān)系，都會(huì)有自己的強(qiáng)項(xiàng)和弱項(xiàng)，例如有些關(guān)系圖譜連通性好些，而有些關(guān)系圖譜的社交性好些，所以往往我們需要使用關(guān)系A(chǔ)來(lái)豐富關(guān)系B。為此，在圖譜體檢平臺(tái)之上，借助GraphX，我們開(kāi)發(fā)了一個(gè)多圖合并工具，提供類(lèi)似于圖的并集的概念，可以快速的對(duì)指定的2個(gè)不同關(guān)系圖譜，進(jìn)行合并，產(chǎn)生一個(gè)新的關(guān)系圖譜。

以用基于A關(guān)系的圖來(lái)擴(kuò)充基于B關(guān)系的圖，生成擴(kuò)充圖C為例，融合算法基本思路如下：

1. 若圖B中某邊的兩個(gè)頂點(diǎn)都在圖A中，則將該邊加入C圖(如BD邊)

2. 若圖B中某邊的一個(gè)頂點(diǎn)在圖A中，另外一個(gè)頂點(diǎn)不在，則將該邊和另一頂點(diǎn)都加上(如CE邊和E點(diǎn))

3. 若圖A中某邊的兩個(gè)頂點(diǎn)都不在圖B中，則舍棄這條邊和頂點(diǎn)(如EF邊)

使用GraphX的outerJoinVertices等圖運(yùn)算符，可以很簡(jiǎn)單地完成上述的操作。另外，在考慮圖合并的時(shí)候，也可以考慮給不同的圖的邊加上不同的權(quán)重，綜合考慮點(diǎn)之間的不同關(guān)系的重要性。新產(chǎn)生的圖，會(huì)再進(jìn)行一輪圖譜體檢，通過(guò)前后三個(gè)圖各個(gè)體檢指標(biāo)的對(duì)比，可以對(duì)于業(yè)務(wù)上線之后效果有個(gè)預(yù)估和判斷。如果不符合期望，可以嘗試重新選擇擴(kuò)充方案。

3. 能量傳播模型

        加權(quán)網(wǎng)絡(luò)上的能量傳播是經(jīng)典的圖模型之一， 可用于用戶信譽(yù)度預(yù)測(cè)。模型的思路是：物以類(lèi)聚，人以群分。常和信譽(yù)度高的用戶進(jìn)行交易的，信譽(yù)度自然較高，常和信譽(yù)度差的用戶有業(yè)務(wù)來(lái)往的，信譽(yù)度自然較低。模型不復(fù)雜，但淘寶全網(wǎng)有上億的用戶點(diǎn)和幾十億關(guān)系邊，要對(duì)如此規(guī)模的巨型圖進(jìn)行能量傳播，并對(duì)邊的權(quán)重進(jìn)行精細(xì)的調(diào)節(jié)，對(duì)圖計(jì)算框架的性能和功能都是巨大的考驗(yàn)。借助GraphX，我們?cè)谶@兩點(diǎn)之間取得了平衡，成功實(shí)現(xiàn)了該模型。

        流程如圖4，先生成以用戶為點(diǎn)、買(mǎi)賣(mài)關(guān)系為邊的巨型圖initGraph，對(duì)選出種子用戶，分別賦予相同的初始正負(fù)能量值(TrustRank & BadRank)，然后進(jìn)行兩輪隨機(jī)游走，一輪好種子傳播正能量（tr），一輪壞種子傳播負(fù)能量（br），然后正負(fù)能量相減得到finalRank，根據(jù)finalRank判斷用戶的好壞。邊的初始傳播強(qiáng)度是0.85，這時(shí)AUC很低，需要再給每條邊，帶上一個(gè)由多個(gè)特征（交易次數(shù)，金額……）組成的組合權(quán)重。每個(gè)特征，都有不同的獨(dú)立權(quán)重和偏移量。通過(guò)使用partialDerivativeAUC方法，在訓(xùn)練集上計(jì)算AUC，然后對(duì)AUC求偏導(dǎo)，得到每個(gè)關(guān)系維度的獨(dú)立權(quán)重和偏移量，生成新的權(quán)重調(diào)節(jié)器（WeightAdjustor），對(duì)圖上所有邊上的權(quán)重更新，然后再進(jìn)行新一輪大迭代，這樣一直到AUC穩(wěn)定時(shí)，終止計(jì)算。

        在接近全量的數(shù)據(jù)上進(jìn)行3輪大迭代，每輪2+6次Pregel，每次Pregel大約30次小迭代后，最終的AUC從0.6提升到0.9，達(dá)到了不錯(cuò)的用戶預(yù)測(cè)準(zhǔn)確率。訓(xùn)練時(shí)長(zhǎng)在6個(gè)小時(shí)左右，無(wú)論在性能還是準(zhǔn)確率上，都超越業(yè)務(wù)方的期望。

未來(lái)圖計(jì)算的前景

        經(jīng)過(guò)半年多的嘗試，對(duì)于GraphX可以勝任的圖計(jì)算的規(guī)模和性能，目前我們都已經(jīng)心中有數(shù)。之前一些想做，但因?yàn)闆](méi)有足夠的計(jì)算能力而不能實(shí)現(xiàn)的圖模型，現(xiàn)已經(jīng)不是問(wèn)題。我們將會(huì)進(jìn)一步將越來(lái)越多的圖模型，在GraphX上實(shí)現(xiàn)。

        這些模型應(yīng)用于用戶網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)、用戶影響力、能量傳播、標(biāo)簽傳播等，可以提升用戶粘性和活躍度；而應(yīng)用到推薦領(lǐng)域的標(biāo)簽推理，人群劃分、年齡段預(yù)測(cè)、商品交易時(shí)序跳轉(zhuǎn)，則可以提升推薦的豐富度和準(zhǔn)確性。復(fù)雜網(wǎng)絡(luò)和圖計(jì)算的天地廣闊無(wú)垠，有更多的未知等待我們?nèi)ヌ剿骱蛯?shí)踐，借助Spark GraphX，未來(lái)我們可以迎接更大挑戰(zhàn)。

“Spark GraphX怎么使用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！