面向數(shù)據(jù)高交互任務(wù)的分布式圖計算方案的設(shè)計與實現(xiàn)

俞山青，王甬琪，崔文豪，孟櫟均，李 冰，傅晨波

1(浙江工業(yè)大學(xué) 信息工程學(xué)院，杭州 310000) 2(杭州中奧科技有限公司，杭州 310000)

1 引 言

許多領(lǐng)域中數(shù)據(jù)間的復(fù)雜關(guān)系，例如金融交易、社交網(wǎng)絡(luò)、電子商務(wù)等等，均可以使用圖這種數(shù)據(jù)結(jié)構(gòu)進行抽象化簡，進而為相關(guān)問題的研究提供巨大的便利.例如Google通過網(wǎng)頁間超鏈接關(guān)系設(shè)計了PageRank[1]算法對網(wǎng)頁進行排序，優(yōu)化搜索引擎；Facebook通過對用戶及其社交關(guān)系進行建模研究，提供更好的社區(qū)服務(wù)；Amazon通過用戶及其購物行為關(guān)系等信息構(gòu)建推薦系統(tǒng)，引導(dǎo)用戶購物行為[2]等.在相關(guān)問題的研究過程中，圖計算往往是必不可少的，而對于其中較大規(guī)模圖數(shù)據(jù)的復(fù)雜計算任務(wù)，集中式計算方式難以達到預(yù)期效果，而現(xiàn)有的分布式計算方法又會由于過多的數(shù)據(jù)傳輸產(chǎn)生大量時耗，計算效率較低.

基于上述情況，本文提出了一種面向數(shù)據(jù)高交互任務(wù)的分布式圖計算方案.該方案中系統(tǒng)由任務(wù)管理中心、數(shù)據(jù)中心與計算節(jié)點組成.首先，任務(wù)管理中心分割計算任務(wù)并創(chuàng)建任務(wù)狀態(tài)表，將子任務(wù)分配給計算節(jié)點執(zhí)行，同時將狀態(tài)表上傳至數(shù)據(jù)中心.其次，計算節(jié)點從數(shù)據(jù)中心獲取計算所需數(shù)據(jù)后執(zhí)行計算任務(wù)，并將計算結(jié)果上傳至數(shù)據(jù)中心.在此過程中，任務(wù)管理中心通過任務(wù)狀態(tài)表定時檢測所有子任務(wù)是否已完成.最后，當(dāng)檢測到所有任務(wù)完成后，任務(wù)管理中心將獲取所有子任務(wù)中間計算結(jié)果，將其進行整合匯總后上傳至數(shù)據(jù)中心存儲.在上述過程中，任務(wù)分割過程采用均勻分割策略，使每一子任務(wù)計算用時趨于一致以避免各計算節(jié)點負載不均衡；任務(wù)分發(fā)過程使用現(xiàn)有的任務(wù)分發(fā)框架實現(xiàn)，并由此實現(xiàn)任務(wù)的分布式計算；數(shù)據(jù)中心功能由數(shù)據(jù)庫實現(xiàn)，該方式可以在任務(wù)異常中斷后保留已完成的任務(wù)計算結(jié)果及任務(wù)狀態(tài)，且可以通過使用特定的文件存儲機制降低數(shù)據(jù)庫的讀表開銷，通過文件壓縮降低數(shù)據(jù)傳輸量；各計算節(jié)點執(zhí)行任務(wù)時可獲取完整圖數(shù)據(jù)，從而避免了現(xiàn)有分布式圖計算方案中各節(jié)點間數(shù)據(jù)頻繁傳輸帶來的時耗.

此外，本文選取節(jié)點中心性作為計算目標，實現(xiàn)了上述分布式圖計算方案并進行相關(guān)實驗.節(jié)點中心性具體包括度中心性、接近中心性與介數(shù)中心性.選擇節(jié)點中心性作為計算目標的原因在于：1)節(jié)點中心性可以表示圖模型中各節(jié)點的影響力、控制力、流行性等，是一個重要的計算指標；2)該計算任務(wù)屬于我們的目標任務(wù)類型：中心性計算，尤其是介數(shù)中心性的計算，計算復(fù)雜度較高且需要使用到全圖數(shù)據(jù).介數(shù)中心性計算的一般方法計算復(fù)雜度為O(n3)，其中n為節(jié)點數(shù)，當(dāng)圖數(shù)據(jù)較大時，集中式計算方法難以實現(xiàn)高效運算.而該計算過程又需要頻繁使用全圖數(shù)據(jù)，現(xiàn)有分布式圖計算方案會產(chǎn)生大量的數(shù)據(jù)交互時耗.本文主要貢獻點如下：

