本站小編為你精心準備了社交關系網絡圖數據挖掘論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1相關工作

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

1.1.1Pregel為了解決MapReduce在一些機器學習算法中性能瓶頸問題，Google針對大規模圖運算提出了Pregel框架，它是嚴格的BSP（bulksynchronousparallel）模型（BSP模型，即“大塊”同步模型，其概念由哈佛大學的Valiant和牛津大學的BillMcColl提出，是一種異步MIMD-DM模型，支持消息傳遞系統，塊內異步并行，塊間顯式同步），采用“計算-通信-同步”模式面向頂點的迭代方式完成機器學習的數據同步，這種靈活的面向頂點的方法和高效的容錯機制的設計模式可以描述一系列的算法，并在有上千臺的計算節點的集群中得以實現。在集群環境中，從遠程機器上讀取數據難以避免地會有延遲，Pregel選擇了一種純消息傳遞的模式，通過異步和批量的方式傳遞消息，通過共享內存的方式，有效地緩解了遠程讀取數據的延遲，提升了集群的性能，并且Pregel應用一組抽象的API隱藏了分布式編程的相關細節，展現給使用者一個易編程和易使用的大型圖算法處理計算框架。但是Google一直沒有將Pregel的具體實現開源，外界對Pregel的模仿實現在性能和穩定性方面都未能達到工業級應用的標準。同時，在圖計算中，由于圖的頂點、邊密度的不平衡性的特點，帶來BSP模型的“木桶效應”（木桶效應是由美國管理學家彼得提出的，本文指的是先完成的任務需要等待后完成的任務，處理速度最慢的任務將成為整個系統的效率制約瓶頸）的限制，網絡、計算機硬件中的差異性也會使這種現象更加明顯。

1.1.2SparkSpark是UCBerkeleyAMP實驗室開發的通用的并行計算框架，是Pregel的優化模型，它是基于MapReduce算法實現的分布式計算框架。Spark擁有MapReduce所具有的優點，但不同于MapReduce的是，Spark采用了一種彈性分布式數據集（resilientdistributeddataset，RDD）的抽象數據結構，Spark是一個基于內存計算的開源的集群計算系統。RDD是一個具有容錯機制的特殊集合，它提供了一種抽象的數據架構，使用RDD邏輯轉換而來的可重復使用的共享內存，而不再需要反復讀寫HDFS，解決了MapReduce框架在迭代計算式中要進行大量磁盤I/O操作的問題，這讓數據分析更加快速，為構建低延遲的并行性大數據分析處理框架提供了穩定的基礎。同時，Spark提供了REPL（read-eval-printloop）的交互式查詢以及函數式編程，支持圍繞RDD抽象的API，同時包括一套transformation（轉化）和action（動作）操作以及針對大量流行編程語言的支持，比如Scala、Java和Python。在圖計算方面，Spark原生的Bagel以及Graphx提供了對于圖操作的API，為大規模的圖計算提供了低延遲，負責優化交互式的大規模并行處理框架，但是Spark的磁盤索引是簡單的靜態機制，無法隨著迭代狀態的變化而動態優化。

1.1.3GraphlabGraphlab是CMU的Select實驗室提出的基于內存共享機制且面向機器學習的流處理并行框架，它的分布式處理是基于MPI（messagepassinginterface，消息傳遞接口）實現的，并且將數據抽象成圖結構，它是以圖的頂點為計算單元的大規模圖處理系統，支持稀疏的計算依賴異步迭代計算等，解決了MapReduce不適應需要頻繁數據交換的迭代機器學習算法問題，是繼Google的Pregel之后的第一個開源的大規模圖處理系統。Graphlab的核心思想是“以圖頂點的方式思考問題”，以最小化集群計算節點之間的通信量和均衡計算節點上的計算和存儲資源為原則，對圖的頂點進行切分。類似于MapReduce中的map和reduce過程，它將機器學習抽象成GAS（gather（收集）、apply（運算）、scatter（更新））3個步驟，然后按該抽象模型設計頂點程序實現算法。在gather階段，當前點收集鄰接點和邊的值，結合自身的值，進行簡單的用戶定義的sum（求和）操作；在apply階段，當前點根據sum得到的值及其前一時刻自身的值計算新的點值；scatter階段當前點利用自己的新值，結合鄰接點/邊前一時刻的值來計算鄰接邊的新值，并更新鄰接邊。GraphLab的算法被應用于很多推薦系統，也包括銀行的欺詐偵測和電腦網絡中的入侵偵測等領域。

