GraphX 在圖數(shù)據(jù)庫 Nebula Graph 的圖計算實踐

不同來源的異構(gòu)數(shù)據(jù)間存在著千絲萬縷的關(guān)聯(lián)，這種數(shù)據(jù)之間隱藏的關(guān)聯(lián)關(guān)系和網(wǎng)絡(luò)結(jié)構(gòu)特性對于數(shù)據(jù)分析至關(guān)重要，圖計算就是以圖作為數(shù)據(jù)模型來表達(dá)問題并予以解決的過程。

圖計算實踐

一、背景

隨著網(wǎng)絡(luò)信息技術(shù)的飛速發(fā)展，數(shù)據(jù)逐漸向多源異構(gòu)化方向發(fā)展，且不同來源的異構(gòu)數(shù)據(jù)之間也存在的千絲萬縷的關(guān)聯(lián)，這種數(shù)據(jù)之間隱藏的關(guān)聯(lián)關(guān)系和網(wǎng)絡(luò)結(jié)構(gòu)特性對于數(shù)據(jù)分析至關(guān)重要。但傳統(tǒng)關(guān)系型數(shù)據(jù)庫在分析大規(guī)模數(shù)據(jù)關(guān)聯(lián)特性時存在性能缺陷、表達(dá)有限等問題，因此有著更強(qiáng)大表達(dá)能力的圖數(shù)據(jù)受到業(yè)界極大重視，圖計算就是以圖作為數(shù)據(jù)模型來表達(dá)問題并予以解決的過程。圖可以融合多源多類型的數(shù)據(jù)，除了可以展示數(shù)據(jù)靜態(tài)基礎(chǔ)特性之外，還可通過圖計算展示隱藏在數(shù)據(jù)之間的圖結(jié)構(gòu)特性和點對關(guān)聯(lián)關(guān)系，成為社交網(wǎng)絡(luò)、推薦系統(tǒng)、知識圖譜、金融風(fēng)控、網(wǎng)絡(luò)安全、文本檢索等領(lǐng)域重要的分析手段。

二、算法應(yīng)用

為了支撐大規(guī)模圖計算的業(yè)務(wù)需求，Nebula Graph 基于 GraphX 提供了 PageRank 和 Louvain 社區(qū)發(fā)現(xiàn)的圖計算算法，允許用戶通過提交 Spark 任務(wù)的形式執(zhí)行算法應(yīng)用。此外，用戶也可以通過 Spark Connector 編寫 Spark 程序調(diào)用 GraphX 自帶的其他圖算法，如 LabelPropagation、ConnectedComponent 等。

PageRank

PageRank 是谷歌提出的用于解決鏈接分析中網(wǎng)頁排名問題的算法，目的是為了對互聯(lián)網(wǎng)中數(shù)以億計的網(wǎng)頁進(jìn)行排名。

PageRank 簡介

美國斯坦福大學(xué)的 Larry Page 和 Sergey Brin 在研究網(wǎng)頁排序問題時采用學(xué)術(shù)界評判論文重要性的方法，即看論文的引用量以及引用該論文的論文質(zhì)量，對應(yīng)于網(wǎng)頁的重要性有兩個假設(shè)：

  1. 數(shù)量假設(shè)：如果一個網(wǎng)頁 A 被很多其他網(wǎng)頁鏈接到，則該網(wǎng)頁比較重要；
  2. 質(zhì)量假設(shè)：如果一個很重要的網(wǎng)頁鏈接到網(wǎng)頁 A，則該網(wǎng)頁的重要性會被提高。

并基于這兩個假設(shè)提出 PageRank 算法。

PageRank 應(yīng)用場景

社交應(yīng)用的相似度內(nèi)容推薦

在對微博、微信等社交平臺進(jìn)行社交網(wǎng)絡(luò)分析時，可以基于 PageRank 算法根據(jù)用戶通常瀏覽的信息以及停留時間實現(xiàn)基于用戶的相似度的內(nèi)容推薦；

分析用戶社交影響力

在社交網(wǎng)絡(luò)分析時根據(jù)用戶的 PageRank 值進(jìn)行用戶影響力分析；

文獻(xiàn)重要性研究

根據(jù)文獻(xiàn)的 PageRank 值評判該文獻(xiàn)的質(zhì)量，PageRank 算法就是基于評判文獻(xiàn)質(zhì)量的想法來實現(xiàn)設(shè)計。

此外 PageRank 在數(shù)據(jù)分析和挖掘中也有很多的應(yīng)用。

算法思路

GraphX 的 PageRank 算法是基于 Pregel 計算模型的，該算法流程包括 3 步驟：

  1. 為圖中每個節(jié)點（網(wǎng)頁）設(shè)置一個同樣的初始 PageRank 值；
  2. 第一次迭代：沿邊發(fā)送消息，每個節(jié)點收到所有關(guān)聯(lián)邊上對點的信息，得到一個新的 PageRank 值；
  3. 第二次迭代：用這組新的 PageRank 按不同算法模式對應(yīng)的公式形成節(jié)點自己新的 PageRank。

Louvain 社區(qū)發(fā)現(xiàn)

