張瑞　王三福

摘 要：文章結(jié)合GraphLab大數(shù)據(jù)框架應(yīng)用技術(shù)最新的發(fā)展，全面分析研究了該技術(shù)在復(fù)雜網(wǎng)絡(luò)研究中的具體應(yīng)用。包括GraphLab并行框架并將其應(yīng)用在復(fù)雜網(wǎng)絡(luò)度計算、最短路徑及聚集系數(shù)等計算方面，同時，還分析了處理該類型大數(shù)據(jù)時可能遭遇的問題。為搭建高效合理的復(fù)雜網(wǎng)絡(luò)大數(shù)據(jù)處理計算提供了一種新思路，進而提升復(fù)雜網(wǎng)絡(luò)研究的整體水平。

關(guān)鍵詞：GraphLab；復(fù)雜網(wǎng)絡(luò)；度計算；最短路徑；聚集系數(shù)

全球互聯(lián)網(wǎng)數(shù)據(jù)中心報告指出，2013年全球數(shù)據(jù)量為4.4ZB，2014年全球數(shù)據(jù)總量在6.2ZB左右，2015年全球數(shù)據(jù)總量在8.6ZB左右，2016年將在12ZB左右。在未來的幾年時間內(nèi)，全球數(shù)據(jù)流量將實現(xiàn)跨越式增長。到2020年，全球數(shù)據(jù)總量將增至40ZB。另外，大數(shù)據(jù)是由非結(jié)構(gòu)化的數(shù)據(jù)與結(jié)構(gòu)化數(shù)據(jù)構(gòu)成的。其中，非結(jié)構(gòu)化的占比最大，達到了85%。截至目前，非結(jié)構(gòu)化數(shù)據(jù)的一般性特征、個體表現(xiàn)及其基本原理還未明朗化。為此，在后續(xù)研究過程中，應(yīng)綜合運用社會學(xué)、數(shù)學(xué)、管理科學(xué)等諸多學(xué)科進行探討。復(fù)雜網(wǎng)絡(luò)理論是以網(wǎng)絡(luò)為研究對象的學(xué)科，是一種不同研究對象的統(tǒng)一抽象的表達方式，它迎合了目前大數(shù)據(jù)處理的機遇與挑戰(zhàn)，開辟了一種新科學(xué)方法。

1 GraphLab大數(shù)據(jù)框架

大數(shù)據(jù)是這幾年科技和應(yīng)用領(lǐng)域炙手可熱的話題，而GraphLab又是大數(shù)據(jù)非結(jié)構(gòu)網(wǎng)絡(luò)研究中最活躍的技術(shù)，該技術(shù)比較新，許多應(yīng)用還處在探索階段。利用該計算框架，我們寫的程序可以充分利用大量資源，而不需要關(guān)心分布式系統(tǒng)的實現(xiàn)細節(jié)。GraphLab將數(shù)據(jù)抽象成Graph結(jié)構(gòu)，將算法的執(zhí)行過程抽象成Gather、Apply、Scatter三個步驟。其并行的核心思想是對頂點的切分，以下面的例子作為一個說明。如圖1所示，首先，要求率先對V0鄰接頂點實施求和計算，在串行實現(xiàn)中，依靠V0遍歷其全部鄰接點，緊接著實施累積求和。GraphLab先切分頂點V0，緊接著在兩臺處理器上分別部署V0的邊關(guān)系及與之相對應(yīng)的鄰接點，同時實施部分求和運算，再由mirror頂點與master頂點的通信負責做好最終的計算工作。

圖1 Graph對并行思想

邊是機器學(xué)習(xí)算法中充分反映數(shù)據(jù)依賴性的重要形式，頂點是大數(shù)據(jù)中最小的通信粒度與并行粒度。當頂點設(shè)置于多臺機器上時，應(yīng)將其中一臺機器視作master頂點，將剩下的所有機器視作mirror頂點。全部mirror頂點都需由Master負責管理，接收其下達的計算任務(wù)。而mirror是master頂點在各臺機器中的代理實施者，因此要確保其數(shù)據(jù)和master數(shù)據(jù)的同步。在并行計算過程中，各個線程分攤進程中所有頂點的gather->apply->scatter操作。任何頂點在迭代過程中均需歷經(jīng)gather、apple、scatter這三個發(fā)展階段，下面將對其展開具體地介紹。

1.1 Gather階段

通過自身或者鄰接頂點，工作頂點的邊獲取到相應(yīng)數(shù)據(jù)，并做好gather_data_i的標注，然后由所有邊的數(shù)據(jù)graphlab進行求和，用sum_data表示求和結(jié)果。在該階段，所有的邊與工作頂點均為只讀的。

1.2 Apply階段

