劉麗嬌，陶俊才，肖曉軍，盧 宇

（1.南昌大學(xué)信息工程學(xué)院計(jì)算中心 南昌 330029；2.廣州優(yōu)億信息科技有限公司 廣州 510630）

1 引言

對(duì)大規(guī)模數(shù)據(jù)特別是大規(guī)模圖數(shù)據(jù)的分析和計(jì)算近年來獲得了廣泛關(guān)注。在電信領(lǐng)域，現(xiàn)代通信設(shè)備的發(fā)展和普及使得電信數(shù)據(jù)不斷擴(kuò)增，而如何挖掘并利用這些數(shù)據(jù)實(shí)現(xiàn)客戶關(guān)系維系，挖掘客戶潛在價(jià)值以及為客戶提供個(gè)性化的服務(wù)項(xiàng)目，在日益激烈的市場(chǎng)競(jìng)爭(zhēng)環(huán)境中顯得尤為重要。

電信網(wǎng)絡(luò)數(shù)據(jù)可以映射成由頂點(diǎn)和邊表達(dá)的抽象圖數(shù)據(jù)結(jié)構(gòu)，從而形成社交關(guān)系網(wǎng)絡(luò)。社交關(guān)系網(wǎng)絡(luò)具有“小世界性”，它可以反映網(wǎng)絡(luò)的局部特征，電信運(yùn)營(yíng)商通過分析每個(gè)客戶群中成員的年齡、性別、職業(yè)、級(jí)別、愛好和興趣等相關(guān)特征，在推廣新業(yè)務(wù)、減少客戶流失、防止詐騙等方面有重要作用。同時(shí)可以根據(jù)客戶資料信息、語音清單和短信清單，發(fā)掘客戶交往圈信息，幫助市場(chǎng)部門細(xì)分客戶群，制定有競(jìng)爭(zhēng)力和針對(duì)性的營(yíng)銷方案[1]。

圖1所示為抽象后的用戶網(wǎng)絡(luò)關(guān)系，利用圖計(jì)算的PageRank算法可以分析出該網(wǎng)絡(luò)中的關(guān)鍵人物，圖中圓圈的大小表示對(duì)應(yīng)的用戶在關(guān)系網(wǎng)中的重要程度，邊的粗細(xì)表示往來的頻繁程度。

圖的處理技術(shù)已經(jīng)發(fā)展了很長(zhǎng)一段時(shí)間，并形成了成熟的理論基礎(chǔ)，但是信息時(shí)代帶來各種數(shù)據(jù)的爆炸式增長(zhǎng)，導(dǎo)致圖的規(guī)模也日益增大，動(dòng)輒上百萬個(gè)節(jié)點(diǎn)，上億條邊。以互聯(lián)網(wǎng)和社交網(wǎng)絡(luò)為例，近幾十年來，互聯(lián)網(wǎng)的普及和Web 2.0技術(shù)的推動(dòng)，社交網(wǎng)絡(luò)的發(fā)展異常迅猛，如全球最大的社交網(wǎng)絡(luò)Facebook已有約7億用戶，新浪微博用戶數(shù)已達(dá)5億。將這樣龐大的數(shù)據(jù)量抽象為圖來進(jìn)行計(jì)算和挖掘是非常困難的。

大規(guī)模圖數(shù)據(jù)時(shí)代已然到來，而如何高效處理大規(guī)模圖數(shù)據(jù)，成為一個(gè)新的挑戰(zhàn)，設(shè)計(jì)簡(jiǎn)單可用的系統(tǒng)來分析處理現(xiàn)實(shí)世界中大規(guī)模的圖已經(jīng)成為當(dāng)前面臨的最迫切的問題。

面對(duì)這些挑戰(zhàn)，當(dāng)前針對(duì)大規(guī)模圖數(shù)據(jù)的處理和分析主要有單機(jī)處理方式和并行分布式處理方式。本文介紹了幾種大規(guī)模圖數(shù)據(jù)運(yùn)算的分布式工具和單機(jī)計(jì)算工具Graphchi，并且針對(duì)Graphchi的應(yīng)用前景以及大數(shù)據(jù)圖處理的可行性和可用性進(jìn)行了實(shí)驗(yàn)和對(duì)比，最后應(yīng)用Graphchi對(duì)電信社交關(guān)系網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行了挖掘?qū)嶒?yàn)。

2 相關(guān)工作

2.1 分布式框架下的圖計(jì)算工具

2.1.1 Pregel

為了解決MapReduce在一些機(jī)器學(xué)習(xí)算法中性能瓶頸問題，Google針對(duì)大規(guī)模圖運(yùn)算提出了Pregel框架，它是嚴(yán)格的BSP（bulk synchronous parallel）模型（BSP模型，即“大塊”同步模型，其概念由哈佛大學(xué)的Valiant和牛津大學(xué)的Bill McColl提出，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步），采用“計(jì)算-通信-同步”模式面向頂點(diǎn)的迭代方式完成機(jī)器學(xué)習(xí)的數(shù)據(jù)同步，這種靈活的面向頂點(diǎn)的方法和高效的容錯(cuò)機(jī)制的設(shè)計(jì)模式可以描述一系列的算法，并在有上千臺(tái)的計(jì)算節(jié)點(diǎn)的集群中得以實(shí)現(xiàn)。