1.1.4PowerGraphPowerGraph是卡內基梅隆大學設計的一種強大的圖計算分布式并行框架，它結合了Graphlab和Pregel關于圖計算的優點，有效改善了Pregel和Graphlab等框架的并行化受限于頂點的鄰居個數的問題。現實世界中的圖，都是典型的Power-Law（冪律）分布圖，其中少部分頂點連接到圖中大部分的頂點上，這種圖的劃分對于并行的分布式框架來說是一個非常大的難題，并且圖的劃分效率直接影響系統的通信開銷。一般的并行框架采用的是散列隨機分配方案，但這種方案沒有考慮局部性，劃分完成后各任務負責的子圖之間的強耦合性導致后續的迭代計算過程產生大量的消息通信，嚴重影響負載均衡。PowerGraph使用了支持同步處理和異步處理機制的GAS模型，并且提出了一種P-路頂點切割分區方案，在減少計算中通信量的同時保證了負載均衡，很好地解決了圖的Power-Law問題。

1.2單機圖計算工具——Graphchi除了以上介紹的分布式圖計算框架外，還可以使用單機的圖算法庫，如BGL、LEAD、NetworkX、JDSL、StandfordGraphBase、FGL等進行圖的挖掘和計算，但這種單機的方式由于內存限制的原因，對圖本身的規模有了很大的限制[2]。為解決單機圖計算的內存瓶頸問題，卡內基梅隆大學的Select實驗室開發了Graphchi，它是Graphlab的一個分支，采用基于磁盤的以頂點為中心的計算模型，它可以在PC上進行大規模的類似于社會網絡分析的圖計算，而不需要分布式的集群和云服務，也不需要考慮內存的限制。

1.2.1基于磁盤的計算要想利用單機而不利用集群來并行地進行大規模的圖計算，首當其沖面臨的是存儲問題。龐大的圖數據在內存中處理上百萬條邊需要幾十或幾百吉字節的DRAM，因為其價格昂貴，目前只對高端服務器有可用性，所以Graphchi將目光投向了價格低廉、容量大的磁盤作為其外部存儲，用基于磁盤的計算模型減少內存的使用和隨機存取問題。然而，如何從磁盤上處理大規模的圖數據是一個難題。為了處理這個問題，Graphchi采用了新穎的PSW（parallelslidingwindow，并行式滑動窗口）模型，從磁盤上處理大的圖數據。

1.2.2PSW模型Graphchi采用了PSW模型從磁盤處理大的圖數據，不同于分布式框架通用的BSP模型，PSW模型能夠異步處理存儲在硬盤上的可擴展圖數據，有效規避了“木桶效應”。PSW模型中，邊的信息分區shard采用不相交子集（頂點集被分為P個子集interval(i)）的形式關聯存儲，這種存儲方式將每個子集以滑動窗口的形式分別從硬盤裝入內存。Graphchi分多次取節點子集interval(i)，每次取1個，并且根據節點子集中的點信息構造子圖進行計算。在第p次操作所需的子圖數據載入后，每個節點并行地執行用戶定義的更新函數，并更新節點，節點子集更新后的塊文件將被寫入磁盤。圖2表示PSW模型進行一次迭代的滑動窗口示意，頂點被分為4個不相交的子集，每個自己都關聯一個分區，計算過程是構建一次子圖頂點的子集。從內存的分區中讀取頂點的入邊，從每個滑動的分區中讀取出邊，每個分區的最頂端為當前的滑動窗口。

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

2Graphchi應用前景

2.1分布式圖計算局限性基于圖的分布式框架通過云平臺的計算資源處理上百萬條邊的圖數據有很高的效率，但是利用分布式集群進行圖計算仍然面臨較高的硬件和技術要求，對于那些沒有分布式專業背景、沒有足夠的硬件資源的人來說，仍然是個巨大的挑戰。首先，使用分布式框架時，使用者面臨如何將強耦合性的圖數據進行分割，部署到集群計算節點上的問題[3]。其次，圖的分布式計算涉及復雜的處理過程，需要大量的迭代和數據通信，大多數分布式系統用到的是BSP模型，是一種同步計算模型，對于消息的處理容量有限，網絡的延遲以及節點間的通信會造成“木桶效應”。再次，分布式框架處理需要計算耗時的大規模圖數據時，重復計算以及系統故障使效率大大降低，同時系統的容錯性也是制約運算效率和穩定性的關鍵瓶頸。最后，對于編程者來說，調試和優化分布式算法有很大的難度。相對于復雜的分布式集群框架來說，簡單的單機進行大規模的圖計算，能夠規避分布式框架的問題。使用者不需考慮強耦合性的圖數據如何分割放置到分布式的集群節點中，也不需管理和部署眾多的集群節點，并且可以減少分布式集群節點中的通信開銷，規避網絡延遲、“木桶效應”等問題。例如，企業如果想要在同一張圖上計算多種任務（個性化推薦、圖的社團發現等），在不同的國家、不同的利益集團都要計算同一個任務的情況下，企業要想提高運算速度，就必須要增加集群節點，也就是說要增加成本。但是，如果一臺機器上可以處理一個這樣的大任務，企業可以為每臺機器分配一個任務，每臺機器之間無需互相通信，當增加機器數量時，吞吐量也隨之增加，這樣多種任務的處理將會變得非常簡單、有效。僅僅需要一臺機器就可以對大規模的圖數據進行分析處理和挖掘，這可以大大簡化分布式集群處理框架的復雜性，如圖5所示。本文對單機處理圖數據技術Graphchi的發展、應用場景以及性能進行了研究，并進行了試驗。

