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

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

1 引言

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

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

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

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

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

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

2 相關(guān)工作

2.1 分布式框架下的圖計算工具

2.1.1 Pregel

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

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

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

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

2.1.2 Spark

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

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

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

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

2.1.3 Graphlab

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

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

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

2.1.4 PowerGraph

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

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

2.2 單機圖計算工具——Graphchi

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

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

2.2.1 基于磁盤的計算

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

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

2.2.2 PSW模型

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

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

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

2.2.3 Graphchi基于PSW模型的改進

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

圖3 改進的PSW模型

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

圖4 Graphchi流程

3 Graphchi應(yīng)用前景

3.1 分布式圖計算局限性

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

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

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

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

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

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

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

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

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

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

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

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

4 Graphchi的可行性、可用性評估實驗

4.1 測試環(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ù)測試環(huán)境均為服務(wù)器環(huán)境）、CentOS 6.4。

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

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

表1是對實驗中使用到的測試數(shù)據(jù)集的說明，其中|V|表示測試數(shù)據(jù)集的頂點數(shù)目，|E|表示測試數(shù)據(jù)集邊的數(shù)目。

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

4.3 Graphchi測試結(jié)果

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

圖6 兩種算法隨邊規(guī)模增長運行時間變化

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

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

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

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

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

圖8 協(xié)同過濾算法運行時間

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

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

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

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

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

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

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

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

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

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

4.4 可行性、可用性分析對比

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

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

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

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

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

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

表2 Graphchi和不同框架性能對比

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

5.1 PageRank算法挖掘核心人物

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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

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

1 于戈，谷峪，鮑玉斌等.計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù).計算機學(xué)報,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ù)，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