1)提出了一種面向數(shù)據(jù)高交互任務(wù)的分布式圖計算方案，為此類圖計算任務(wù)提供一種可選的高效計算途徑；

2)以節(jié)點中心性為計算目標實現(xiàn)了本文所提出的分布式圖計算方案，并通過實驗驗證本文設(shè)計方案在目標任務(wù)類型上具有優(yōu)良的計算性能.

2 相關(guān)工作

2.1 分布式圖計算系統(tǒng)

當(dāng)前大規(guī)模分布式圖計算系統(tǒng)按照其計算模型主要可分為基于MapReduce模型的計算系統(tǒng)、基于BSP模型的計算系統(tǒng)、基于GAS模型的計算系統(tǒng)等幾大類[3].本小節(jié)將簡要介紹其中最具代表性的幾種計算模型.

MapReduce[4]是并行處理大規(guī)模數(shù)據(jù)的分布式計算平臺，最早由Google于2004年提出.該模型首先對數(shù)據(jù)進行切片，將計算任務(wù)分配到每一個切片上.切片后的處理過程分為Map與Reduce兩個階段.MapReduce模型的優(yōu)勢在于使用簡單，只需定義Map與Reduce函數(shù)，且其對大數(shù)據(jù)的處理能力較強.但由于該模型切片一般較大，處理過程又分為兩個階段，對算法的迭代運算帶來較大困難，計算過程中頻繁讀寫磁盤數(shù)據(jù)又降低了計算效率.研究人員提出了一些基于MapReduce的優(yōu)化模型，例如Haloop[5]、Twister[6]等，用于彌補其不足，但仍然難以勝任大規(guī)模圖計算任務(wù).

BSP(Bulk Synchronous Parallel)[7]整體同步并行模型是一種適用于迭代計算的基于消息通信的并行計算模型，由Valiant于1990年提出.該模型將計算任務(wù)分解為一系列的迭代運算，每次迭代運算又分為本地計算、消息通信和路障同步三個階段.在BSP基礎(chǔ)上，Google于2010年提出“像節(jié)點一樣思考”的分布式圖計算模型Pregel[8].此類模型解決了MapReduce不善于做迭代計算的問題，使得計算效能得到提升.但由于存在著路障同步，各節(jié)點需要等待所有節(jié)點完成當(dāng)前階段后才能進入下一階段.Giraph[9]，GPS[10]，Hama[11]等在Pregel的基礎(chǔ)上實現(xiàn)了一定的改進，用以提升計算性能.

GAS(Gather-Apply-Scatter)模型由GraphLab[12]項目組提出.該模型處理流程類似于BSP模型，又將節(jié)點更新函數(shù)細分為收集、應(yīng)用和分散三個階段.GAS模型通過將節(jié)點更新函數(shù)細分化，使得計算節(jié)點間在運算時不需要時刻保持路障同步，大大減少了各節(jié)點的閑置時間，提升了系統(tǒng)的計算性能.但當(dāng)各節(jié)點由于軟硬件原因等使得迭代輪數(shù)相差較大時，最終計算結(jié)果可能會不正確，需要引入額外的機制保證系統(tǒng)運算的準確性.在基于GAS模型的計算系統(tǒng)中，PowerGraph[13]首次使用節(jié)點分割策略替代邊分割策略，提升了系統(tǒng)的并發(fā)處理能力.PowerSwitch[14]、BiGraph[15]等均為在GraphLab與PowerGraph之上改進的計算模型，在不同層面上得到一定的提升.

