基于大規模社會網絡的并行布局算法框架

顧惠健 韓忠愿 許加書

(南京財經大學信息工程學院 江蘇 南京 210046)

基于大規模社會網絡的并行布局算法框架

顧惠健 韓忠愿 許加書

(南京財經大學信息工程學院 江蘇 南京 210046)

隨著社會網絡的迅速發展，針對大規模社會網絡的可視化已經成為數據挖掘領域中的一項重要的研究課題。傳統的布局算法已經無法對大規模的社區網絡進行全局管理和展示。因此，該框架基于并行化技術以及分層的思想，實現了大規模社會網絡的可視化框架。其貢獻主要有：提出了一種基于力導引算法的非重疊社區布局算法(簡稱NFR)；設計了一個基于Spark的并行計算框架；將圖數據庫(Neo4j)無縫地整合到框架中。最后通過在真實數據集上的測試，驗證了該框架的有效性。

社會網絡 力導引布局算法 圖數據庫

0 引 言

近年來，互聯網迅速發展，網絡數據的拓撲結構也變得日益復雜。而且現實中的諸多系統都是以網絡的形式存在的，如社會關系網絡、生物食物鏈網絡、交通運輸網絡、蛋白質交互網絡等[1]，這些復雜的系統可以被抽象地描述為復雜網絡。復雜網絡的一個重要分支是社會網絡，已逐漸成為當前的最熱門研究領域。它作為社區網絡分析的重要的方法，在國家安全、軍事等重要領域都有廣闊的應用前景。目前，社區網絡可視化的主要布局算法有：層次布局、樹型布局和彈簧布局等，在上述的布局算法中，彈簧布局又稱為力導引布局算法。由于力導引布局算法能簡明、快速地展示社區信息，逐漸成為布局算法應用中的主流。但是在傳統的力導引布局算法中，社會網絡中的邊和節點通常被視為物理作用力系統。雖然這樣可以使算法自然簡單且應用廣泛，但只能應用于小型網絡，并且節點與節點之間的重疊現象嚴重。近些年，有些學者提出分層的思想對社區網絡進行布局，這樣確實使大型網絡的布局時間大大縮短，提高了效率，但是布局效果不是很理想，而且大部分文獻只是提出了一個算法，并沒有一個完整的系統框架被提出來。

因此，本文結合了社區網絡的具體特征，在建立分層的思想上，提出了適合大規模社區網絡數據的布局算法，并且以此為基礎，設計了基于分布式的社區網絡布局框架。

1 相關工作

社區網絡可視化的核心技術主要是布局算法，力導引算法又是目前被廣泛應用的布局效果最好的布局算法。1984年Eades提出了該算法[2]，算法的原理是模擬力學平衡，將網絡中的每個節點比作鋼球，而連接鋼球的線比作彈簧，鋼球通過彼此之間的作用力調整位置使得整個物理系統達到力學平衡，從而布局完成。目前，基于該布局算法的改進算法有很多，如：FR(Fruchterman-Reingold)算法[3]、KK(Kamada Kawai)算法[4]、DH(Davidson Harel)算法[5]等。FR算法定義了兩個基本原則：第一，所有的節點相互之間都存在斥力；第二，只有邊相連的節點才存在引力。FR算法還增加了“溫度”，通過設定一個初始溫度，然后線性降溫，直至為零。隨著溫度的下降，節點調節的幅度也變小，布局就會更美觀。這種方法被稱為模擬退火算法。同時，為了降低計算斥力的復雜度，FR還建議采用網格變量的方法進行優化，將布局區域分成若干個網格，不相鄰網格的節點之間不計算斥力，這樣計算斥力的復雜度從二次降到了一次。KK算法找到一種方法直接減少彈簧的動力勢能，引入了節點之間理想距離的概念，這樣可以避免所有節點縮成一團。接下來就通過Newton-Raohson方法[6]，每次優化一個節點，其他所有節點的位置保持不變。在每個循環里，首先選取具有最大梯度的節點，然后讓它在優化的方向上移動數次直到梯度低于某個固定值，再選取下一個具有最大梯度的節點，以此類推循環優化。DH算法在傳統的能量函數上增加了額外的約束條件，通過減少交叉邊的個數使節點遠離同它不相連的邊，同時，還可以調節約束權重使布局滿足不同的審美標準。適用于大型組合優化的模擬退火技術也在該算法上得到了廣泛的應用，該技術可以快速求解能量函數的局部最小值，并且在算法的最后加入了邊交叉和邊點交叉的罰函數，使得該算法與其他算法相比能夠產生更加好的節點布局效果。但是因為模擬退火技術本身復雜及選取最優化參數存在一定困難，該算法計算時間長。

