張瑞 王三福
摘 要:文章結(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é)院)