在集群環(huán)境中，從遠(yuǎn)程機(jī)器上讀取數(shù)據(jù)難以避免地會(huì)有延遲，Pregel選擇了一種純消息傳遞的模式，通過異步和批量的方式傳遞消息，通過共享內(nèi)存的方式，有效地緩解了遠(yuǎn)程讀取數(shù)據(jù)的延遲，提升了集群的性能，并且Pregel應(yīng)用一組抽象的API隱藏了分布式編程的相關(guān)細(xì)節(jié)，展現(xiàn)給使用者一個(gè)易編程和易使用的大型圖算法處理計(jì)算框架。

圖1 抽象后的用戶網(wǎng)絡(luò)關(guān)系

但是Google一直沒有將Pregel的具體實(shí)現(xiàn)開源，外界對(duì)Pregel的模仿實(shí)現(xiàn)在性能和穩(wěn)定性方面都未能達(dá)到工業(yè)級(jí)應(yīng)用的標(biāo)準(zhǔn)。同時(shí)，在圖計(jì)算中，由于圖的頂點(diǎn)、邊密度的不平衡性的特點(diǎn)，帶來BSP模型的“木桶效應(yīng)”（木桶效應(yīng)是由美國(guó)管理學(xué)家彼得提出的，本文指的是先完成的任務(wù)需要等待后完成的任務(wù)，處理速度最慢的任務(wù)將成為整個(gè)系統(tǒng)的效率制約瓶頸）的限制，網(wǎng)絡(luò)、計(jì)算機(jī)硬件中的差異性也會(huì)使這種現(xiàn)象更加明顯。

2.1.2 Spark

Spark是UC Berkeley AMP實(shí)驗(yàn)室開發(fā)的通用的并行計(jì)算框架，是Pregel的優(yōu)化模型，它是基于MapReduce算法實(shí)現(xiàn)的分布式計(jì)算框架。Spark擁有MapReduce所具有的優(yōu)點(diǎn)，但不同于MapReduce的是，Spark采用了一種彈性分布式數(shù)據(jù)集（resilient distributed dataset，RDD）的抽象數(shù)據(jù)結(jié)構(gòu)，Spark是一個(gè)基于內(nèi)存計(jì)算的開源的集群計(jì)算系統(tǒng)。

RDD是一個(gè)具有容錯(cuò)機(jī)制的特殊集合，它提供了一種抽象的數(shù)據(jù)架構(gòu)，使用RDD邏輯轉(zhuǎn)換而來的可重復(fù)使用的共享內(nèi)存，而不再需要反復(fù)讀寫HDFS，解決了MapReduce框架在迭代計(jì)算式中要進(jìn)行大量磁盤I/O操作的問題，這讓數(shù)據(jù)分析更加快速，為構(gòu)建低延遲的并行性大數(shù)據(jù)分析處理框架提供了穩(wěn)定的基礎(chǔ)。

同時(shí)，Spark提供了REPL（read-eval-print loop）的交互式查詢以及函數(shù)式編程，支持圍繞RDD抽象的API，同時(shí)包括一套transformation（轉(zhuǎn)化）和action（動(dòng)作）操作以及針對(duì)大量流行編程語言的支持，比如Scala、Java和Python。

在圖計(jì)算方面，Spark原生的Bagel以及Graphx提供了對(duì)于圖操作的API，為大規(guī)模的圖計(jì)算提供了低延遲，負(fù)責(zé)優(yōu)化交互式的大規(guī)模并行處理框架，但是Spark的磁盤索引是簡(jiǎn)單的靜態(tài)機(jī)制，無法隨著迭代狀態(tài)的變化而動(dòng)態(tài)優(yōu)化。

2.1.3 Graphlab

Graphlab是CMU的Select實(shí)驗(yàn)室提出的基于內(nèi)存共享機(jī)制且面向機(jī)器學(xué)習(xí)的流處理并行框架，它的分布式處理是基于MPI（message passing interface，消息傳遞接口）實(shí)現(xiàn)的，并且將數(shù)據(jù)抽象成圖結(jié)構(gòu)，它是以圖的頂點(diǎn)為計(jì)算單元的大規(guī)模圖處理系統(tǒng)，支持稀疏的計(jì)算依賴異步迭代計(jì)算等，解決了MapReduce不適應(yīng)需要頻繁數(shù)據(jù)交換的迭代機(jī)器學(xué)習(xí)算法問題，是繼Google的Pregel之后的第一個(gè)開源的大規(guī)模圖處理系統(tǒng)。