Louvain 是用來進(jìn)行社會網(wǎng)絡(luò)挖掘的社區(qū)發(fā)現(xiàn)算法，屬于圖的聚類算法。

Louvain 算法介紹

Louvain 是基于模塊度（Modularity）的社區(qū)發(fā)現(xiàn)算法，通過模塊度來衡量一個社區(qū)的緊密程度。如果一個節(jié)點加入到某一社區(qū)中會使得該社區(qū)的模塊度相比其他社區(qū)有最大程度的增加，則該節(jié)點就應(yīng)當(dāng)屬于該社區(qū)。如果加入其它社區(qū)后沒有使其模塊度增加，則留在自己當(dāng)前社區(qū)中。

模塊度

模塊度公式

模塊度 Q 的物理意義：社區(qū)內(nèi)節(jié)點的連邊數(shù)與隨機(jī)情況下的邊數(shù)之差，定義函數(shù)如下：

image

其中

image

：節(jié)點 i 和節(jié)點 j 之間邊的權(quán)重


image

：所有與節(jié)點 i 相連的邊的權(quán)重之和


image
：節(jié)點 i 所屬的社區(qū)
image
： 圖中所有邊的權(quán)重之和

模塊度公式變形

在此公式中，只有節(jié)點 i 和節(jié)點 j 屬于同一社區(qū)，公式才有意義，所以該公式是衡量的某一社區(qū)內(nèi)的緊密度。對于該公式的簡化變形如下：

image
image

表示： 社區(qū) c 內(nèi)的邊的權(quán)重之和


image

表示： 所有與社區(qū) c 內(nèi)節(jié)點相連的邊的權(quán)重之和（因為 i 屬于社區(qū) c）包括社區(qū)內(nèi)節(jié)點與節(jié)點 i 的邊和社區(qū)外節(jié)點與節(jié)點 i 的邊。


image
表示： 所有與社區(qū) c 內(nèi)節(jié)點相連的邊的權(quán)重之和（因為 j 屬于社區(qū) c）包括社區(qū)內(nèi)節(jié)點與節(jié)點 j 的邊和社區(qū)外節(jié)點與節(jié)點 j 的邊。
image
代替
image

和
image
。（即社區(qū) c 內(nèi)邊權(quán)重和 + 社區(qū) c 與其他社區(qū)連邊的權(quán)重和）

求解模塊度變化

在 Louvain 算法中不需要求每個社區(qū)具體的模塊度，只需要比較社區(qū)中加入某個節(jié)點之后的模塊度變化，所以需要求解 △Q。

將節(jié)點 i 分配到某一社區(qū)中，社區(qū)的模塊度變化為：

image

其中

image

： 社區(qū)內(nèi)所有節(jié)點與節(jié)點 i 連邊權(quán)重之和（對應(yīng)新社區(qū)的實際內(nèi)部權(quán)重和乘以 2，因為
image

對于社區(qū)內(nèi)所有的頂點 i，每條邊其實被計算了兩次）


image
： 所有與節(jié)點 i 相連的邊的權(quán)重之和
故實現(xiàn)算法時只需求
image

即可。

Louvain 應(yīng)用場景

  • 金融風(fēng)控

在金融風(fēng)控場景中，可以根據(jù)用戶行為特征進(jìn)行團(tuán)伙識別；

  • 社交網(wǎng)絡(luò)

可以基于網(wǎng)絡(luò)關(guān)系中點對之間關(guān)聯(lián)的廣度和強(qiáng)度進(jìn)行社交網(wǎng)絡(luò)劃分；對復(fù)雜網(wǎng)絡(luò)分析、電話網(wǎng)絡(luò)分析人群之間的聯(lián)系密切度；

  • 推薦系統(tǒng)

基于用戶興趣愛好的社區(qū)發(fā)現(xiàn)，可以根據(jù)社區(qū)并結(jié)合協(xié)同過濾等推薦算法進(jìn)行更精確有效的個性化推薦。

Louvain 算法思路

Louvain 算法包括兩個階段，其流程就是這兩個階段的迭代過程。

階段一：不斷地遍歷網(wǎng)絡(luò)圖中的節(jié)點，通過比較節(jié)點給每個鄰居社區(qū)帶來的模塊度的變化，將單個節(jié)點加入到能夠使 Modularity 模塊度有最大增量的社區(qū)中。
（比如節(jié)點 v 分別加入到社區(qū) A、B、C 中，使得三個社區(qū)的模塊度增量為-1， 1， 2， 則節(jié)點 v 最終應(yīng)該加入到社區(qū) C 中）

階段二：對第一階段進(jìn)行處理，將屬于同一社區(qū)的頂點合并為一個大的超點重新構(gòu)造網(wǎng)絡(luò)圖，即一個社區(qū)作為圖的一個新的節(jié)點。此時兩個超點之間邊的權(quán)重是兩個超點內(nèi)所有原始頂點之間相連的邊權(quán)重之和，即兩個社區(qū)之間的邊權(quán)重之和。

下面是對第一二階段的實例介紹。

?
Louvain 社區(qū)算法