除此之外，GraphX[16]是基于BSP與GAS的混合計算模型，可理解為Pregel與GraphLab的重寫與優(yōu)化，它結(jié)合了兩者的優(yōu)點，提升了計算性能.GraphX底層基于分布式計算引擎Spark，可部署于Hadoop分布式大數(shù)據(jù)處理平臺，為圖處理提供了巨大的便利.基于上述原因，本文選用GraphX作為實驗的參照對象.

2.2 中心性計算

本文選取了中心性指標中最具代表性的三種作為計算目標測試本文所提出的系統(tǒng)，分別為度中心性、接近中心性與介數(shù)中心性.本小節(jié)簡要介紹其概念及計算方式.

度中心性(Degree Centrality)是度量網(wǎng)絡(luò)中節(jié)點中心性最直接的指標，其值直接決定于與其相鄰的節(jié)點數(shù).度中心性越大，表示相鄰節(jié)點越多，該節(jié)點越重要.其歸一化后計算公式為：

(1)

其中cD(i)為節(jié)點i的度，n為網(wǎng)絡(luò)的總節(jié)點數(shù).

接近中心性(Closeness Centrality)是用于度量節(jié)點與其它節(jié)點接近程度的指標.接近中心性越大，表示該節(jié)點與其它節(jié)點的交互越迅速.其歸一化后計算公式為：

(2)

其中d(i,j)為節(jié)點i與節(jié)點j之間的最短距離，n為網(wǎng)絡(luò)的總節(jié)點數(shù).

介數(shù)中心性(Betweenness Centrality)取決于一個節(jié)點擔(dān)任其它任意兩節(jié)點間最短路徑橋梁的次數(shù).介數(shù)中心性越大，表示該節(jié)點在節(jié)點信息傳遞過程中的中介承載程度越高，起重要橋梁作用.其標準化后計算公式為：

(3)

其中V為所有節(jié)點集，s與t為節(jié)點集中與i相異的任意兩節(jié)點，σst為節(jié)點s與節(jié)點t之間的最短路徑的條數(shù)，σst(i)為節(jié)點i經(jīng)過的節(jié)點s與節(jié)點t間最短路徑的條數(shù)，n為網(wǎng)絡(luò)的總節(jié)點數(shù).

上述中心性計算公式可同時實現(xiàn)對有向圖、無向圖、有權(quán)圖與無權(quán)圖的中心性計算，而在各公式符號的計算中存在著一些差異：有向圖的度中心性需要依據(jù)邊的方向，分別基于出度與入度計算；有向圖接近中心性、介數(shù)中心性中最短距離、最短路徑的計算應(yīng)考慮邊的方向，即路徑必須沿邊的正向；有權(quán)圖的中心性計算公式中的度、最短距離、最短路徑均應(yīng)結(jié)合邊的權(quán)重進行計算等.

3 方案設(shè)計

本文提出的分布式圖計算方案整體設(shè)計如圖1所示.該設(shè)計分為三個部分，分別為任務(wù)管理中心、數(shù)據(jù)中心與計算節(jié)點，其中計算節(jié)點可按需求進行擴展.在執(zhí)行計算任務(wù)時，首先由任務(wù)管理中心對任務(wù)進行分割，并同時創(chuàng)建任務(wù)狀態(tài)表傳輸至數(shù)據(jù)中心存儲.而后任務(wù)管理中心將分割后子任務(wù)分發(fā)給計算節(jié)點執(zhí)行計算，更新狀態(tài)表中任務(wù)狀態(tài)為執(zhí)行中.計算節(jié)點完成計算任務(wù)后將結(jié)果傳輸至數(shù)據(jù)中心存儲，更新狀態(tài)表中任務(wù)狀態(tài)為已完成.在上述過程中，任務(wù)管理中心通過任務(wù)狀態(tài)表定時檢測任務(wù)完成情況.當(dāng)檢測到所有子任務(wù)均執(zhí)行完成后，任務(wù)管理中心從數(shù)據(jù)中心獲取所有計算子任務(wù)的中間計算結(jié)果，并對其進行整合匯總后傳輸至數(shù)據(jù)中心存儲，完成本次計算任務(wù).

圖1 方案整體設(shè)計Fig.1 Overall design of the scheme