Graphlab的核心思想是“以圖頂點(diǎn)的方式思考問題”，以最小化集群計(jì)算節(jié)點(diǎn)之間的通信量和均衡計(jì)算節(jié)點(diǎn)上的計(jì)算和存儲(chǔ)資源為原則，對(duì)圖的頂點(diǎn)進(jìn)行切分。類似于MapReduce中的map和reduce過程，它將機(jī)器學(xué)習(xí)抽象成GAS（gather（收集）、apply（運(yùn)算）、scatter（更新））3個(gè)步驟，然后按該抽象模型設(shè)計(jì)頂點(diǎn)程序?qū)崿F(xiàn)算法。在gather階段，當(dāng)前點(diǎn)收集鄰接點(diǎn)和邊的值，結(jié)合自身的值，進(jìn)行簡(jiǎn)單的用戶定義的sum（求和）操作；在apply階段，當(dāng)前點(diǎn)根據(jù)sum得到的值及其前一時(shí)刻自身的值計(jì)算新的點(diǎn)值；scatter階段當(dāng)前點(diǎn)利用自己的新值，結(jié)合鄰接點(diǎn)/邊前一時(shí)刻的值來計(jì)算鄰接邊的新值，并更新鄰接邊。

GraphLab的算法被應(yīng)用于很多推薦系統(tǒng)，也包括銀行的欺詐偵測(cè)和電腦網(wǎng)絡(luò)中的入侵偵測(cè)等領(lǐng)域。

2.1.4 PowerGraph

PowerGraph是卡內(nèi)基梅隆大學(xué)設(shè)計(jì)的一種強(qiáng)大的圖計(jì)算分布式并行框架，它結(jié)合了Graphlab和Pregel關(guān)于圖計(jì)算的優(yōu)點(diǎn)，有效改善了Pregel和Graphlab等框架的并行化受限于頂點(diǎn)的鄰居個(gè)數(shù)的問題。

現(xiàn)實(shí)世界中的圖，都是典型的Power-Law（冪律）分布圖，其中少部分頂點(diǎn)連接到圖中大部分的頂點(diǎn)上，這種圖的劃分對(duì)于并行的分布式框架來說是一個(gè)非常大的難題，并且圖的劃分效率直接影響系統(tǒng)的通信開銷。一般的并行框架采用的是散列隨機(jī)分配方案，但這種方案沒有考慮局部性，劃分完成后各任務(wù)負(fù)責(zé)的子圖之間的強(qiáng)耦合性導(dǎo)致后續(xù)的迭代計(jì)算過程產(chǎn)生大量的消息通信，嚴(yán)重影響負(fù)載均衡。PowerGraph使用了支持同步處理和異步處理機(jī)制的GAS模型，并且提出了一種P-路頂點(diǎn)切割分區(qū)方案，在減少計(jì)算中通信量的同時(shí)保證了負(fù)載均衡，很好地解決了圖的Power-Law問題。

2.2 單機(jī)圖計(jì)算工具——Graphchi

除了以上介紹的分布式圖計(jì)算框架外，還可以使用單機(jī)的圖算法庫(kù)，如BGL、LEAD、NetworkX、JDSL、Standford GraphBase、FGL等進(jìn)行圖的挖掘和計(jì)算，但這種單機(jī)的方式由于內(nèi)存限制的原因，對(duì)圖本身的規(guī)模有了很大的限制[2]。

為解決單機(jī)圖計(jì)算的內(nèi)存瓶頸問題，卡內(nèi)基梅隆大學(xué)的Select實(shí)驗(yàn)室開發(fā)了Graphchi，它是Graphlab的一個(gè)分支，采用基于磁盤的以頂點(diǎn)為中心的計(jì)算模型，它可以在PC上進(jìn)行大規(guī)模的類似于社會(huì)網(wǎng)絡(luò)分析的圖計(jì)算，而不需要分布式的集群和云服務(wù)，也不需要考慮內(nèi)存的限制。

2.2.1 基于磁盤的計(jì)算

要想利用單機(jī)而不利用集群來并行地進(jìn)行大規(guī)模的圖計(jì)算，首當(dāng)其沖面臨的是存儲(chǔ)問題。龐大的圖數(shù)據(jù)在內(nèi)存中處理上百萬條邊需要幾十或幾百吉字節(jié)的DRAM，因?yàn)槠鋬r(jià)格昂貴，目前只對(duì)高端服務(wù)器有可用性，所以Graphchi將目光投向了價(jià)格低廉、容量大的磁盤作為其外部存儲(chǔ)，用基于磁盤的計(jì)算模型減少內(nèi)存的使用和隨機(jī)存取問題。

然而，如何從磁盤上處理大規(guī)模的圖數(shù)據(jù)是一個(gè)難題。為了處理這個(gè)問題，Graphchi采用了新穎的PSW（parallel sliding window，并行式滑動(dòng)窗口）模型，從磁盤上處理大的圖數(shù)據(jù)。