以上的改進算法都是基于小規模數據的。直到20世紀90年代末，一些擴展了傳統力導引算法的技術出現了，它們能展示成千上萬個節點。這些方法都有個共性，就是采用了分層的技術，從最簡單的結構逐漸變得越來越復雜。例如Hadany和Harel提出的HH算法[7]采用分層的技術可以展示一千個節點；Harel和Koren提出的HK算法[8]采用了一種新的多層模型，僅需2秒就可以完全展示一千個節點。該算法把模型分為兩層，分別為模糊層和精確層。模糊層是基于k-centers，精確層是基于傳統的KK算法或FR算法。Walshaw提出的算法[9]則可以展示225 000個節點。還有一種是Gajer等人提出的過濾方法[10]，先過濾某些不重要的節點，再把重要的節點展示出來。

之前的力導引算法都是基于節點與節點之間的斥力或者節點與邊的斥力，它們沒有考慮基于邊與邊計算斥力的方法。通過邊與邊的計算斥力，能夠解決零角分辨率的問題,卻會導致不良的重疊的點。針對這個問題，Lin等人提出了一種新的方法：結合邊與邊、點與點的計算斥力的方法[11]。

為了進一步減少算法復雜度，2006年，Hu[12]引入超節點的概念并且提出了多層級力導引算法。該算法的原理是當一個節點和一簇節點隔著相當遠的距離，那么就不需要計算該節點與簇中所有節點的斥力，只需把這簇節點看成是一個超節點，然后計算該節點與超節點的斥力。通過引入超節點，從而大大減少計算量，把計算復雜度降至O(nlog(n))。

而國內伍勇等學者[13]通過計算節點的度得到每個節點的緊密度來改變FR算法中的引力，以此來提高布局的展示效果。還有朱志良等學者[14]結合社區網絡的特點，通過把一個社區看成一個節點，以社區間的關聯為邊構建新的網絡，再用傳統方法進行布局，其實這種方法類似于Harel和Koren提出的分層模型。

通過以上文獻資料，發現FR、KK等算法雖然在傳統的力導引算法上進行了速度或者美觀上的改進，但是布局規模十分有限。雖然之后的算法基于分層或者簇以達到計算大規模網絡數據的目的，但是由于節點數量多，布局速度不理想而且用戶體驗不好。因此本文基于分層的思想結合分布式框架Spark和圖數據庫Neo4j，設計出了基于NFR算法的社區布局框架。

2 系統框架

本文基于社區網絡的具體特征，結合圖數據庫Neo4j和分布式框架Spark的特點，對社區網絡數據進行基于分層思想的布局。主要算法是通過NFR算法實現了社區之間布局的不重疊，并且根據社區坐標及社區內部節點信息對社區內部進行布局，把得到的社區數據存儲在Neo4j中，最后設計出一個完整的社區布局系統，系統架構如圖1所示。

圖1 社區布局系統框架

2.1 存儲層

根據社區數據的網絡特征，本文選擇圖數據庫Neo4j存儲初始化數據。圖數據庫是NoSQL數據庫的一種，它采用圖數據模型，以圖的方式管理具有圖特性的數據。Neo4j不僅是基于磁盤的、嵌入式的，而且還是具備完全的事務特性的Java持久化引擎。關于圖形數據的基本概念有以下三個：

(1) 節點：表示一個實體。例如：人、商品或者一個帳號。

(2) 邊：表示關系，即節點與節點之間的聯系，可以有方向性。例如：用戶B購買了商品A，表示B->A。

(3) 屬性：表示節點與邊附帶的屬性。例如：用戶的身高、年齡等。

本文根據社區標簽對數據進行劃分，把劃分好的社區看作節點，那么這些節點就具有一些屬性，如社區大小、標簽、該社區的內部成員等。社區與社區之間的關系就被看成邊，關系的緊密程度則是根據社區之間內部關系決定的，社區與社區之間內部的節點連接越多那么關系就越緊密，如圖2所示。