具體地，在任務(wù)分割過程中，本文方案采用均勻分割策略.該策略可使得各計算節(jié)點執(zhí)行子任務(wù)時用時趨于一致，從而實現(xiàn)負載均衡，避免任務(wù)將完成時有計算節(jié)點處于閑置狀態(tài)而降低計算效率.在任務(wù)分發(fā)過程中，本文方案使用現(xiàn)有的任務(wù)分發(fā)系統(tǒng)框架，由此實現(xiàn)任務(wù)的分布式計算.

方案中選用數(shù)據(jù)庫作為數(shù)據(jù)中心，其優(yōu)點在于：將數(shù)據(jù)存儲于數(shù)據(jù)庫中可以有效避免任務(wù)非正常中斷時計算結(jié)果及任務(wù)狀態(tài)表的丟失；通過數(shù)據(jù)庫存儲的方式，極大地方便了各計算節(jié)點對數(shù)據(jù)的存取，也方便了計算結(jié)果的獲取與管理.考慮到使用數(shù)據(jù)庫存儲管理數(shù)據(jù)，會產(chǎn)生額外的讀寫開銷，本文方案對數(shù)據(jù)進行了整體存儲、整體讀寫的設(shè)計，相較于數(shù)據(jù)庫中數(shù)據(jù)記錄的逐條讀寫方式，具有更低的讀寫開銷；同時通過對整體存儲的數(shù)據(jù)進行壓縮，降低了數(shù)據(jù)的傳輸量.

計算節(jié)點在執(zhí)行計算子任務(wù)時，從數(shù)據(jù)中心獲取全圖數(shù)據(jù).采用數(shù)據(jù)分布式存儲的分布式圖計算方法在計算數(shù)據(jù)高交互計算任務(wù)時，會在各計算節(jié)點間產(chǎn)生大量的數(shù)據(jù)傳輸時耗，本文方案采取計算節(jié)點保留整體圖數(shù)據(jù)的設(shè)計，提升了計算性能.

4 具體實現(xiàn)

本節(jié)將基于節(jié)點中心性計算任務(wù)，具體實現(xiàn)本文所設(shè)計的方案，并將其用于測試本方案的有效性.

4.1 任務(wù)管理中心具體實現(xiàn)

本文選取任務(wù)分發(fā)框架Gearman(1)https：//gearman.org/實現(xiàn)任務(wù)的分發(fā)功能，其原因在于：1)Gearman可以有效實現(xiàn)任務(wù)的分布式并行計算；2)Gearman具有一定負載均衡的能力；3)Gearman可以實現(xiàn)多種程序語言之間的溝通，方便程序的實現(xiàn).

任務(wù)管理中心主要負責(zé)任務(wù)的分割、分發(fā)、定時檢測及最終計算結(jié)果的匯總，其具體流程如圖2所示.值得注意的是，在任務(wù)分割的過程中，由于不同節(jié)點的中心性計算時耗不一且難以估計，具體實現(xiàn)過程中基于節(jié)點數(shù)進行均勻分割，使得各計算子任務(wù)時耗盡可能趨于一致，避免負載不均衡造成時間損耗.任務(wù)分割完成后創(chuàng)建任務(wù)狀態(tài)表上傳至數(shù)據(jù)中心，用于后續(xù)的定時檢測功能的實現(xiàn).任務(wù)分發(fā)過程通過Gearman實現(xiàn).定時檢測過程中，查看任務(wù)狀態(tài)表中任務(wù)狀態(tài)是否全部為已完成，若均已完成則進入最終計算結(jié)果的匯總過程.由于三種中心性中，度中心性及接近中心性計算結(jié)果已為最終計算結(jié)果，不需要進行整合匯總，該過程僅對介數(shù)中心性實行，即從數(shù)據(jù)中心中下載中間計算結(jié)果至任務(wù)管理中心實現(xiàn)整合匯總后，重新上傳數(shù)據(jù)中心存儲.

圖2 任務(wù)管理中心流程圖Fig.2 Flow chart on tasks management center

此外，由于度中心性的計算較為簡單，對其使用分布式計算方案會由于數(shù)據(jù)傳輸?shù)臅r耗而降低整體計算效率.本文直接在任務(wù)管理中心中完成其計算，即任務(wù)中心也可直接完成簡單計算任務(wù)以提升整體計算效率.