2.2.2 PSW模型

Graphchi采用了PSW模型從磁盤處理大的圖數(shù)據(jù)，不同于分布式框架通用的BSP模型，PSW模型能夠異步處理存儲(chǔ)在硬盤上的可擴(kuò)展圖數(shù)據(jù)，有效規(guī)避了“木桶效應(yīng)”。

PSW模型中，邊的信息分區(qū)shard采用不相交子集（頂點(diǎn)集被分為P個(gè)子集interval(i)）的形式關(guān)聯(lián)存儲(chǔ)，這種存儲(chǔ)方式將每個(gè)子集以滑動(dòng)窗口的形式分別從硬盤裝入內(nèi)存。Graphchi分多次取節(jié)點(diǎn)子集interval(i)，每次取1個(gè)，并且根據(jù)節(jié)點(diǎn)子集中的點(diǎn)信息構(gòu)造子圖進(jìn)行計(jì)算。在第p次操作所需的子圖數(shù)據(jù)載入后，每個(gè)節(jié)點(diǎn)并行地執(zhí)行用戶定義的更新函數(shù)，并更新節(jié)點(diǎn)，節(jié)點(diǎn)子集更新后的塊文件將被寫入磁盤。

圖2表示PSW模型進(jìn)行一次迭代的滑動(dòng)窗口示意，頂點(diǎn)被分為4個(gè)不相交的子集，每個(gè)自己都關(guān)聯(lián)一個(gè)分區(qū)，計(jì)算過程是構(gòu)建一次子圖頂點(diǎn)的子集。從內(nèi)存的分區(qū)中讀取頂點(diǎn)的入邊，從每個(gè)滑動(dòng)的分區(qū)中讀取出邊，每個(gè)分區(qū)的最頂端為當(dāng)前的滑動(dòng)窗口。

2.2.3 Graphchi基于PSW模型的改進(jìn)

為了支持Graphchi的可擴(kuò)展性，Graphchi對(duì)PSW模型進(jìn)行了改進(jìn)，通過實(shí)現(xiàn)一個(gè)簡(jiǎn)化的、高效的I/O緩存樹來支持圖邊的增加和刪除，改進(jìn)的PSW模型如圖3所示。

圖3 改進(jìn)的PSW模型

圖4 顯示了Graphchi執(zhí)行PSW模型的流程。

圖4 Graphchi流程

3 Graphchi應(yīng)用前景

3.1 分布式圖計(jì)算局限性

基于圖的分布式框架通過云平臺(tái)的計(jì)算資源處理上百萬條邊的圖數(shù)據(jù)有很高的效率，但是利用分布式集群進(jìn)行圖計(jì)算仍然面臨較高的硬件和技術(shù)要求，對(duì)于那些沒有分布式專業(yè)背景、沒有足夠的硬件資源的人來說，仍然是個(gè)巨大的挑戰(zhàn)。

首先，使用分布式框架時(shí)，使用者面臨如何將強(qiáng)耦合性的圖數(shù)據(jù)進(jìn)行分割，部署到集群計(jì)算節(jié)點(diǎn)上的問題[3]。其次，圖的分布式計(jì)算涉及復(fù)雜的處理過程，需要大量的迭代和數(shù)據(jù)通信，大多數(shù)分布式系統(tǒng)用到的是BSP模型，是一種同步計(jì)算模型，對(duì)于消息的處理容量有限，網(wǎng)絡(luò)的延遲以及節(jié)點(diǎn)間的通信會(huì)造成“木桶效應(yīng)”。再次，分布式框架處理需要計(jì)算耗時(shí)的大規(guī)模圖數(shù)據(jù)時(shí)，重復(fù)計(jì)算以及系統(tǒng)故障使效率大大降低，同時(shí)系統(tǒng)的容錯(cuò)性也是制約運(yùn)算效率和穩(wěn)定性的關(guān)鍵瓶頸。最后，對(duì)于編程者來說，調(diào)試和優(yōu)化分布式算法有很大的難度。

相對(duì)于復(fù)雜的分布式集群框架來說，簡(jiǎn)單的單機(jī)進(jìn)行大規(guī)模的圖計(jì)算，能夠規(guī)避分布式框架的問題。使用者不需考慮強(qiáng)耦合性的圖數(shù)據(jù)如何分割放置到分布式的集群節(jié)點(diǎn)中，也不需管理和部署眾多的集群節(jié)點(diǎn)，并且可以減少分布式集群節(jié)點(diǎn)中的通信開銷，規(guī)避網(wǎng)絡(luò)延遲、“木桶效應(yīng)”等問題。