Mirror向master頂點成功發(fā)送gather計算的結(jié)果sum_data后，由master負責歸納整理，結(jié)果用total表示。然后，Master結(jié)合業(yè)務(wù)的實際需求，在上一環(huán)節(jié)的頂點數(shù)據(jù)與total結(jié)果的基礎(chǔ)上實施計算，針對master的頂點數(shù)據(jù)進行更新，并且同步mirror。這一發(fā)展階段的邊不支持修改，但工作頂點是可進行調(diào)整。

1.3 Scatter階段

待工作頂點更新完畢后，應(yīng)對邊上的數(shù)據(jù)進行更新，并向與其關(guān)系較為密切的鄰接頂點發(fā)布通知，使其更新狀態(tài)。在該發(fā)展階段，邊上數(shù)據(jù)可寫，工作頂點只讀。

2 復(fù)雜網(wǎng)絡(luò)理論

物理學(xué)家霍金說過“21世紀將是復(fù)雜性科學(xué)的世紀”。復(fù)雜網(wǎng)絡(luò)（Complex Network），顧名思義，指的是具備小世界、自組織、無標度、吸引子、自相似中至少一種或全部性質(zhì)的網(wǎng)絡(luò)。最近幾年時間以來，學(xué)界紛紛開始加大力度探究復(fù)雜網(wǎng)絡(luò)，其中影響力最具影響力有兩大具有開創(chuàng)意義的工作。其一，1998年，Strogatz與Watts合著的文章被刊登在Nature雜志中，該著作指出，小世界（Small-World）網(wǎng)絡(luò)模型可用于闡釋由完全規(guī)則網(wǎng)絡(luò)逐步過渡到完全隨機網(wǎng)絡(luò)的過程，它具有平均路徑長度小、聚類特性和規(guī)則網(wǎng)絡(luò)相似的特征。其二，1999年，Albert與Barabasi發(fā)表了文章在Science上，其強調(diào)，大量復(fù)雜網(wǎng)絡(luò)的連接度均呈冪律式分布。因冪律分布不存在顯著的特征長度，因此該網(wǎng)絡(luò)又叫無標度（Scale-Free）網(wǎng)絡(luò)。隨后，相關(guān)研究人員開始重視對復(fù)雜網(wǎng)絡(luò)的特征的探究，其涉足的領(lǐng)域主要有計算機網(wǎng)絡(luò)研究、圖論、社會學(xué)、統(tǒng)計物理學(xué)、經(jīng)濟學(xué)以及生態(tài)學(xué)等，涉足的網(wǎng)絡(luò)大致涵蓋了蛋白質(zhì)折疊網(wǎng)絡(luò)、Internet/WWW網(wǎng)絡(luò)、生命科學(xué)領(lǐng)域的網(wǎng)絡(luò)、社會網(wǎng)絡(luò)等。在研究過程中，主要采取物理學(xué)中的社會網(wǎng)絡(luò)分析法、統(tǒng)計物理學(xué)法以及數(shù)學(xué)領(lǐng)域的圖論。

截至如今，復(fù)雜網(wǎng)絡(luò)的研究對象較之前有了進一步拓展，針對網(wǎng)絡(luò)的演化動力學(xué)機制、形成機制、結(jié)構(gòu)穩(wěn)定性、網(wǎng)絡(luò)中的模型性質(zhì)以及網(wǎng)絡(luò)發(fā)展的統(tǒng)計規(guī)律等問題均有涉獵。網(wǎng)絡(luò)研究的基本測度主要有：度的相關(guān)性、最短距離及其分布特點、度及其分布特點、集聚程度及其分布特點、連通集團的規(guī)模分布以及介數(shù)及其分布特點。利用GraphLab大數(shù)據(jù)處理技術(shù)對上述復(fù)雜網(wǎng)絡(luò)的計算研究起始于基本的三項內(nèi)容，它們分別是度與度分布、平均路徑長度和聚類系數(shù)。我們選取Facebook于2015年3月公開數(shù)據(jù)集，節(jié)點數(shù)18462135，鏈接數(shù)41963380。

3 GraphLab處理大數(shù)據(jù)注意問題

3.1成功的分析中絕大部分工作是數(shù)據(jù)預(yù)處理

數(shù)據(jù)是混亂的，在讓數(shù)據(jù)產(chǎn)生價值之前，必須對數(shù)據(jù)進行清洗、處理、融合、挖掘和許多其他操作。特別是對大數(shù)據(jù)集，由于人們很難直接檢查，為了知道需要哪些預(yù)處理步驟，甚至需采用計算方法。一般情況下，即使在模型調(diào)優(yōu)階段，在整個數(shù)據(jù)處理管道各個作業(yè)中，花在特征提取和選擇上的時間比選擇和實現(xiàn)算法的時間還要多。 比如，在構(gòu)建Facebook社交數(shù)據(jù)網(wǎng)絡(luò)模型時，數(shù)據(jù)科學(xué)家需要從許多可能的特征中進行選擇。這些特征包括必填項個人、登錄時間和轉(zhuǎn)發(fā)點擊等。在將特征轉(zhuǎn)換成適用于機器學(xué)習(xí)算法的向量時，每個特征可能都會有不同的問題。系統(tǒng)需要支持更靈活的轉(zhuǎn)換，遠遠不止是將二維雙精度數(shù)組轉(zhuǎn)換成一個數(shù)學(xué)模型那么簡單。