圖2 社區數據在圖數據庫的存儲

所有通過計算層求出的節點信息，包括節點的坐標，存儲到圖數據庫Neo4j中。這樣可以根據展示層用戶的請求，及時返回所需展示的社區的信息。

2.2 計算層

2.2.1 社區布局

對于社區布局，即對網絡數據分層布局的粗糙層進行布局，如對圖3(b)進行布局，圖3(a)表示對應社區的內部結構。FR算法布局，其實就是對節點中心(x,y)的布局，由于節點本身很小，并沒考慮節點重疊的情況。

圖3 分層布局模型

但是基于社區的布局，由于社區都比較大，傳統的FR布局會出現嚴重的重疊現象，導致對之后的社區內部布局產生影響，所以本文根據Harel和Koren[8]提出的重疊節點之間增大斥力、減少引力的原則提出了NFR算法。

本文對基于社區布局的算法重新進行定義：

繪圖畫布area=n×r×q，其中n表示社區所有節點的個數，r為社區中每個節點的平均半徑，q為一個常數控制節點與節點之間的距離，q越大則節點之間離得越遠。

NFR算法對斥力的定義如下：

fr(d)=-k2/d

NFR算法對引力的定義如下：

fa(d)=d2/k

其中k為彈簧的彈性系數，d為兩個節點的距離。

根據重疊節點斥力增大、引力減少的原則修改社區與社區之間的距離d，如果d≥R1+R2，則兩個社區不重疊，d保持不變；d

function fa(d):=begin return d2/k end;

function fr(d):=begin return k2/d end;

for i:=1 to iterations do begin

for v in V do begin

//計算所有點與點V的斥力

v.disp:=0;

//表示節點v的偏移量

for u in V do

if(u≠v) then begin

δ:=v.pos-u.pos;

//表示節點v和u的坐標位置

d:=d>(v.r+u.r)?

d:min(d,v.r,u.r)/(v.r×u.r×n2);

v.disp:=v.disp+(δ/d)×fr(d);

end

end

for v in E do begin

//計算節點v與其連接邊的節點的引力

δ:=e.v.pos-e.u.pos;

d:=d>(v.r+u.r)?

d:min(d,v.r,u.r)/(v.r×u.r×n2);

e.v.disp:=e.v.disp+(δ/d)×fa(d);

e.u.disp:=e.u.disp+(δ/d)×fa(d);

end

for v in V do begin

//通過偏移量更新節點的坐標

v.pos:=v.pos+(v.disp/|v.disp|)×min(v.disp,t);

end

t:=cool(t);

//減少溫度作為布局的參數

end

2.2.2 社區內部布局

通過NFR算法把社區布局之后，就得到了社區的坐標及其半徑。因為每個社區是相互獨立的，所以本文選擇Spark并行布局各個社區，而社區內部的布局算法，本文選取傳統FR布局算法。在加州大學伯克利分校的AMP實驗室，一個開源的、并行分布式計算框架Spark誕生了，基于內存的計算、批量處理、迭代計算、流處理、即席查詢等多種范式。因為Spark是基于MapReduce原理實現的，所以具備MapReduce所具有的優點;但是相比于MapReduce不同的是Job中間輸出和結果可以保存在內存中，從而省去了HDFS的讀寫，大大加快了計算速度，因此Spark較多應用于數據挖掘與機器學習等需要迭代的算法。從圖數據庫Neo4j中讀取社區信息，通過Spark分布式框架，用FR算法對社區進行布局，Neo4j和Spark通過Mazerunner連接，如圖4所示。

圖4 Neo4j和Spark通信

2.3 展示層

本文采用網頁的形式展示，通過引用wz_jsgraphic畫出節點及邊的信息。wz_jsgraphics是一個專門用來繪制簡單圖形的JavaScript包。展示的過程是從Neo4j讀取社區信息，再經過NFR算法進行社區布局，把社區展示出來。根據用戶選擇查看的社區，把已經分布式計算過的并且存在Neo4j數據庫中的該社區的信息讀取出，展示到畫布上。如圖3(b)所示的三個社區，選擇把2號社區展示出來，如圖5所示。

圖5 2號社區的展示效果

3 實驗說明