例如，企業(yè)如果想要在同一張圖上計(jì)算多種任務(wù)（個(gè)性化推薦、圖的社團(tuán)發(fā)現(xiàn)等），在不同的國(guó)家、不同的利益集團(tuán)都要計(jì)算同一個(gè)任務(wù)的情況下，企業(yè)要想提高運(yùn)算速度，就必須要增加集群節(jié)點(diǎn)，也就是說要增加成本。但是，如果一臺(tái)機(jī)器上可以處理一個(gè)這樣的大任務(wù)，企業(yè)可以為每臺(tái)機(jī)器分配一個(gè)任務(wù)，每臺(tái)機(jī)器之間無需互相通信，當(dāng)增加機(jī)器數(shù)量時(shí)，吞吐量也隨之增加，這樣多種任務(wù)的處理將會(huì)變得非常簡(jiǎn)單、有效。

僅僅需要一臺(tái)機(jī)器就可以對(duì)大規(guī)模的圖數(shù)據(jù)進(jìn)行分析處理和挖掘，這可以大大簡(jiǎn)化分布式集群處理框架的復(fù)雜性，如圖5所示。

圖5 集群與單機(jī)處理多任務(wù)情況

本文對(duì)單機(jī)處理圖數(shù)據(jù)技術(shù)Graphchi的發(fā)展、應(yīng)用場(chǎng)景以及性能進(jìn)行了研究，并進(jìn)行了試驗(yàn)。

3.2 單機(jī)Graphchi應(yīng)用前景

在圖挖掘方面，Graphchi實(shí)現(xiàn)了PageRank、連通分支、社區(qū)發(fā)現(xiàn)等算法處理和分析現(xiàn)實(shí)世界中大規(guī)模的圖數(shù)據(jù)；另外，應(yīng)用在協(xié)同過濾算法的推薦系統(tǒng)中，Graphchi從紛繁復(fù)雜的信息中找出可向用戶推薦的有價(jià)值的信息。

不僅在圖挖掘和協(xié)同過濾方面，Graphchi還提供了通用的編程框架，支持使用者調(diào)用自己的算法對(duì)圖進(jìn)行分析和計(jì)算，這使得Graphchi使用起來更加靈活，也有更加個(gè)性化的可用性。

當(dāng)前Graphchi中一些應(yīng)用的算法設(shè)計(jì)還不盡完善，但是隨著技術(shù)的發(fā)展以及應(yīng)用的普及，Graphchi因其在圖計(jì)算方面獨(dú)特的模型，其單機(jī)運(yùn)行的簡(jiǎn)便、高可用和可觀的運(yùn)行效率，將在大規(guī)模圖計(jì)算方面表現(xiàn)出越來越廣闊的應(yīng)用前景。

為了驗(yàn)證Graphchi在不同硬件環(huán)境下，不同數(shù)量級(jí)別社交網(wǎng)絡(luò)圖數(shù)據(jù)應(yīng)用中的可行性和可用性，下文對(duì)不同數(shù)量級(jí)的數(shù)據(jù)在兩種不同的環(huán)境進(jìn)行了相應(yīng)的測(cè)試，并且和其他分布式框架進(jìn)行了對(duì)比。

4 Graphchi的可行性、可用性評(píng)估實(shí)驗(yàn)

4.1 測(cè)試環(huán)境

·Intel(R)Core(TM)2Duo CPU T6600@2.20 GHz、RAM 2 GB、Ubuntu11.04。

·Dell服務(wù)器QEMU Virtual CPU Version(cpu64-rhel6)6核CPU、4 GB內(nèi)存（未特殊注明，本文中數(shù)據(jù)測(cè)試環(huán)境均為服務(wù)器環(huán)境）、CentOS 6.4。

4.2 數(shù)據(jù)集說明

本文采用的數(shù)據(jù)集來自斯坦福的Snap網(wǎng)站[4]以及Netflix網(wǎng)站。測(cè)試的數(shù)據(jù)集為Wiki、Twitter、Facebook、Friendster等流行的社交網(wǎng)站，數(shù)據(jù)集大小為40 MB～30 GB。

表1是對(duì)實(shí)驗(yàn)中使用到的測(cè)試數(shù)據(jù)集的說明，其中|V|表示測(cè)試數(shù)據(jù)集的頂點(diǎn)數(shù)目，|E|表示測(cè)試數(shù)據(jù)集邊的數(shù)目。

表1 測(cè)試數(shù)據(jù)集

4.3 Graphchi測(cè)試結(jié)果

圖6表示的是PageRank和CommunityDetection兩種算法對(duì)除Netflix數(shù)據(jù)集外所有數(shù)據(jù)集進(jìn)行的測(cè)試，X軸表示邊集的數(shù)量，Y軸表示對(duì)應(yīng)的運(yùn)行時(shí)間。從圖中可以看出，對(duì)于兩種不同算法，隨著數(shù)據(jù)集的增大，運(yùn)行時(shí)間大體呈線性增長(zhǎng)。

圖6 兩種算法隨邊規(guī)模增長(zhǎng)運(yùn)行時(shí)間變化