4.2 數(shù)據(jù)中心具體實現(xiàn)

本文選取MongoDB(2)https://www.mongodb.com/數(shù)據(jù)庫作為數(shù)據(jù)中心，其原因在于：

1)MongoDB數(shù)據(jù)庫為眾多程序語言提供了接口，使用方便；2)MongoDB數(shù)據(jù)庫中可使用GirdFS文件存儲機制，可以實現(xiàn)數(shù)據(jù)以文檔形式進行整體傳輸，降低數(shù)據(jù)庫的讀寫開銷.

數(shù)據(jù)中心主要負責(zé)數(shù)據(jù)的存儲與傳輸.在數(shù)據(jù)存儲功能中，MongoDB數(shù)據(jù)庫主要實現(xiàn)了圖數(shù)據(jù)、任務(wù)狀態(tài)表、子任務(wù)計算結(jié)果及最終任務(wù)結(jié)果的存儲.其中圖數(shù)據(jù)用于各計算節(jié)點執(zhí)行任務(wù)的過程；任務(wù)狀態(tài)表用于任務(wù)管理中心的定時檢測；子任務(wù)計算結(jié)果來自于各計算節(jié)點，并用于計算結(jié)果的整合匯總，即最終任務(wù)結(jié)果.具體地，數(shù)據(jù)庫中設(shè)計了四張數(shù)據(jù)表，分別為任務(wù)狀態(tài)表、度中心性表、接近中心性表與介數(shù)中心性表.其中任務(wù)狀態(tài)表中具體字段及相關(guān)信息如表1所示；而度中心性表、接近中心性表與介數(shù)中心性表由于字段及相關(guān)信息基本一致，其主要設(shè)置可同時參照表2.此外，針對有向圖的中心性計算，在度中心性表中存在出度、入度兩個字段未在表中給出.

表1 數(shù)據(jù)中心任務(wù)狀態(tài)表Table 1 Task status table in data center

表2 數(shù)據(jù)中心中心性表Table 2 Centrality tables in data cente

在數(shù)據(jù)傳輸功能上，方案實例使用GirdFS文件存儲機制：相較于對數(shù)據(jù)庫中的記錄進行逐條讀寫，基于文件存儲機制的數(shù)據(jù)整體傳輸方式可以在一定程度上減少讀寫開銷.此外，使用Google開發(fā)的壓縮庫Snappy(3)https：//github.com/google/snappy對文件進行壓縮，以減少數(shù)據(jù)傳輸量：Snappy壓縮庫特點在于能提供快速解壓縮的同時具有較低的壓縮率，性能均衡.官方文檔顯示，該壓縮庫在64位Core i7單核模式下，具有超過250MB/s的壓縮速率與超過500MB/s的解壓縮速率.同時，使用Snappy對實驗中原數(shù)據(jù)大小為91.3MB的web-Google數(shù)據(jù)集進行壓縮后文件大小降為35.5MB.本文通過上述設(shè)計優(yōu)化數(shù)據(jù)傳輸過程.

4.3 計算節(jié)點具體實現(xiàn)

本文方案中計算節(jié)點主要負責(zé)計算子任務(wù)的執(zhí)行及結(jié)果的上傳.具體地，計算節(jié)點連接到任務(wù)分發(fā)框架Gearman后，從中獲取計算任務(wù)及MongoDB數(shù)據(jù)庫端口，并由此獲取計算數(shù)據(jù).計算節(jié)點執(zhí)行接近中心性及介數(shù)中心性分量的計算程序.待執(zhí)行完成后，將計算結(jié)果上傳至數(shù)據(jù)庫，等待最終的結(jié)果匯總.其具體流程如圖3所示.

圖3 計算節(jié)點執(zhí)行流程圖Fig.3 Flow chart on computing nodes

5 實驗結(jié)果

5.1 實驗環(huán)境

本文方案實例部署在由5臺相同配置服務(wù)器組成的內(nèi)網(wǎng)集群，其CPU型號為Intel(R)Xeon(R)E5-2650 v4，主頻2.20GHz，核數(shù)8個，內(nèi)存8G.

