不同來源的異構(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)重要，圖計(jì)算就是以圖作為數(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è)界極大重視磷斧，圖計(jì)算就是以圖作為數(shù)據(jù)模型來表達(dá)問題并予以解決的過程振愿。圖可以融合多源多類型的數(shù)據(jù)，除了可以展示數(shù)據(jù)靜態(tài)基礎(chǔ)特性之外弛饭，還可通過圖計(jì)算展示隱藏在數(shù)據(jù)之間的圖結(jié)構(gòu)特性和點(diǎn)對關(guān)聯(lián)關(guān)系冕末，成為社交網(wǎng)絡(luò)、推薦系統(tǒng)侣颂、知識圖譜档桃、金融風(fēng)控、網(wǎng)絡(luò)安全憔晒、文本檢索等領(lǐng)域重要的分析手段胳蛮。
二、算法應(yīng)用
為了支撐大規(guī)模圖計(jì)算的業(yè)務(wù)需求丛晌，Nebula Graph 基于 GraphX 提供了 PageRank 和 Louvain 社區(qū)發(fā)現(xiàn)的圖計(jì)算算法仅炊，允許用戶通過提交 Spark 任務(wù)的形式執(zhí)行算法應(yīng)用。此外澎蛛，用戶也可以通過 Spark Connector 編寫 Spark 程序調(diào)用 GraphX 自帶的其他圖算法抚垄，如 LabelPropagation、ConnectedComponent 等。
PageRank
PageRank 是谷歌提出的用于解決鏈接分析中網(wǎng)頁排名問題的算法呆馁，目的是為了對互聯(lián)網(wǎng)中數(shù)以億計(jì)的網(wǎng)頁進(jìn)行排名桐经。
PageRank 簡介
美國斯坦福大學(xué)的 Larry Page 和 Sergey Brin 在研究網(wǎng)頁排序問題時采用學(xué)術(shù)界評判論文重要性的方法，即看論文的引用量以及引用該論文的論文質(zhì)量浙滤，對應(yīng)于網(wǎng)頁的重要性有兩個假設(shè)：
- 數(shù)量假設(shè)：如果一個網(wǎng)頁 A 被很多其他網(wǎng)頁鏈接到阴挣，則該網(wǎng)頁比較重要；
- 質(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ù)用戶通常瀏覽的信息以及停留時間實(shí)現(xiàn)基于用戶的相似度的內(nèi)容推薦；
分析用戶社交影響力
在社交網(wǎng)絡(luò)分析時根據(jù)用戶的 PageRank 值進(jìn)行用戶影響力分析壹粟；
文獻(xiàn)重要性研究
根據(jù)文獻(xiàn)的 PageRank 值評判該文獻(xiàn)的質(zhì)量拜隧，PageRank 算法就是基于評判文獻(xiàn)質(zhì)量的想法來實(shí)現(xiàn)設(shè)計(jì)。
此外 PageRank 在數(shù)據(jù)分析和挖掘中也有很多的應(yīng)用趁仙。
算法思路
GraphX 的 PageRank 算法是基于 Pregel 計(jì)算模型的洪添，該算法流程包括 3 步驟：
- 為圖中每個節(jié)點(diǎn)（網(wǎng)頁）設(shè)置一個同樣的初始 PageRank 值；
- 第一次迭代：沿邊發(fā)送消息雀费，每個節(jié)點(diǎn)收到所有關(guān)聯(lián)邊上對點(diǎn)的信息干奢，得到一個新的 PageRank 值；
- 第二次迭代：用這組新的 PageRank 按不同算法模式對應(yīng)的公式形成節(jié)點(diǎn)自己新的 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é)點(diǎn)加入到某一社區(qū)中會使得該社區(qū)的模塊度相比其他社區(qū)有最大程度的增加，則該節(jié)點(diǎn)就應(yīng)當(dāng)屬于該社區(qū)逛漫。如果加入其它社區(qū)后沒有使其模塊度增加黑低，則留在自己當(dāng)前社區(qū)中。
模塊度
模塊度公式
模塊度 Q 的物理意義：社區(qū)內(nèi)節(jié)點(diǎn)的連邊數(shù)與隨機(jī)情況下的邊數(shù)之差酌毡，定義函數(shù)如下：
其中
：節(jié)點(diǎn) i 和節(jié)點(diǎn) j 之間邊的權(quán)重
：所有與節(jié)點(diǎn) i 相連的邊的權(quán)重之和
模塊度公式變形
在此公式中克握，只有節(jié)點(diǎn) i 和節(jié)點(diǎn) j 屬于同一社區(qū)，公式才有意義枷踏，所以該公式是衡量的某一社區(qū)內(nèi)的緊密度菩暗。對于該公式的簡化變形如下：
表示： 社區(qū) c 內(nèi)的邊的權(quán)重之和
表示： 所有與社區(qū) c 內(nèi)節(jié)點(diǎn)相連的邊的權(quán)重之和（因?yàn)?i 屬于社區(qū) c）包括社區(qū)內(nèi)節(jié)點(diǎn)與節(jié)點(diǎn) i 的邊和社區(qū)外節(jié)點(diǎn)與節(jié)點(diǎn) i 的邊。
求解模塊度變化
在 Louvain 算法中不需要求每個社區(qū)具體的模塊度旷坦，只需要比較社區(qū)中加入某個節(jié)點(diǎn)之后的模塊度變化，所以需要求解 △Q佑稠。
將節(jié)點(diǎn) i 分配到某一社區(qū)中秒梅，社區(qū)的模塊度變化為：
其中
對于社區(qū)內(nèi)所有的頂點(diǎn) i舌胶，每條邊其實(shí)被計(jì)算了兩次）
故實(shí)現(xiàn)算法時只需求
即可捆蜀。
Louvain 應(yīng)用場景
- 金融風(fēng)控
在金融風(fēng)控場景中，可以根據(jù)用戶行為特征進(jìn)行團(tuán)伙識別幔嫂；
- 社交網(wǎng)絡(luò)
可以基于網(wǎng)絡(luò)關(guān)系中點(diǎ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é)點(diǎn)咐刨，通過比較節(jié)點(diǎn)給每個鄰居社區(qū)帶來的模塊度的變化昙衅，將單個節(jié)點(diǎn)加入到能夠使 Modularity 模塊度有最大增量的社區(qū)中。
（比如節(jié)點(diǎn) v 分別加入到社區(qū) A定鸟、B而涉、C 中，使得三個社區(qū)的模塊度增量為-1联予， 1啼县， 2， 則節(jié)點(diǎn) v 最終應(yīng)該加入到社區(qū) C 中）
階段二：對第一階段進(jìn)行處理沸久，將屬于同一社區(qū)的頂點(diǎn)合并為一個大的超點(diǎn)重新構(gòu)造網(wǎng)絡(luò)圖季眷，即一個社區(qū)作為圖的一個新的節(jié)點(diǎn)。此時兩個超點(diǎn)之間邊的權(quán)重是兩個超點(diǎn)內(nèi)所有原始頂點(diǎn)之間相連的邊權(quán)重之和卷胯，即兩個社區(qū)之間的邊權(quán)重之和子刮。
下面是對第一二階段的實(shí)例介紹。
?
第一階段遍歷圖中節(jié)點(diǎn)加入到其所屬社區(qū)中窑睁，得到中間的圖挺峡，形成四個社區(qū)；
第二節(jié)點(diǎn)對社區(qū)內(nèi)的節(jié)點(diǎn)進(jìn)行合并成一個超級節(jié)點(diǎn)担钮，社區(qū)節(jié)點(diǎn)有自連邊橱赠，其權(quán)重為社區(qū)內(nèi)部所有節(jié)點(diǎn)間相連的邊的權(quán)重之和的 2 倍，社區(qū)之間的邊為兩個社區(qū)間頂點(diǎn)跨社區(qū)相連的邊的權(quán)重之和箫津，如紅色社區(qū)和淺綠色社區(qū)之間通過（8,11）狭姨、（10吓著，11）、（10,13）相連送挑，所以兩個社區(qū)之間邊的權(quán)重為 3绑莺。
注：社區(qū)內(nèi)的權(quán)重為所有內(nèi)部結(jié)點(diǎn)之間邊權(quán)重的兩倍，因?yàn)?Kin 的概念是社區(qū)內(nèi)所有節(jié)點(diǎn)與節(jié)點(diǎn) i 的連邊和惕耕，在計(jì)算某一社區(qū)的 Kin 時纺裁，實(shí)際上每條邊都被其兩端的頂點(diǎn)計(jì)算了一次，一共被計(jì)算了兩次司澎。
整個 Louvain 算法就是不斷迭代第一階段和第二階段欺缘，直到算法穩(wěn)定（圖的模塊度不再變化）或者到達(dá)最大迭代次數(shù)。
三挤安、算法實(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é)點(diǎn)集群
- yarn V2.10.0：三個節(jié)點(diǎn)集群
- Nebula Graph V1.1.0：分布式部署，默認(rèn)配置
測試數(shù)據(jù)
- 創(chuàng)建圖空間
CREATE SPACE algoTest(partition_num=100, replica_factor=1);
- 創(chuàng)建點(diǎn)邊 Schema
CREATE TAG PERSON()
CREATE EDGE FRIEND(likeness double);
- 導(dǎo)入數(shù)據(jù)
利用 Exchange 工具將數(shù)據(jù)離線導(dǎo)入 Nebula Graph蛤铜。
- 測試結(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 的算法
- 下載 nebula-algorithm 項(xiàng)目并打成 jar 包
$ git clone git@github.com:vesoft-inc/nebula-java.git
$ cd nebula-java/tools/nebula-algorithm
$ mvn package -DskipTests
- 配置項(xiàng)目中的
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
}
}
}
確保用戶環(huán)境已安裝 Spark 并啟動 Spark 服務(wù)
提交 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
- Nebula Graph：https://github.com/vesoft-inc/nebula
- GraphX：https://github.com/apache/spark/tree/master/graphx
- Spark-connector：https://github.com/vesoft-inc/nebula-java/tree/master/tools/nebula-spark
- Exchange：https://github.com/vesoft-inc/nebula-java/blob/master/doc/tools/exchange/ex-ug-toc.md
- nebula-algorithm：https://github.com/vesoft-inc/nebula-java/tree/master/tools/nebula-algorithm
作者有話說：Hi，我是安祺穆刻，Nebula Graph 研發(fā)工程師置尔，如果你對本文有任何疑問，歡迎來論壇和我交流：https://discuss.nebula-graph.com.cn/