圖7 表示PageRank和CommunityDetection兩種算法以及CommunityDetection分別在4次和10次迭代過程中，吞吐量隨邊數(shù)的變化。X軸為邊集的數(shù)量，Y軸表示吞吐量（系統(tǒng)每秒處理邊的數(shù)量）。Graphchi每秒可以處理的邊的數(shù)量為0.2×106～2×106個(gè)。

圖7 兩種算法吞吐量隨邊數(shù)變化

Graphchi測(cè)試Twitter 2010年所有的user-follower關(guān)系，14億條邊、4千萬個(gè)頂點(diǎn)共20 GB的數(shù)據(jù)，PageRank算法需要46min，CommunityDetection算法10次迭代需要70min，Trianglecounting算法需要130 min；測(cè)試在線游戲Friendster，18億個(gè)頂點(diǎn)、6千萬條邊共30 GB的數(shù)據(jù)集comfriendster.ungraph，PageRank算法4次迭代需要54 min。

可見，Graphchi可以在1 h左右完成對(duì)社交網(wǎng)絡(luò)一年數(shù)據(jù)的分析。這種處理能力完全可以滿足使用者對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行計(jì)算的需求，并且具有較好的吞吐量。

圖8表示的是Graphchi測(cè)試兩種數(shù)據(jù)集smallNetflix和Netflix協(xié)同過濾的7種算法進(jìn)行6次迭代的運(yùn)行時(shí)間。X軸表示7種協(xié)同過濾算法：SGD、ALS、RBM、SVD++、biasSGD、CCD++和PMF，Y軸對(duì)應(yīng)的是各種算法的運(yùn)行時(shí)間。

圖8 協(xié)同過濾算法運(yùn)行時(shí)間

Graphchi在協(xié)同過濾中的運(yùn)行時(shí)間最長(zhǎng)為450 s，Netflix數(shù)據(jù)集的時(shí)間不超過300 s。

圖9表示的是SGD算法運(yùn)行50次迭代的運(yùn)行時(shí)間以及RSME（root square mean error）均方差的變化曲線。迭代20次時(shí)，算法的RSME已經(jīng)趨于穩(wěn)定，無限接近于0.92，而此時(shí)的運(yùn)行時(shí)間約為350 s。

可見，Graphchi在協(xié)同過濾方面表現(xiàn)出良好的性能，可以在幾百秒的時(shí)間內(nèi)處理2 GB規(guī)模的數(shù)據(jù)。

圖10表示的是PageRank、CommunityDetection和ConnectedComponents 3種算法，wiki-Talk和com-orkut兩種測(cè)試集分別在2核CPU和6核CPU上運(yùn)行時(shí)間的對(duì)比。X軸表示運(yùn)行時(shí)間，Y軸表示3種算法以及兩種數(shù)據(jù)集。從圖10中可以看出，在相同數(shù)據(jù)集上6核CPU的運(yùn)行時(shí)間要比2核CPU運(yùn)行時(shí)間快了近10倍。

圖11表示的是協(xié)同過濾的3種算法，Netflix測(cè)試集分別在2核CPU和6核CPU上運(yùn)行時(shí)間的對(duì)比。X軸表示運(yùn)行時(shí)間，Y軸表示協(xié)同過濾4種不同算法。Netflix數(shù)據(jù)集在6核CPU上的運(yùn)行時(shí)間比在2核CPU上的運(yùn)行時(shí)間快了5～10倍。

圖9 SGD算法RSME隨迭代數(shù)變化曲線以及運(yùn)行50次迭代的時(shí)間變化曲線

圖10 3種算法兩種數(shù)據(jù)集在不同核數(shù)CPU上運(yùn)行時(shí)間對(duì)比

圖11 表示協(xié)同過濾4種算法在不同核數(shù)CPU運(yùn)行時(shí)間的對(duì)比。

隨著CPU數(shù)目的增加，運(yùn)行速度也有明顯的提升。相信在配置更高的單機(jī)上運(yùn)行Graphchi將會(huì)有更加可觀的性能。

圖11 協(xié)同過濾4種算法在不同核數(shù)CPU運(yùn)行時(shí)間對(duì)比

4.4 可行性、可用性分析對(duì)比

本文對(duì)比了一些分布式的圖處理框架，參考了一些其他文章的測(cè)試結(jié)果，見表2。

在 有50個(gè) 節(jié) 點(diǎn)、100個(gè)CPU的Spark框 架 下，在Twitter-2010數(shù)據(jù)集上運(yùn)行5次迭代的PageRank算法的時(shí)間比Graphchi在4核CPU的環(huán)境中運(yùn)行相同數(shù)據(jù)集快了大約5倍。在有1 636個(gè)節(jié)點(diǎn)的Hadoop框架運(yùn)行Twitter-2010數(shù)據(jù)集的PageRank算法迭代一次，Graphchi比Hadoop快45倍，比Powergraph慢了155倍。與運(yùn)行在AMD服務(wù)器上的Graphlab相比，用ALS算法測(cè)試Netflix數(shù)據(jù)集，Graphchi運(yùn)行時(shí)間是Graphlab的2.5倍。Trianglecounting算法測(cè)試Twitter-2010數(shù)據(jù)集在1 636個(gè)節(jié)點(diǎn)的Hadoop環(huán)境，Graphchi比Hadoop快了3倍。