2.2單機Graphchi應用前景在圖挖掘方面，Graphchi實現了PageRank、連通分支、社區發現等算法處理和分析現實世界中大規模的圖數據；另外，應用在協同過濾算法的推薦系統中，Graphchi從紛繁復雜的信息中找出可向用戶推薦的有價值的信息。不僅在圖挖掘和協同過濾方面，Graphchi還提供了通用的編程框架，支持使用者調用自己的算法對圖進行分析和計算，這使得Graphchi使用起來更加靈活，也有更加個性化的可用性。當前Graphchi中一些應用的算法設計還不盡完善，但是隨著技術的發展以及應用的普及，Graphchi因其在圖計算方面獨特的模型，其單機運行的簡便、高可用和可觀的運行效率，將在大規模圖計算方面表現出越來越廣闊的應用前景。為了驗證Graphchi在不同硬件環境下，不同數量級別社交網絡圖數據應用中的可行性和可用性，下文對不同數量級的數據在兩種不同的環境進行了相應的測試，并且和其他分布式框架進行了對比。

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

3.1測試環境•Intel(R)Core(TM)[email protected]、RAM2GB、Ubuntu11.04。•Dell服務器QEMUVirtualCPUVersion(cpu64-rhel6)6核CPU、4GB內存（未特殊注明，本文中數據測試環境均為服務器環境）、CentOS6.4。

3.2數據集說明本文采用的數據集來自斯坦福的Snap網站[4]以及Netflix網站。測試的數據集為Wiki、Twitter、Facebook、Friendster等流行的社交網站，數據集大小為40MB~30GB。表1是對實驗中使用到的測試數據集的說明，其中|V|表示測試數據集的頂點數目，|E|表示測試數據集邊的數目。

3.3Graphchi測試結果圖6表示的是PageRank和CommunityDetection兩種算法對除Netflix數據集外所有數據集進行的測試，X軸表示邊集的數量，Y軸表示對應的運行時間。從圖中可以看出，對于兩種不同算法，隨著數據集的增大，運行時間大體呈線性增長。圖7表示PageRank和CommunityDetection兩種算法以及CommunityDetection分別在4次和10次迭代過程中，吞吐量隨邊數的變化。X軸為邊集的數量，Y軸表示吞吐量（系統每秒處理邊的數量）。Graphchi每秒可以處理的邊的數量為0.2×106~2×106個。Graphchi測試Twitter2010年所有的user-follower關系，14億條邊、4千萬個頂點共20GB的數據，PageRank算法需要46min，CommunityDetection算法10次迭代需要70min，Trianglecounting算法需要130min；測試在線游戲Friendster，18億個頂點、6千萬條邊共30GB的數據集com-friendster.ungraph，PageRank算法4次迭代需要54min。可見，Graphchi可以在1h左右完成對社交網絡一年數據的分析。這種處理能力完全可以滿足使用者對大規模圖數據進行計算的需求，并且具有較好的吞吐量。圖8表示的是Graphchi測試兩種數據集smallNetflix和Netflix協同過濾的7種算法進行6次迭代的運行時間。X軸表示7種協同過濾算法：SGD、ALS、RBM、SVD++、biasSGD、CCD++和PMF，Y軸對應的是各種算法的運行時間。Graphchi在協同過濾中的運行時間最長為450s，Netflix數據集的時間不超過300s。圖9表示的是SGD算法運行50次迭代的運行時間以及RSME（rootsquaremeanerror）均方差的變化曲線。迭代20次時，算法的RSME已經趨于穩定，無限接近于0.92，而此時的運行時間約為350s。可見，Graphchi在協同過濾方面表現出良好的性能，可以在幾百秒的時間內處理2GB規模的數據。圖10表示的是PageRank、CommunityDetection和ConnectedComponents3種算法，wiki-Talk和com-orkut兩種測試集分別在2核CPU和6核CPU上運行時間的對比。X軸表示運行時間，Y軸表示3種算法以及兩種數據集。從圖10中可以看出，在相同數據集上6核CPU的運行時間要比2核CPU運行時間快了近10倍。圖11表示的是協同過濾的3種算法，Netflix測試集分別在2核CPU和6核CPU上運行時間的對比。X軸表示運行時間，Y軸表示協同過濾4種不同算法。Netflix數據集在6核CPU上的運行時間比在2核CPU上的運行時間快了5~10倍。圖11表示協同過濾4種算法在不同核數CPU運行時間的對比。隨著CPU數目的增加，運行速度也有明顯的提升。相信在配置更高的單機上運行Graphchi將會有更加可觀的性能。

