GraphLab大數據框架與復雜網絡結合研究

張瑞　王三福

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

關鍵詞：GraphLab；復雜網絡；度計算；最短路徑；聚集系數

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

1 GraphLab大數據框架

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

圖1 Graph對并行思想

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

1.1 Gather階段

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

1.2 Apply階段

Mirror向master頂點成功發送gather計算的結果sum_data后，由master負責歸納整理，結果用total表示。然后，Master結合業務的實際需求，在上一環節的頂點數據與total結果的基礎上實施計算，針對master的頂點數據進行更新，并且同步mirror。這一發展階段的邊不支持修改，但工作頂點是可進行調整。

1.3 Scatter階段

待工作頂點更新完畢后，應對邊上的數據進行更新，并向與其關系較為密切的鄰接頂點發布通知，使其更新狀態。在該發展階段，邊上數據可寫，工作頂點只讀。

2 復雜網絡理論

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

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

3 GraphLab處理大數據注意問題

3.1成功的分析中絕大部分工作是數據預處理

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

3.2迭代與數據科學緊密相關

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

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

眾所周知，在檢測相關性方面，大數據的性能優越，甚至于可檢測出小數據集不能測出的微小相關性，然而卻無法告知研究人員，何種相關性的意義顯著。舉個例子，假定大數據分析結果顯示，Facebook的數據與瀏覽時間在2015年1月至3月這一段時間內表現出極度相關性，且呈現出驟降的發展態勢。然而，這一結果很難領研究人員信服。

3.4大數據可以輔助科學調查，但不可能成功地完全代替

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

4 結束語

到目前為止，基于傳統領域的計算方法對于復雜網絡的研究越來越顯示出局限性，其主要原因在于對目前大數據量的網絡信息無法定量的加以研究。基于GraphLab大數據框架為復雜網絡研究提供了一條新的思路，是研究者可以便利的開展復雜網絡的計算研究。對網絡圖的搭建，以及演化機理的闡述，嘗試從結構方面進行趨勢的研究，從而引導復雜網絡具體量化計算發展的趨勢。

參考文獻：

[1]趙剛.大數據：技術與應用實踐指南[M] 北京：電子工業出版社，2013，20-163.

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

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

[4]何大韌，劉宗華，汪秉宏.復雜系統與復雜網絡[M].北京：高等教育出版社，2009，143-202.

[5]郭雷，許曉鳴.復雜網絡[M].上海：上海科技教育出版社，2006，128-132.

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

[7]林敏.網絡拓撲結構對自組織臨界行為影響的研究[D].天津：南開大學，2005，1-30.

[8]韓定定.復雜網絡的拓撲、動力學行為及其實證研究[D].上海：華東師范大學，2008，43-50.

（作者單位：1.蘭州財經大學；2.天水師范學院）