3.2迭代與數(shù)據(jù)科學(xué)緊密相關(guān)

在利用GraphLab建模和分析經(jīng)常需要對一個數(shù)據(jù)集進行多次遍歷。這其中一方面是由機器學(xué)習(xí)算法和統(tǒng)計過程本身造成的。常用的優(yōu)化過程，比如隨機梯度下降 和最大似然估計，在收斂前都需要多次掃描輸入數(shù)據(jù)。數(shù)據(jù)科學(xué)家自身的工作流程也涉及迭代。在初步調(diào)查和理解數(shù)據(jù)集時，一個查詢的結(jié)果往往給下一個查詢帶來啟示。在構(gòu)建模型時，數(shù)據(jù)科學(xué)家往往很難在第一次就得到理想的結(jié)果。選擇正確的特征，挑選合適的算法，運行恰當?shù)娘@著性測試，找到合適的超參數(shù)，所有這些工作都需要反復(fù)試驗。

3.3通過對大數(shù)據(jù)的研究，人類可知曉是何種數(shù)據(jù)，但無法知曉具體的原因

眾所周知，在檢測相關(guān)性方面，大數(shù)據(jù)的性能優(yōu)越，甚至于可檢測出小數(shù)據(jù)集不能測出的微小相關(guān)性，然而卻無法告知研究人員，何種相關(guān)性的意義顯著。舉個例子，假定大數(shù)據(jù)分析結(jié)果顯示，F(xiàn)acebook的數(shù)據(jù)與瀏覽時間在2015年1月至3月這一段時間內(nèi)表現(xiàn)出極度相關(guān)性，且呈現(xiàn)出驟降的發(fā)展態(tài)勢。然而，這一結(jié)果很難領(lǐng)研究人員信服。

3.4大數(shù)據(jù)可以輔助科學(xué)調(diào)查，但不可能成功地完全代替

比如，在利用Facebook數(shù)據(jù)的處理中想推導(dǎo)出潛在的網(wǎng)絡(luò)數(shù)據(jù)演化模型，部分科學(xué)家已在試圖通過大數(shù)據(jù)的方式使該問題得到妥善地處理。然而，不論是哪個科學(xué)家均無法純粹地通過處理數(shù)據(jù)的方式達到目的，在實踐過程中他們往往會綜合利用數(shù)學(xué)理論與物理理論來對數(shù)據(jù)進行處理。

4 結(jié)束語

到目前為止，基于傳統(tǒng)領(lǐng)域的計算方法對于復(fù)雜網(wǎng)絡(luò)的研究越來越顯示出局限性，其主要原因在于對目前大數(shù)據(jù)量的網(wǎng)絡(luò)信息無法定量的加以研究?；贕raphLab大數(shù)據(jù)框架為復(fù)雜網(wǎng)絡(luò)研究提供了一條新的思路，是研究者可以便利的開展復(fù)雜網(wǎng)絡(luò)的計算研究。對網(wǎng)絡(luò)圖的搭建，以及演化機理的闡述，嘗試從結(jié)構(gòu)方面進行趨勢的研究，從而引導(dǎo)復(fù)雜網(wǎng)絡(luò)具體量化計算發(fā)展的趨勢。

參考文獻：

[1]趙剛.大數(shù)據(jù)：技術(shù)與應(yīng)用實踐指南[M] 北京：電子工業(yè)出版社，2013，20-163.

[2]李軍.大數(shù)據(jù)：從海量到精準[M] 北京：清華大學(xué)出版社，2014，120-260.

[3]（美）卡勞.Spark快速大數(shù)據(jù)分析[M] 北京：人民郵電出版社，2015，20-150.

[4]何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)[M].北京：高等教育出版社，2009，143-202.

[5]郭雷，許曉鳴.復(fù)雜網(wǎng)絡(luò)[M].上海：上?？萍冀逃霭嫔?，2006，128-132.

[6]（美）Tom White. Hadoop權(quán)威指南[M] 北京：清華大學(xué)出版社，2015，21-298.

[7]林敏.網(wǎng)絡(luò)拓撲結(jié)構(gòu)對自組織臨界行為影響的研究[D].天津：南開大學(xué)，2005，1-30.

[8]韓定定.復(fù)雜網(wǎng)絡(luò)的拓撲、動力學(xué)行為及其實證研究[D].上海：華東師范大學(xué)，2008，43-50.

（作者單位：1.蘭州財經(jīng)大學(xué)；2.天水師范學(xué)院）