3.4可行性、可用性分析對比本文對比了一些分布式的圖處理框架，參考了一些其他文章的測試結果，見表2。在有50個節點、100個CPU的Spark框架下，在Twitter-2010數據集上運行5次迭代的PageRank算法的時間比Graphchi在4核CPU的環境中運行相同數據集快了大約5倍。在有1636個節點的Hadoop框架運行Twitter-2010數據集的PageRank算法迭代一次，Graphchi比Hadoop快45倍，比Powergraph慢了155倍。與運行在AMD服務器上的Graphlab相比，用ALS算法測試Netflix數據集，Graphchi運行時間是Graphlab的2.5倍。Trianglecounting算法測試Twitter-2010數據集在1636個節點的Hadoop環境，Graphchi比Hadoop快了3倍。相對于Hadoop來說，Graphchi的大規模圖數據方面的性能遠優于Hadoop；在協同過濾方面，Graphchi和Graphlab性能相差不大；與性能較好的Spark相比，Graphchi的性能表現也在可以接受的范圍內；對于性能強大的Powergraph，Graphchi性能還是有一些差距。總體來說，Graphchi以單機運行方式進行圖運算所表現出的性能可以和一些分布式的框架相媲美，雖然不及性能強大的Powergraph，但是這樣的性能表現已經可以滿足一定規模的圖運算了。這樣的性能表現已足以為成本不足、硬件設備配置不高的中小企業或者個人提供高可行、高可用的社交關系網絡圖數據分析和挖掘平臺。

4Graphchi電信圖數據挖掘應用

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

4.1PageRank算法挖掘核心人物PageRank算法是Google用于用來標識網頁的等級/重要性的一種方法，是Google用來衡量一個網站好壞的唯一標準。它基于馬爾科夫狀態轉移理論，通過網頁的鏈入數對網頁進行投票來得出重要性排名。發展到目前，PageRank算法也被廣泛用于關鍵人物挖掘等社交關系網絡分析中。本文應用Graphchi的Pagerank算法，對電信關系網絡數據進行Rank值的計算，從而找出關鍵人物。表4是采用Graphchi的Pagerank算法對電信數據集進行計算Rank值的排名前10的結果，在4000萬個用戶中，標號為1653的用戶的重要性最高，為核心用戶，應該對其重點挖掘和營銷推廣。

4.2CommunityDetection算法進行社區發現CommunityDetection社區發現算法用于發現網絡中的社區結構，也可以看作是一種聚類算法。同一社區之間的節點與節點之間的關系比較緊密，而社區與社區之間的關系比較稀疏。如果兩者之間的聯系越頻繁，那么其社交關系就越緊密。如圖12所示，可以找到3個關系緊密的社區。表5為采用Graphchi的CommunityDetection算法對電信數據集進行社團發現的結果，共發現社區1733613個，最大社區有35558616個用戶。運營商可以對每一個社團分析其相似特征，進行潛在客戶挖掘以及后續的客戶關系維護。

5結束語

電信技術的發展帶來了大規模的電信數據，面對日趨激烈的市場競爭環境，電信運營商如何從通信數據抽象成大規模的圖網絡數據中挖掘有價值的信息，維護客戶關系，進行針對性服務成了關注的焦點。本文闡述了可以對大規模電信社交網絡圖數據進行挖掘和計算的幾種分布式框架和單機計算框架。并且通過實驗和對比，說明單機的Graphchi運行各算法在不同規模數據集所用的時間和其他可以運行這些算法的框架相比在合理的范圍內，使用廉價的硬盤和普通的服務器就可以實現大規模的圖計算，并且有良好的性能，它可以像其他分布式框架一樣，在解決大規模社交關系網絡圖數據時有很好的運行效率。同時，Graphchi簡單、高可用的性能使其在解決其他分布式系統能解決的大規模電信社交關系網絡圖數據方面也有很高的運行效率，其在一定規模的圖數據量上的應用前景不可限量。但是，隨著當前信息時代數量的不斷擴增，對圖數據處理的需求越來越高，Graphchi能否繼續承載更高數據量的分析處理任務仍然是一個問號，本文也提到了并行分布式框架在超大規模的社交關系網絡圖數據挖掘中，表現出強大的處理能力和效率，相信并行處理將是超大規模社交關系網絡圖數據處理發展的必然趨勢。

作者：劉麗嬌陶俊才肖曉軍盧宇單位：南昌大學信息工程學院計算中心廣州優億信息科技有限公司