相對(duì)于Hadoop來說，Graphchi的大規(guī)模圖數(shù)據(jù)方面的性能遠(yuǎn)優(yōu)于Hadoop；在協(xié)同過濾方面，Graphchi和Graphlab性能相差不大；與性能較好的Spark相比，Graphchi的性能表現(xiàn)也在可以接受的范圍內(nèi)；對(duì)于性能強(qiáng)大的Powergraph，Graphchi性能還是有一些差距。

總體來說，Graphchi以單機(jī)運(yùn)行方式進(jìn)行圖運(yùn)算所表現(xiàn)出的性能可以和一些分布式的框架相媲美，雖然不及性能強(qiáng)大的Powergraph，但是這樣的性能表現(xiàn)已經(jīng)可以滿足一定規(guī)模的圖運(yùn)算了。這樣的性能表現(xiàn)已足以為成本不足、硬件設(shè)備配置不高的中小企業(yè)或者個(gè)人提供高可行、高可用的社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)分析和挖掘平臺(tái)。

5 Graphchi電信圖數(shù)據(jù)挖掘應(yīng)用

為驗(yàn)證Graphchi對(duì)電信大規(guī)模圖數(shù)據(jù)的處理能力，本文構(gòu)造了電信通話清單數(shù)據(jù)約20 GB，有4 000萬個(gè)頂點(diǎn)、14億條邊（已對(duì)數(shù)據(jù)進(jìn)行匿名處理），格式見表3。

表2 Graphchi和不同框架性能對(duì)比

表3 電信數(shù)據(jù)格式

5.1 PageRank算法挖掘核心人物

PageRank算法是Google用于用來標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)/重要性的一種方法，是Google用來衡量一個(gè)網(wǎng)站好壞的唯一標(biāo)準(zhǔn)。它基于馬爾科夫狀態(tài)轉(zhuǎn)移理論，通過網(wǎng)頁(yè)的鏈入數(shù)對(duì)網(wǎng)頁(yè)進(jìn)行投票來得出重要性排名。

發(fā)展到目前，PageRank算法也被廣泛用于關(guān)鍵人物挖掘等社交關(guān)系網(wǎng)絡(luò)分析中。本文應(yīng)用Graphchi的Pagerank算法，對(duì)電信關(guān)系網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行Rank值的計(jì)算，從而找出關(guān)鍵人物。

表4是采用Graphchi的Pagerank算法對(duì)電信數(shù)據(jù)集進(jìn)行計(jì)算Rank值的排名前10的結(jié)果，在4 000萬個(gè)用戶中，標(biāo)號(hào)為1 653的用戶的重要性最高，為核心用戶，應(yīng)該對(duì)其重點(diǎn)挖掘和營(yíng)銷推廣。

表4 PageRank前10名排名結(jié)果

5.2 CommunityDetection算法進(jìn)行社區(qū)發(fā)現(xiàn)

CommunityDetection社區(qū)發(fā)現(xiàn)算法用于發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，也可以看作是一種聚類算法。同一社區(qū)之間的節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系比較緊密，而社區(qū)與社區(qū)之間的關(guān)系比較稀疏。如果兩者之間的聯(lián)系越頻繁，那么其社交關(guān)系就越緊密。如圖12所示，可以找到3個(gè)關(guān)系緊密的社區(qū)。

表5為采用Graphchi的CommunityDetection算法對(duì)電信數(shù)據(jù)集進(jìn)行社團(tuán)發(fā)現(xiàn)的結(jié)果，共發(fā)現(xiàn)社區(qū)1 733 613個(gè)，最大社區(qū)有35 558 616個(gè)用戶。運(yùn)營(yíng)商可以對(duì)每一個(gè)社團(tuán)分析其相似特征，進(jìn)行潛在客戶挖掘以及后續(xù)的客戶關(guān)系維護(hù)。

表5 社團(tuán)發(fā)現(xiàn)前10名社團(tuán)大小

6 結(jié)束語

電信技術(shù)的發(fā)展帶來了大規(guī)模的電信數(shù)據(jù)，面對(duì)日趨激烈的市場(chǎng)競(jìng)爭(zhēng)環(huán)境，電信運(yùn)營(yíng)商如何從通信數(shù)據(jù)抽象成大規(guī)模的圖網(wǎng)絡(luò)數(shù)據(jù)中挖掘有價(jià)值的信息，維護(hù)客戶關(guān)系，進(jìn)行針對(duì)性服務(wù)成了關(guān)注的焦點(diǎn)。