第一階段遍歷圖中節(jié)點加入到其所屬社區(qū)中，得到中間的圖，形成四個社區(qū)；

第二節(jié)點對社區(qū)內(nèi)的節(jié)點進(jìn)行合并成一個超級節(jié)點，社區(qū)節(jié)點有自連邊，其權(quán)重為社區(qū)內(nèi)部所有節(jié)點間相連的邊的權(quán)重之和的 2 倍，社區(qū)之間的邊為兩個社區(qū)間頂點跨社區(qū)相連的邊的權(quán)重之和，如紅色社區(qū)和淺綠色社區(qū)之間通過（8,11）、（10，11）、（10,13）相連，所以兩個社區(qū)之間邊的權(quán)重為 3。

注：社區(qū)內(nèi)的權(quán)重為所有內(nèi)部結(jié)點之間邊權(quán)重的兩倍，因為 Kin 的概念是社區(qū)內(nèi)所有節(jié)點與節(jié)點 i 的連邊和，在計算某一社區(qū)的 Kin 時，實際上每條邊都被其兩端的頂點計算了一次，一共被計算了兩次。

整個 Louvain 算法就是不斷迭代第一階段和第二階段，直到算法穩(wěn)定（圖的模塊度不再變化）或者到達(dá)最大迭代次數(shù)。

三、算法實踐

演示環(huán)境

  • 三臺虛擬機(jī)，環(huán)境如下：
    • Cpu name：Intel(R) Xeon(R) Platinum 8260M CPU @ 2.30GHz
    • Processors：32
    • CPU Cores：16
    • Memory Size：128G
  • 軟件環(huán)境
    • Spark：spark-2.4.6-bin-hadoop2.7 三個節(jié)點集群
    • yarn V2.10.0：三個節(jié)點集群
    • Nebula Graph V1.1.0：分布式部署，默認(rèn)配置

測試數(shù)據(jù)

  1. 創(chuàng)建圖空間
CREATE SPACE algoTest(partition_num=100, replica_factor=1);
  1. 創(chuàng)建點邊 Schema
CREATE TAG PERSON()
CREATE EDGE FRIEND(likeness double);
  1. 導(dǎo)入數(shù)據(jù)

利用 Exchange 工具將數(shù)據(jù)離線導(dǎo)入 Nebula Graph。

  1. 測試結(jié)果

Spark 任務(wù)的資源分配為 --driver-memory=20G --executor-memory=100G --executor-cores=3

  • PageRank 在一億數(shù)據(jù)集上的執(zhí)行時間為 21min（PageRank 算法執(zhí)行時間）
  • Louvain 在一億數(shù)據(jù)集上的執(zhí)行時間為 1.3h（Reader + Louvain 算法執(zhí)行時間）

如何使用 Nebula Graph 的算法

  1. 下載 nebula-algorithm 項目并打成 jar 包
$ git clone git@github.com:vesoft-inc/nebula-java.git
$ cd nebula-java/tools/nebula-algorithm
$ mvn package -DskipTests
  1. 配置項目中的 src/main/resources/application.conf 
{
  # Spark relation config
  spark: {
    app: {
        # not required, default name is the algorithm that you are going to execute.
        name: PageRank

        # not required
        partitionNum: 12
    }

    master: local

    # not required
    conf: {
        driver-memory: 8g
        executor-memory: 8g
        executor-cores: 1g
        cores-max:6
    }
  }

  # Nebula Graph relation config
  nebula: {
    # metadata server address
    addresses: "127.0.0.1:45500"
    user: root
    pswd: nebula
    space: algoTest
    # partition specified while creating nebula space, if you didn't specified the partition, then it's 100.
    partitionNumber: 100
    # nebula edge type
    labels: ["FRIEND"]

    hasWeight: true
    # if hasWeight is true，then weightCols is required， and weghtCols' order must be corresponding with labels.
    # Noted: the graph algorithm only supports isomorphic graphs,
    #        so the data type of each col in weightCols must be consistent and all numeric types.
    weightCols: [“l(fā)ikeness”]
  }

  algorithm: {
    # the algorithm that you are going to execute，pick one from [pagerank, louvain]
    executeAlgo: louvain
    # algorithm result path
    path: /tmp

    # pagerank parameter
    pagerank: {
        maxIter: 20
        resetProb: 0.15  # default 0.15

    }

    # louvain parameter
    louvain: {
        maxIter: 20
        internalIter: 10
        tol: 0.5
   }
  }
}

  1. 確保用戶環(huán)境已安裝 Spark 并啟動 Spark 服務(wù)

  2. 提交 nebula-algorithm 應(yīng)用程序：

spark-submit --master xxx --class com.vesoft.nebula.tools.algorithm.Main /your-jar-path/nebula-algorithm-1.0.1.jar -p /your-application.conf-path/application.conf

如果你對上述內(nèi)容感興趣，歡迎用 nebula-algorithm 試試^^

References

作者有話說：Hi，我是安祺，Nebula Graph 研發(fā)工程師，如果你對本文有任何疑問，歡迎來論壇和我交流：https://discuss.nebula-graph.com.cn/

推薦閱讀

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容