實驗中五臺服務(wù)器均作為計算節(jié)點.在此基礎(chǔ)上，選取其中兩臺服務(wù)器分別部署任務(wù)管理中心與數(shù)據(jù)中心.同一臺服務(wù)器同時作為計算節(jié)點與任務(wù)管理中心或數(shù)據(jù)中心可能會影響程序的運行性能，但這種方式計算性能高于僅將3臺服務(wù)器作為計算節(jié)點.

此外，實驗選取幾種單機下集中式圖計算工具與分布式圖計算工具GraphX作為本文設(shè)計系統(tǒng)的參照對象.實驗環(huán)境分別為單臺服務(wù)器與五臺服務(wù)器組成的Spark內(nèi)網(wǎng)集群.

5.2 數(shù)據(jù)集

實驗中使用的數(shù)據(jù)集來自美國斯坦福大學(xué)和德國科布倫茨-蘭道大學(xué)的開源網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站.數(shù)據(jù)集的說明如表3所示.

表3的數(shù)據(jù)集源數(shù)據(jù)存儲格式不一，實驗前需進行預(yù)處理，使其具有相同格式.此外，實驗中通過兩條有向邊來表示無向邊；通過對無權(quán)圖數(shù)據(jù)集上對每條邊做1-10整數(shù)的隨機賦權(quán)，作為有權(quán)圖進行測試實驗，并在相應(yīng)文件名后添加“-w”區(qū)分于無權(quán)圖數(shù)據(jù)集.

表3 實驗數(shù)據(jù)集說明Table 3 Description on experimental data sets

5.3 參照方案

在本文實驗中，選擇幾種常用的集中式圖計算工具igraph(4)https：//igraph.org/、Gephi(5)https：//gephi.org/、NetworkX(6)http：//networkx.github.io/及Spark平臺下的分布式圖計算工具GraphX作為參照對象.各方案所使用的程序語言及介數(shù)中心性計算的近似算法復(fù)雜度等相關(guān)信息如表4所示.其中m為邊數(shù)，n為節(jié)點數(shù).

表4 各方案相關(guān)信息Table 4 Related information of each scheme

表4中除NetworkX外的參照方案的程序語言效率及算法復(fù)雜度均與本方案相近或是優(yōu)于本方案.其中NetworkX方案主要用于保證本文方案計算結(jié)果與直接通過定義計算的方案結(jié)果一致.GraphX方案采用基于DFS加速的分布式介數(shù)中心性算法[17]實現(xiàn)優(yōu)化.

5.4 實驗相關(guān)信息與結(jié)果分析

本小節(jié)首先介紹具體實驗過程中計算任務(wù)分割及任務(wù)分發(fā)情況，其次通過計算本文方案計算結(jié)果與集中式工具結(jié)果之間的相關(guān)系數(shù)及各自L2范數(shù)，驗證本方案及方案實例計算結(jié)果的正確性，最后通過比較各種方案對相同計算任務(wù)的計算用時，驗證本文方案對此類任務(wù)具有優(yōu)良的計算效率.

在實驗過程中，任務(wù)分割采用基于節(jié)點數(shù)的均勻分割策略，分割后任務(wù)由Gearman任務(wù)分發(fā)系統(tǒng)實現(xiàn)分配.在一次Epinions數(shù)據(jù)集的中心性計算實驗中，分割后的子任務(wù)及分配情況如表5所示.任務(wù)數(shù)依據(jù)計算節(jié)點的整數(shù)倍被設(shè)置為10，每個任務(wù)所需計算的節(jié)點數(shù)均勻分配，計算節(jié)點完成當(dāng)前任務(wù)的計算后發(fā)送請求并開始下一個任務(wù)的計算.

表5 任務(wù)分割及分發(fā)實例Table 5 Example of task split and tasks distribute

