社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)挖掘論文

社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)挖掘論文1相關(guān)工作1.1分布式框架下的圖計算工具1.1.1Pregel為了解決MapReduce在一些機(jī)器學(xué)習(xí)算法中性能瓶頸問題，Google針對大規(guī)模圖運(yùn)算提出了Pregel框架，它是嚴(yán)格的BSP〔bulksynchronousparallel〕模型〔BSP模型，即“大塊〞同步模型，其概念由哈fo大學(xué)的Valiant和牛津大學(xué)的BillMcColl提出，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步〕，采用“計算-通信-同步〞形式面向頂點(diǎn)的迭代方式完成機(jī)器學(xué)習(xí)的數(shù)據(jù)同步，這種靈敏的面向頂點(diǎn)的方法和高效的容錯機(jī)制的設(shè)計形式能夠描繪一系列的算法，并在有上千臺的計算節(jié)點(diǎn)的集群中得以實(shí)現(xiàn)。在集群環(huán)境中，從遠(yuǎn)程機(jī)器上讀取數(shù)據(jù)難以避免地會有延遲，Pregel選擇了一種純消息傳遞的形式，通過異步和批量的方式傳遞消息，通過分享內(nèi)存的方式，有效地緩解了遠(yuǎn)程讀取數(shù)據(jù)的延遲，提升了集群的性能，并且Pregel應(yīng)用一組抽象的API隱藏了分布式編程的相關(guān)細(xì)節(jié)，展現(xiàn)給使用者一個易編程和易使用的大型圖算法處理計算框架。但是Google一直沒有將Pregel的詳細(xì)實(shí)現(xiàn)開源，外界對Pregel的模擬實(shí)如今性能和穩(wěn)定性方面都未能到達(dá)工業(yè)級應(yīng)用的標(biāo)準(zhǔn)。同時，在圖計算中，由于圖的頂點(diǎn)、邊密度的不平衡性的特點(diǎn)，帶來BSP模型的“木桶效應(yīng)〞〔木桶效應(yīng)是由美國管理學(xué)家彼得提出的，本文指的是先完成的任務(wù)需要等待后完成的任務(wù)，處理速度最慢的任務(wù)將成為整個系統(tǒng)的效率制約瓶頸〕的限制，網(wǎng)絡(luò)、計算機(jī)硬件中的差異性也會使這種現(xiàn)象愈加明顯。1.1.2SparkSpark是UCBerkeleyAMP實(shí)驗(yàn)室開發(fā)的通用的并行計算框架，是Pregel的優(yōu)化模型，它是基于MapReduce算法實(shí)現(xiàn)的分布式計算框架。Spark擁有MapReduce所具有的優(yōu)點(diǎn)，但不同于MapReduce的是，Spark采用了一種彈性分布式數(shù)據(jù)集〔resilientdistributeddataset，RDD〕的抽象數(shù)據(jù)構(gòu)造，Spark是一個基于內(nèi)存計算的開源的集群計算系統(tǒng)。RDD是一個具有容錯機(jī)制的特殊集合，它提供了一種抽象的數(shù)據(jù)架構(gòu)，使用RDD邏輯轉(zhuǎn)換而來的可重復(fù)使用的分享內(nèi)存，而不再需要反復(fù)讀寫HDFS，解決了MapReduce框架在迭代計算式中要進(jìn)行大量磁盤I/O操作的問題，這讓數(shù)據(jù)分析愈加快速，為構(gòu)建低延遲的并行性大數(shù)據(jù)分析處理框架提供了穩(wěn)定的基礎(chǔ)。同時，Spark提供了REPL〔read-eval-printloop〕的交互式查詢以及函數(shù)式編程，支持圍繞RDD抽象的API，同時包括一套transformation〔轉(zhuǎn)化〕和action〔動作〕操作以及針對大量流行編程語言的支持，比方Scala、Java和Python。在圖計算方面，Spark原生的Bagel以及Graphx提供了對于圖操作的API，為大規(guī)模的圖計算提供了低延遲，負(fù)責(zé)優(yōu)化交互式的大規(guī)模并行處理框架，但是Spark的磁盤索引是簡單的靜態(tài)機(jī)制，無法隨著迭代狀態(tài)的變化而動態(tài)優(yōu)化。1.1.3GraphlabGraphlab是CMU的Select實(shí)驗(yàn)室提出的基于內(nèi)存分享機(jī)制且面向機(jī)器學(xué)習(xí)的流處理并行框架，它的分布式處理是基于MPI〔messagepassinginterface，消息傳遞接口〕實(shí)現(xiàn)的，并且將數(shù)據(jù)抽象成圖構(gòu)造，它是以圖的頂點(diǎn)為計算單元的大規(guī)模圖處理系統(tǒng)，支持稀疏的計算依靠異步迭代計算等，解決了MapReduce不適應(yīng)需要頻繁數(shù)據(jù)交換的迭代機(jī)器學(xué)習(xí)算法問題，是繼Google的Pregel之后的第一個開源的大規(guī)模圖處理系統(tǒng)。Graphlab的核心思想是“以圖頂點(diǎn)的方式考慮問題〞，以最小化集群計算節(jié)點(diǎn)之間的通信量和平衡計算節(jié)點(diǎn)上的計算和存儲資源為原則，對圖的頂點(diǎn)進(jìn)行切分。類似于MapReduce中的map和reduce經(jīng)過，它將機(jī)器學(xué)習(xí)抽象成GAS〔gather〔收集〕、apply〔運(yùn)算〕、scatter〔更新〕〕3個步驟，然后按該抽象模型設(shè)計頂點(diǎn)程序?qū)崿F(xiàn)算法。在gather階段，當(dāng)前點(diǎn)收集鄰接點(diǎn)和邊的值，結(jié)合本身的值，進(jìn)行簡單的用戶定義的sum〔求和〕操作；在apply階段，當(dāng)前點(diǎn)根據(jù)sum得到的值及其前一時刻本身的值計算新的點(diǎn)值；scatter階段當(dāng)前點(diǎn)利用本人的新值，結(jié)合鄰接點(diǎn)/邊前一時刻的值來計算鄰接邊的新值，并更新鄰接邊。GraphLab的算法被應(yīng)用于很多推薦系統(tǒng)，也包括銀行的欺詐偵測和電腦網(wǎng)絡(luò)中的入侵偵測等領(lǐng)域。1.1.4PowerGraphPowerGraph是卡內(nèi)基梅隆大學(xué)設(shè)計的一種強(qiáng)大的圖計算分布式并行框架，它結(jié)合了Graphlab和Pregel關(guān)于圖計算的優(yōu)點(diǎn)，有效改善了Pregel和Graphlab等框架的并行化受限于頂點(diǎn)的鄰居個數(shù)的問題?，F(xiàn)實(shí)世界中的圖，都是典型的Power-Law〔冪律〕分布圖，其中少部分頂點(diǎn)連接到圖中大部分的頂點(diǎn)上，這種圖的劃分對于并行的分布式框架來講是一個非常大的難題，并且圖的劃分效率直接影響系統(tǒng)的通信開銷。一般的并行框架采用的是散列隨機(jī)分配方案，但這種方案沒有考慮局部性，劃分完成后各任務(wù)負(fù)責(zé)的子圖之間的強(qiáng)耦合性導(dǎo)致后續(xù)的迭代計算經(jīng)過產(chǎn)生大量的消息通信，嚴(yán)重影響負(fù)載平衡。PowerGraph使用了支持同步處理和異步處理機(jī)制的GAS模型，并且提出了一種P-路頂點(diǎn)切割分區(qū)方案，在減少計算中通信量的同時保證了負(fù)載平衡，很好地解決了圖的Power-Law問題。1.2單機(jī)圖計算工具——Graphchi除了以上介紹的分布式圖計算框架外，還能夠使用單機(jī)的圖算法庫，如BGL、LEAD、NetworkX、JDSL、StandfordGraphBase、FGL等進(jìn)行圖的挖掘和計算，但這種單機(jī)的方式由于內(nèi)存限制的原因，對圖本身的規(guī)模有了很大的限制[2]。為解決單機(jī)圖計算的內(nèi)存瓶頸問題，卡內(nèi)基梅隆大學(xué)的Select實(shí)驗(yàn)室開發(fā)了Graphchi，它是Graphlab的一個分支，采用基于磁盤的以頂點(diǎn)為中心的計算模型，它能夠在PC上進(jìn)行大規(guī)模的類似于社會網(wǎng)絡(luò)分析的圖計算，而不需要分布式的集群和云服務(wù)，也不需要考慮內(nèi)存的限制。1.2.1基于磁盤的計算要想利用單機(jī)而不利用集群來并行地進(jìn)行大規(guī)模的圖計算，首當(dāng)其沖面臨的是存儲問題。龐大的圖數(shù)據(jù)在內(nèi)存中處理上百萬條邊需要幾十或幾百吉字節(jié)的DRAM，由于其價格昂貴，目前只對高端服務(wù)器有可用性，所以Graphchi將目光投向了價格低廉、容量大的磁盤作為其外部存儲，用基于磁盤的計算模型減少內(nèi)存的使用和隨機(jī)存取問題。然而，怎樣從磁盤上處理大規(guī)模的圖數(shù)據(jù)是一個難題。為了處理這個問題，Graphchi采用了新穎的PSW〔parallelslidingwindow，并行式滑動窗口〕模型，從磁盤上處理大的圖數(shù)據(jù)。1.2.2PSW模型Graphchi采用了PSW模型從磁盤處理大的圖數(shù)據(jù)，不同于分布式框架通用的BSP模型，PSW模型能夠異步處理存儲在硬盤上的可擴(kuò)展圖數(shù)據(jù)，有效躲避了“木桶效應(yīng)〞。PSW模型中，邊的信息分區(qū)shard采用不相交子集〔頂點(diǎn)集被分為P個子集interval(i)〕的形式關(guān)聯(lián)存儲，這種存儲方式將每個子集以滑動窗口的形式分別從硬盤裝入內(nèi)存。Graphchi分屢次取節(jié)點(diǎn)子集interval(i)，每次取1個，并且根據(jù)節(jié)點(diǎn)子集中的點(diǎn)信息構(gòu)造子圖進(jìn)行計算。在第p次操作所需的子圖數(shù)據(jù)載入后，每個節(jié)點(diǎn)并行地執(zhí)行用戶定義的更新函數(shù)，并更新節(jié)點(diǎn)，節(jié)點(diǎn)子集更新后的塊文件將被寫入磁盤。圖2表示PSW模型進(jìn)行一次迭代的滑動窗口示意，頂點(diǎn)被分為4個不相交的子集，每個本人都關(guān)聯(lián)一個分區(qū)，計算經(jīng)過是構(gòu)建一次子圖頂點(diǎn)的子集。從內(nèi)存的分區(qū)中讀取頂點(diǎn)的入邊，從每個滑動的分區(qū)中讀取出邊，每個分區(qū)的最頂端為當(dāng)前的滑動窗口。1.2.3Graphchi基于PSW模型的改良為了支持Graphchi的可擴(kuò)展性，Graphchi對PSW模型進(jìn)行了改良，通過實(shí)現(xiàn)一個簡化的、高效的I/O緩存樹來支持圖邊的增加和刪除，改良的PSW模型如圖3所示。2Graphchi應(yīng)用前景2.1分布式圖計算局限性基于圖的分布式框架通過云平臺的計算資源處理上百萬條邊的圖數(shù)據(jù)有很高的效率，但是利用分布式集群進(jìn)行圖計算仍然面臨較高的硬件和技術(shù)要求，對于那些沒有分布式專業(yè)背景、沒有足夠的硬件資源的人來講，仍然是個宏大的挑戰(zhàn)。首先，使用分布式框架時，使用者面臨怎樣將強(qiáng)耦合性的圖數(shù)據(jù)進(jìn)行分割，部署到集群計算節(jié)點(diǎn)上的問題[3]。其次，圖的分布式計算涉及復(fù)雜的處理經(jīng)過，需要大量的迭代和數(shù)據(jù)通信，大多數(shù)分布式系統(tǒng)用到的是BSP模型，是一種同步計算模型，對于消息的處理容量有限，網(wǎng)絡(luò)的延遲以及節(jié)點(diǎn)間的通信會造成“木桶效應(yīng)〞。再次，分布式框架處理需要計算耗時的大規(guī)模圖數(shù)據(jù)時，重復(fù)計算以及系統(tǒng)故障使效率大大降低，同時系統(tǒng)的容錯性也是制約運(yùn)算效率和穩(wěn)定性的關(guān)鍵瓶頸。最后，對于編程者來講，調(diào)試和優(yōu)化分布式算法有很大的難度。相對于復(fù)雜的分布式集群框架來講，簡單的單機(jī)進(jìn)行大規(guī)模的圖計算，能夠躲避分布式框架的問題。使用者不需考慮強(qiáng)耦合性的圖數(shù)據(jù)怎樣分割放置到分布式的集群節(jié)點(diǎn)中，也不需管理和部署諸多的集群節(jié)點(diǎn)，并且能夠減少分布式集群節(jié)點(diǎn)中的通信開銷，躲避網(wǎng)絡(luò)延遲、“木桶效應(yīng)〞等問題。例如，企業(yè)假如想要在同一張圖上計算多種任務(wù)〔個性化推薦、圖的社團(tuán)發(fā)現(xiàn)等〕，在不同的國家、不同的利益集團(tuán)都要計算同一個任務(wù)的情況下，企業(yè)要想提高運(yùn)算速度，就必需要增加集群節(jié)點(diǎn)，也就是講要增加成本。但是，假如一臺機(jī)器上能夠處理一個這樣的大任務(wù)，企業(yè)能夠?yàn)槊颗_機(jī)器分配一個任務(wù)，每臺機(jī)器之間無需相互通信，當(dāng)增加機(jī)器數(shù)量時，吞吐量也隨之增加，這樣多種任務(wù)的處理將會變得非常簡單、有效。僅僅需要一臺機(jī)器就能夠?qū)Υ笠?guī)模的圖數(shù)據(jù)進(jìn)行分析處理和挖掘，這能夠大大簡化分布式集群處理框架的復(fù)雜性，如圖5所示。本文對單機(jī)處理圖數(shù)據(jù)技術(shù)Graphchi的發(fā)展、應(yīng)用場景以及性能進(jìn)行了研究，并進(jìn)行了試驗(yàn)。2.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ù)雜的信息中找出可向用戶推薦的有價值的信息。不僅在圖挖掘和協(xié)同過濾方面，Graphchi還提供了通用的編程框架，支持使用者調(diào)用本人的算法對圖進(jìn)行分析和計算，這使得Graphchi使用起來愈加靈敏，也有愈加個性化的可用性。當(dāng)前Graphchi中一些應(yīng)用的算法設(shè)計還不盡完善，但是隨著技術(shù)的發(fā)展以及應(yīng)用的普及，Graphchi因其在圖計算方面獨(dú)特的模型，其單機(jī)運(yùn)行的簡便、高可用和可觀的運(yùn)行效率，將在大規(guī)模圖計算方面表現(xiàn)出越來越廣闊的應(yīng)用前景。為了驗(yàn)證Graphchi在不同硬件環(huán)境下，不同數(shù)量級別社交網(wǎng)絡(luò)圖數(shù)據(jù)應(yīng)用中的可行性和可用性，下文對不同數(shù)量級的數(shù)據(jù)在兩種不同的環(huán)境進(jìn)行了相應(yīng)的測試，并且和其他分布式框架進(jìn)行了比照。3Graphchi的可行性、可用性評估實(shí)驗(yàn)3.1測試環(huán)境Intel(R)Core(TM)2DuoCPUT66002.20GHz、RAM2GB、Ubuntu11.04。Dell服務(wù)器QEMUVirtualCPUVersion(cpu64-rhel6)6核CPU、4GB內(nèi)存〔未特殊注明，本文中數(shù)據(jù)測試環(huán)境均為服務(wù)器環(huán)境〕、CentOS6.4。3.2數(shù)據(jù)集講明本文采用的數(shù)據(jù)集來自斯坦福的Snap網(wǎng)站[4]以及Netflix網(wǎng)站。測試的數(shù)據(jù)集為Wiki、Twitter、Facebook、Friendster等流行的社交網(wǎng)站，數(shù)據(jù)集大小為40MB~30GB。表1是對實(shí)驗(yàn)中使用到的測試數(shù)據(jù)集的講明，其中V表示測試數(shù)據(jù)集的頂點(diǎn)數(shù)目，E表示測試數(shù)據(jù)集邊的數(shù)目。3.3Graphchi測試結(jié)果圖6表示的是PageRank和CommunityDetection兩種算法對除Netflix數(shù)據(jù)集外所有數(shù)據(jù)集進(jìn)行的測試，X軸表示邊集的數(shù)量，Y軸表示對應(yīng)的運(yùn)行時間。從圖中能夠看出，對于兩種不同算法，隨著數(shù)據(jù)集的增大，運(yùn)行時間大體呈線性增長。圖7表示PageRank和CommunityDetection兩種算法以及CommunityDetection分別在4次和10次迭代經(jīng)過中，吞吐量隨邊數(shù)的變化。X軸為邊集的數(shù)量，Y軸表示吞吐量〔系統(tǒng)每秒處理邊的數(shù)量〕。Graphchi每秒能夠處理的邊的數(shù)量為0.2×106~2×106個。Graphchi測試Twitter2010年所有的user-follower關(guān)系，14億條邊、4千萬個頂點(diǎn)共20GB的數(shù)據(jù)，PageRank算法需要46min，CommunityDetection算法10次迭代需要70min，Trianglecounting算法需要130min；測試在線游戲Friendster，18億個頂點(diǎn)、6千萬條邊共30GB的數(shù)據(jù)集com-friendster.ungraph，PageRank算法4次迭代需要54min?？梢?，Graphchi能夠在1h左右完成對社交網(wǎng)絡(luò)一年數(shù)據(jù)的分析。這種處理能力完全能夠知足使用者對大規(guī)模圖數(shù)據(jù)進(jìn)行計算的需求，并且具有較好的吞吐量。圖8表示的是Graphchi測試兩種數(shù)據(jù)集smallNetflix和Netflix協(xié)同過濾的7種算法進(jìn)行6次迭代的運(yùn)行時間。X軸表示7種協(xié)同過濾算法：SGD、ALS、RBM、SVD++、biasSGD、CCD++和PMF，Y軸對應(yīng)的是各種算法的運(yùn)行時間。Graphchi在協(xié)同過濾中的運(yùn)行時間最長為450s，Netflix數(shù)據(jù)集的時間不超過300s。圖9表示的是SGD算法運(yùn)行50次迭代的運(yùn)行時間以及RSME〔rootsquaremeanerror〕均方差的變化曲線。迭代20次時，算法的RSME已經(jīng)趨于穩(wěn)定，無限接近于0.92，而此時的運(yùn)行時間約為350s?？梢?，Graphchi在協(xié)同過濾方面表現(xiàn)出良好的性能，能夠在幾百秒的時間內(nèi)處理2GB規(guī)模的數(shù)據(jù)。圖10表示的是PageRank、CommunityDetection和ConnectedComponents3種算法，wiki-Talk和com-orkut兩種測試集分別在2核CPU和6核CPU上運(yùn)行時間的比照。X軸表示運(yùn)行時間，Y軸表示3種算法以及兩種數(shù)據(jù)集。從圖10中能夠看出，在一樣數(shù)據(jù)集上6核CPU的運(yùn)行時間要比2核CPU運(yùn)行時間快了近10倍。圖11表示的是協(xié)同過濾的3種算法，Netflix測試集分別在2核CPU和6核CPU上運(yùn)行時間的比照。X軸表示運(yùn)行時間，Y軸表示協(xié)同過濾4種不同算法。Netflix數(shù)據(jù)集在6核CPU上的運(yùn)行時間比在2核CPU上的運(yùn)行時間快了5~10倍。圖11表示協(xié)同過濾4種算法在不同核數(shù)CPU運(yùn)行時間的比照。隨著CPU數(shù)目的增加，運(yùn)行速度也有明顯的提升。相信在配置更高的單機(jī)上運(yùn)行Graphchi將會有愈加可觀的性能。3.4可行性、可用性分析比照本文比照了一些分布式的圖處理框架，參考了一些其他文章的測試結(jié)果，見表2。在有50個節(jié)點(diǎn)、100個CPU的Spark框架下，在Twitter-2010數(shù)據(jù)集上運(yùn)行5次迭代的PageRank算法的時間比Graphchi在4核CPU的環(huán)境中運(yùn)行一樣數(shù)據(jù)集快了大約5倍。在有1636個節(jié)點(diǎn)的Hadoop框架運(yùn)行Twitter-2010數(shù)據(jù)集的PageRank算法迭代一次，Graphchi比Hadoop快45倍，比Powergraph慢了155倍。與運(yùn)行在AMD服務(wù)器上的Graphlab相比，用ALS算法測試Netflix數(shù)據(jù)集，Graphchi運(yùn)行時間是Graphlab的2.5倍。Trianglecounting算法測試Twitter-2010數(shù)據(jù)集在1636個節(jié)點(diǎn)的Hadoop環(huán)境，Graphchi比Hadoop快了3倍。相對于Hadoop來講，Graphchi的大規(guī)模圖數(shù)據(jù)方面的性能遠(yuǎn)優(yōu)于Hadoop；在協(xié)同過濾方面，Graphchi和Graphlab性能相差不大；與性能較好的Spark相比，Graphchi的性能表現(xiàn)也在能夠接受的范圍內(nèi)；對于性能強(qiáng)大的Powergraph，Graphchi性能還是有一些差距?？傮w來講，Graphchi以單機(jī)運(yùn)行方式進(jìn)行圖運(yùn)算所表現(xiàn)出的性能能夠和一些分布式的框架相媲美，固然不及性能強(qiáng)大的Powergraph，但是這樣的性能表現(xiàn)已經(jīng)能夠知足一定規(guī)模的圖運(yùn)算了。這樣的性能表現(xiàn)已足以為成本缺乏、硬件設(shè)備配置不高的中小企業(yè)或者個人提供高可行、高可用的社交關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)分析和挖掘平臺。4Graphchi電信圖數(shù)據(jù)挖掘應(yīng)用為驗(yàn)證Graphchi對電信大規(guī)模圖數(shù)據(jù)的處理能力，本文構(gòu)造了電信通話清單數(shù)據(jù)約20GB，有4000萬個頂點(diǎn)、14億條邊〔已對數(shù)據(jù)進(jìn)行匿名處理〕，格式見表3。4.1PageRank算法挖掘核心人物PageRank算法是Google用于用來標(biāo)識網(wǎng)頁的等級/重要性的一種方法，是Google用來衡量一個網(wǎng)站好壞的唯一標(biāo)準(zhǔn)。它基于馬爾科夫狀態(tài)轉(zhuǎn)移理論，通過網(wǎng)頁的鏈入數(shù)對網(wǎng)頁進(jìn)行投票來得出重要性排名。發(fā)展到目前，PageRank算法也被廣泛用于關(guān)鍵人物挖掘等社交關(guān)系網(wǎng)絡(luò)分析中。本文應(yīng)用Graphchi的Pagerank算法，對電信關(guān)系網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行Rank值的計算，進(jìn)而找出關(guān)鍵人物。表4是采用Graphchi的Pagerank算法對電信數(shù)據(jù)集進(jìn)行計算Rank值的排名前10的結(jié)果，在4000萬個用戶中，標(biāo)號為1653的用戶的重要性最高，為核心用戶，應(yīng)該對