為了對上述架構的有效性進行測試與驗證，根據該架構實現了一個系統。實驗的硬件平臺為：8臺IBM刀片式服務器，每臺的CPU為Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60 GHz，內存為128 GB。軟件平臺為：Red Hat 4.8.2-16、Hadoop 1.1.2、Spark 1.3.1、Neo4j 2.1.2、JDK 1.7、Eclipse 4.4.2、Tomcat 7.0。

本文用社區挖掘的3個網絡對系統的性能進行測試、驗證和分析，并將實驗結果與FR算法、KK算法進行比較。實驗中，本文所指的運算時間為從HDFS中讀文件開始直至計算完所有節點坐標，并存入數據庫Neo4j。

3.1 Karate網絡的實驗結果與分析

Karate網絡來自UCI數據集，是社會學家Zachary根據1970年，美國一所大學的空手道俱樂部成員的關系構建的社區網絡。總共34個節點、77條邊，本文隨機把這些節點分成4個社區。根據NFR算法重疊社區之間斥力增大、引力減少的概念，避免了社區重疊的現象，布局效果如圖6(a)所示。再根據已經劃分好的社區，為社區內部的節點進行布局，如圖6(b)所示。圖6(c)和圖6(d)分別是FR算法和KK算法的布局效果，明顯可以看出圖6(b)的社區劃分鮮明，四個社區能保持一定的距離。

圖6 Karate網絡布局實驗對比圖

3.2 Football網絡的實驗結果與分析

Football網絡也是來自UCI數據集，是美國大學生橄欖球聯賽的對陣情況，總共有12個聯盟，包括115支球隊。網絡中的節點表示參賽球隊，節點之間的邊為兩支球隊進行過比賽，總賽程為613場。Football網絡的社區劃分不是采用隨機的，而是選取12個聯盟為社區，那么與Karate網絡有所區別，即節點與節點之間有很強的聯系，布局效果如圖7所示。其中本文算法布局出的結果，不同顏色代表不同的球隊，布局清晰，能很快找出球隊。FR算法布局結果比較混亂，雖然能大致展示出網絡結構的框架，但是無法完全辨認出一個球隊。KK算法則非常混亂，節點與節點之間完全看不出聯系。

圖7 Football網絡布局實驗對比圖

3.3 大規模網絡的實驗結果與分析

本文選取了兩個大規模網絡數據集進行實驗。Amazon網絡來自斯坦福大學提供的數據集，是亞馬遜網站在2003年3月收集的產品被購買的數據。產品表示節點，假設產品A和產品B一起經常被顧客購買，那么A和B之間就存在一條邊。總共包含262 111個節點、1 234 877條邊，本文隨機把Amazon網絡劃分為1000個社區。由于數據量較大，本文只展示社區的布局，如圖8所示。

圖8 Amazon網絡的社區展示

LiveJournal網絡也是來自斯坦福大學提供的數據集，是一個在線博客的用戶數據集。用戶可以彼此確定好友關系，也可以建立一個小組，其他用戶可以加入進來，通常把這個小組看成社會網絡的一個社區。總共包含3 997 962個節點、34 681 189條邊，本文隨機把LiveJournal網絡劃分為8000個社區。

隨著互聯網的迅速發展，社會網絡的數據規模也越來越大，當面對大規模的網絡數據的布局計算時，只能采用分布式計算，并且為了能更快地展示出數據，將數據共享至內存，為此采用共享內存的并行計算框架Spark。下面通過這兩組數據，比較Spark框架和基于社區劃分算法的優勢，如圖9、圖10所示。

圖9 Amazon和LiveJournal基于Spark比較

圖10 Amazon和LiveJournal的NFR、FR和KK算法比較

通過實驗結果可以看出，基于Spark的并行計算框架與基于力導引算法的非重疊社區布局算法結合可以加快大規模網絡的計算速度。

接下來考慮社區的個數對基于力導引算法的非重疊社區布局算法的影響，如圖11所示。

圖11 社區個數對NFR的影響

通過實驗結果可以看出，Amazon網絡在800個社區的時候，計算速度是最快的，而LiveJournal網絡則在8000個社區的時候，計算速度才是最快的。這是因為分布式計算會隨社區的個數增多而增加計算次數，但社區內部節點少，又浪費計算性能。而當社區個數比較少，社區內部節點就會增多，這樣雖然計算次數會減少，但是計算單個社區的負擔就會加重。