在計算結(jié)果正確性的驗證實驗中，本文以email-Enron數(shù)據(jù)集的介數(shù)中心性為例，計算本文提出方案與常用集中式計算工具計算結(jié)果之間的皮爾森(Person)、斯皮爾曼(Spearman)和肯德爾(Kendall)相關(guān)系數(shù)，用以說明兩類方法變化趨勢一致性，實驗中數(shù)據(jù)集又分為無權(quán)圖數(shù)據(jù)與有權(quán)圖數(shù)據(jù).此外，還對各種工具及分布式計算方案的實驗結(jié)果計算各自的L2范數(shù)，用以確保計算結(jié)果數(shù)值一致性.實驗結(jié)果如表6-表8所示.其中表6為本方案與集中式圖計算方案在無權(quán)圖上計算結(jié)果的相關(guān)系數(shù)，表7為兩者在有權(quán)圖上的相關(guān)系數(shù)，表8為各方法計算結(jié)果的L2范數(shù).表中“/”表示不支持計算.

表6 本文方案與各方案在無權(quán)圖計算中的相關(guān)系數(shù)Table 6 Correlation coefficient on unweighted graphcalculation between our scheme and otrher schemes

表7 本文方案與各方案在有權(quán)圖計算中的相關(guān)系數(shù)Table 7 Correlation coefficient on weighted graphcalculation between our scheme and otrher schemes

表8 各方案計算結(jié)果L2范數(shù)Table 8 L2 norm on calculation results of each scheme

由表中數(shù)據(jù)可以得知，本文方案的運算結(jié)果與常用集中式計算工具的運算結(jié)果之間相關(guān)系數(shù)約等于1，即兩者的變化趨勢基本一致.此外，各方案計算結(jié)果的L2范數(shù)基本一致，說明了本文方案計算數(shù)值能與常用集中式計算工具保持一致.本方案的計算正確性基本可以保證.在實際結(jié)果中，本文方案計算結(jié)果在小數(shù)點后十一位均可與常用集中式計算工具保持一致.

上述實驗結(jié)果已驗證本文提出方案計算結(jié)果的正確性，在此基礎(chǔ)上進行各方案計算效率的比較實驗.實驗中使用選取的3種集中式計算工具、分布式圖計算系統(tǒng)Graph X與本文設(shè)計方案分別在7個數(shù)據(jù)集上計算3種節(jié)點中心性，數(shù)據(jù)集又各自分為有權(quán)圖數(shù)據(jù)與無權(quán)圖數(shù)據(jù).實驗結(jié)果各方案時耗如表9與表10所示.Gephi工具不支持有權(quán)圖的計算，故表10中不含該列.表中“-”表示計算用時超過12小時.

表9 無權(quán)圖中各方案計算時耗Table 9 Time consumption on unweighted graph computation of each scheme

表10 有權(quán)圖中各方案計算時耗Table 10 Time consumption on weighted graph computation of each scheme

由表9和表10中各方案計算時耗數(shù)據(jù)中可以得知，本文提出的方案計算用時遠小于常用的集中式圖計算工具，而基于GraphX的分布式圖計算方案計算用時遠大于常用的集中式圖計算工具.本文方案相較于集中式圖計算工具與分布式圖計算系統(tǒng)GraphX，都具有更高的計算效率.

兩種分布式方案在計算效率上存在巨大差異，其原因在于它們并行計算的原理不同.基于GraphX的分布式計算方法對圖數(shù)據(jù)進行了圖分割，數(shù)據(jù)分布在各個計算節(jié)點上，當(dāng)計算介數(shù)中心性這類需要全圖節(jié)點信息的目標時，需要在計算節(jié)點間頻繁傳遞數(shù)據(jù)，從而產(chǎn)生大量額外開銷，降低計算效率.該分布式方法適用于各計算節(jié)點數(shù)據(jù)間依賴程度不高的任務(wù).而本文方案不對圖數(shù)據(jù)進行分割，而是通過直接對任務(wù)進行分割實現(xiàn)分布式計算，這種方式大大減少了數(shù)據(jù)交互時耗，適用于數(shù)據(jù)高交互的圖計算任務(wù).

6 結(jié) 語

本文設(shè)計并實現(xiàn)了一種面向數(shù)據(jù)高交互任務(wù)的分布式圖計算方案.該方案由任務(wù)管理中心、數(shù)據(jù)中心及計算節(jié)點組成.其中心性計算實例驗證了本方案計算結(jié)果的正確性，并且在目標任務(wù)上具有優(yōu)良性能，為此類計算任務(wù)提供了一種可選的計算方案.