本文闡述了可以對(duì)大規(guī)模電信社交網(wǎng)絡(luò)圖數(shù)據(jù)進(jìn)行挖掘和計(jì)算的幾種分布式框架和單機(jī)計(jì)算框架。并且通過實(shí)驗(yàn)和對(duì)比，說明單機(jī)的Graphchi運(yùn)行各算法在不同規(guī)模數(shù)據(jù)集所用的時(shí)間和其他可以運(yùn)行這些算法的框架相比在合理的范圍內(nèi)，使用廉價(jià)的硬盤和普通的服務(wù)器就可以實(shí)現(xiàn)大規(guī)模的圖計(jì)算，并且有良好的性能，它可以像其他分布式框架一樣，在解決大規(guī)模社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)時(shí)有很好的運(yùn)行效率。

圖12 社區(qū)關(guān)系網(wǎng)絡(luò)

同時(shí)，Graphchi簡(jiǎn)單、高可用的性能使其在解決其他分布式系統(tǒng)能解決的大規(guī)模電信社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)方面也有很高的運(yùn)行效率，其在一定規(guī)模的圖數(shù)據(jù)量上的應(yīng)用前景不可限量。但是，隨著當(dāng)前信息時(shí)代數(shù)量的不斷擴(kuò)增，對(duì)圖數(shù)據(jù)處理的需求越來越高，Graphchi能否繼續(xù)承載更高數(shù)據(jù)量的分析處理任務(wù)仍然是一個(gè)問號(hào)，本文也提到了并行分布式框架在超大規(guī)模的社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)挖掘中，表現(xiàn)出強(qiáng)大的處理能力和效率，相信并行處理將是超大規(guī)模社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)處理發(fā)展的必然趨勢(shì)。

1 于戈，谷峪，鮑玉斌等.計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù).計(jì)算機(jī)學(xué)報(bào),2011(10)：1754～1755 Yu G,Gu Y,Bao Y B,et al.Large scale graph data processing on cloud computing environment.Chinese Journal of Computers,2011(10)：1754～1755

2 Malewicz G,Austern M H,Bik A J,et al.Pregel:a system for large-scale graph processing.Proceedings of SIGMOD ACM,Indianapolis,Indiana,2010

3 楊苗苗，李躍輝，劉靜等.基于Hadoop的電信頻繁交往圈算法研究.電腦知識(shí)與技術(shù)，2013(9)Yang M M,Li Y H,Liu Jing,et al.Research of algorithms about frequency telecom SNA based on Hadoop.Computer Knowledge and Technology,2013(9)

4 Stanford Large Network Dataset Collection.http://memetracker.org/data/,2014

5 SmallNetflix_mm.http://www.select.cs.cmu.edu/code/Graphlab/datasets/smallNetfli-x_mm,2014

6 Stanton I,Kliot G.Streaming graph partitioning for large distributed graphs.Technical report,Microsoft Research,2012

7 Kwak H,Lee C,Park H,et al.What is twitter,a social network or a news media.Proceedings of the 19th International Conference on World Wide Web,Raleigh,NC,USA,2010:591～600

8 Gonzalez J,Low Y,Gu H,et al.Powergraph:distributed graphparallel computation on natural graphs.Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation(OSDI’12),Hollywood,CA,USA,2012

9 Low Y,Gonzalez J,Kyrola A,et al.Graphlab:a distributed framework for machine learning in the cloud.Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence(UAI),Catalina Island,USA,2010

10 Zaharia M,Chowdhury M,Franklin M J,et al.Spark:cluster computing with working sets.Proceedings of HotCloud 2010,Boston,MA,June 2010

11 Seo S,Yoon E J,Kim J,et al.HAMA:an efficient matrix computation with the MapReduce framework.Proceedings of the IEEE 2nd International Conference on Cloud Computing Technology and Science,Washington,DC,USA,2010

12 Aapo Kyrola,Guy Blelloch,Carlos Guestrin.Graphchi:large-scale graph computation on just a PC.Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation(OSDI’12),Hollywood,CA,USA,2012

13 Suri S,Vassilvitskii S.Counting triangles and the curse of the last reducer.Proceedings of the 20th International Conference on World Wide Web,Hyderabad,India,2011:607～614

14 Bertsekas D P,Tsitsiklis J N.Parallel and distributed computation:numerical methods.Prentice-Hall Inc,1989

15 Leskovec J,Lang K,Dasgupta A,et al.Community structure in large networks:natural cluster sizes and the absence of large well-defined clusters.Internet Mathematics,2009,6(1):29～123

16 Zhu X,Ghahramani Z.Learning from labeled and unlabeled data with label propagation,2002

17 Kang U,Chau D,Faloutsos C.Inference of beliefs on billion-scale graphs.Proceedings of the 2nd Workshop on Large-scale Data Mining:Theory and Applications,Washington,DC,USA,2010

18 Gorton.Software architecture challenges for data intensive computing.Software Architecture,2008