4 結 語

目前，社區挖掘算法在對大規模復雜網絡的可視化的問題上存在瓶頸，傳統的布局算法在速度和效果上都無法滿足大規模網絡的需求。因此，本文運用并行化技術以及分層的思想，實現了大規模社會網絡的可視化。本文成功將NFR算法注入到Spark平臺中，同時運用圖數據庫把數據保存為圖中的節點以及節點之間的關系，充分利用社會網絡的特性。實驗結果表明，本文的算法可以在較短時間內布局完節點，并且不會出現社區的重疊現象，質量與效率都有很大的提升。但是，在精確層布局上，本文還是使用原來的算法，如何提高社區內部布局的效率和效果是下一步需要討論的問題。

[1] 孫揚,蔣遠翔,趙翔,等.網絡可視化研究綜述[J].計算機科學,2010,37(2):12-18,30.

[2] Eades P A.A Heuristic for Graph Drawing[J].Congressus Numerantium,1984,42:149-160.

[3] Fruchterman T M J,Reigold E M.Graph drawing by force-directed placement[J].Software-Practice and Experience,1991,21(11):1129-1164.

[4] Kamada T,Kawai S.An Algorithm for Drawing General Undirected Graphs[J].Information Processing Letters,1989,31(1):7-15.

[5] Davidson R,Harel D.Drawing graphs nicely using simulated annealing[J].ACM Transactions on Graphics (TOG),1996,15(4):301-331.

[6] 李厚儒,南敬昌.擬牛頓粒子群算法在非線性電路諧波平衡方程中的應用[J].計算機應用與軟件,2013,30(2):103-105,109.

[7] Hadany R,Harel D.A multi-scale algorithm for drawing graphs nicely[J].Discrete Applied Mathematics,2001,113(1):3-21.

[8] Harel D,Koren Y.A fast multi-scale method for drawing large graphs[J].Journal of Graph Algorithms and Applications,2002,6(3):179-202.

[9] Walshaw C.A multilevel algorithm for force-directed graph drawing[J].Journal of Graph Algorithms and Applications,2003,7(3):253-285.

[10]GajerP,GoodrichMT,KobourovSG.Afastmulti-dimensionalalgorithmfordrawinglargegraphs[J].ComputationalGeometry:TheoryandApplications,2004,29(1):3-18.

[11]LinCC,YenHC.Anewforce-directedgraphdrawingmethodbasedonedge-edgerepulsion[J].JournalofVisualLanguagesandComputing,2012,23(1):29-42.

[12]HuY.Efficientandhighqualityforce-directedgraphdrawing[J].TheMathematicaJournal,2006,10(1):37-71.

[13] 伍勇,鐘志農,景寧,等.適于社區挖掘分析與可視化的布局算法[J].計算機研究與發展,2012,49(Suppl.):203-208.

[14] 朱志良,林森,崔坤,等.基于復雜網絡社區劃分的網絡拓撲結構可視化布局算法[J].計算機輔助設計與圖形學學報,2011,23(11):1808-1815.

FRAMEWORK OF PARALLEL LAYOUT ALGORITHM BASED ON LARGE-SCALE SOCIAL NETWORKS

Gu Huijian Han Zhongyuan Xu Jiashu

(CollegeofInformationEngineering,NanjingUniversityofFinanceandEconomics,Nanjing210046,Jiangsu,China)

With the rapid development of social networks, visualization for large-scale social networks has been an important research topic in the data mining field. The existing layout algorithms failed to manage and demonstrate the large-scale social networks, so the proposed framework realize the visualization framework of large-scale social networks based on parallel techniques and hierarchical ideas. The main contributions include: A non-overlapping community layout algorithm based on force directed layout algorithm (NFR) is proposed. A parallel computing framework based on Spark is designed. A graph database (Neo4j) is seamlessly integrated into the framework. Finally, experiments on various real-world social networks demonstrate the advantage of the framework.

Social networks Force directed layout algorithm Graph database

2015-09-24。國家自然科學基金面上項目(71372188)；國家科技支撐計劃項目(2013BAH16F01)。顧惠健，碩士生，主研領域：網絡可視化。韓忠愿，教授。許加書，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.01.013