顧惠健 韓忠愿 許加書

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

基于大規(guī)模社會網(wǎng)絡(luò)的并行布局算法框架

顧惠健 韓忠愿 許加書

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

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

社會網(wǎng)絡(luò) 力導(dǎo)引布局算法 圖數(shù)據(jù)庫

0 引 言

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

因此，本文結(jié)合了社區(qū)網(wǎng)絡(luò)的具體特征，在建立分層的思想上，提出了適合大規(guī)模社區(qū)網(wǎng)絡(luò)數(shù)據(jù)的布局算法，并且以此為基礎(chǔ)，設(shè)計了基于分布式的社區(qū)網(wǎng)絡(luò)布局框架。

1 相關(guān)工作

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

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

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

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

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

通過以上文獻資料，發(fā)現(xiàn)FR、KK等算法雖然在傳統(tǒng)的力導(dǎo)引算法上進行了速度或者美觀上的改進，但是布局規(guī)模十分有限。雖然之后的算法基于分層或者簇以達到計算大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的目的，但是由于節(jié)點數(shù)量多，布局速度不理想而且用戶體驗不好。因此本文基于分層的思想結(jié)合分布式框架Spark和圖數(shù)據(jù)庫Neo4j，設(shè)計出了基于NFR算法的社區(qū)布局框架。

2 系統(tǒng)框架

本文基于社區(qū)網(wǎng)絡(luò)的具體特征，結(jié)合圖數(shù)據(jù)庫Neo4j和分布式框架Spark的特點，對社區(qū)網(wǎng)絡(luò)數(shù)據(jù)進行基于分層思想的布局。主要算法是通過NFR算法實現(xiàn)了社區(qū)之間布局的不重疊，并且根據(jù)社區(qū)坐標及社區(qū)內(nèi)部節(jié)點信息對社區(qū)內(nèi)部進行布局，把得到的社區(qū)數(shù)據(jù)存儲在Neo4j中，最后設(shè)計出一個完整的社區(qū)布局系統(tǒng)，系統(tǒng)架構(gòu)如圖1所示。

圖1 社區(qū)布局系統(tǒng)框架

2.1 存儲層

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

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

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

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

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

圖2 社區(qū)數(shù)據(jù)在圖數(shù)據(jù)庫的存儲

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

2.2 計算層

2.2.1 社區(qū)布局

對于社區(qū)布局，即對網(wǎng)絡(luò)數(shù)據(jù)分層布局的粗糙層進行布局，如對圖3(b)進行布局，圖3(a)表示對應(yīng)社區(qū)的內(nèi)部結(jié)構(gòu)。FR算法布局，其實就是對節(jié)點中心(x,y)的布局，由于節(jié)點本身很小，并沒考慮節(jié)點重疊的情況。

圖3 分層布局模型

但是基于社區(qū)的布局，由于社區(qū)都比較大，傳統(tǒng)的FR布局會出現(xiàn)嚴重的重疊現(xiàn)象，導(dǎo)致對之后的社區(qū)內(nèi)部布局產(chǎn)生影響，所以本文根據(jù)Harel和Koren[8]提出的重疊節(jié)點之間增大斥力、減少引力的原則提出了NFR算法。

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

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

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

fr(d)=-k2/d

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

fa(d)=d2/k

其中k為彈簧的彈性系數(shù)，d為兩個節(jié)點的距離。

根據(jù)重疊節(jié)點斥力增大、引力減少的原則修改社區(qū)與社區(qū)之間的距離d，如果d≥R1+R2，則兩個社區(qū)不重疊，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;

//表示節(jié)點v的偏移量

for u in V do

if(u≠v) then begin

δ:=v.pos-u.pos;

//表示節(jié)點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

//計算節(jié)點v與其連接邊的節(jié)點的引力

δ:=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

//通過偏移量更新節(jié)點的坐標

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

end

t:=cool(t);

//減少溫度作為布局的參數(shù)

end

2.2.2 社區(qū)內(nèi)部布局

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

圖4 Neo4j和Spark通信

2.3 展示層

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

圖5 2號社區(qū)的展示效果

3 實驗說明

為了對上述架構(gòu)的有效性進行測試與驗證，根據(jù)該架構(gòu)實現(xiàn)了一個系統(tǒng)。實驗的硬件平臺為：8臺IBM刀片式服務(wù)器，每臺的CPU為Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60 GHz，內(nèi)存為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。

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

3.1 Karate網(wǎng)絡(luò)的實驗結(jié)果與分析

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

圖6 Karate網(wǎng)絡(luò)布局實驗對比圖

3.2 Football網(wǎng)絡(luò)的實驗結(jié)果與分析

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

圖7 Football網(wǎng)絡(luò)布局實驗對比圖

3.3 大規(guī)模網(wǎng)絡(luò)的實驗結(jié)果與分析

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

圖8 Amazon網(wǎng)絡(luò)的社區(qū)展示

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

隨著互聯(lián)網(wǎng)的迅速發(fā)展，社會網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模也越來越大，當面對大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)的布局計算時，只能采用分布式計算，并且為了能更快地展示出數(shù)據(jù)，將數(shù)據(jù)共享至內(nèi)存，為此采用共享內(nèi)存的并行計算框架Spark。下面通過這兩組數(shù)據(jù)，比較Spark框架和基于社區(qū)劃分算法的優(yōu)勢，如圖9、圖10所示。

圖9 Amazon和LiveJournal基于Spark比較

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

通過實驗結(jié)果可以看出，基于Spark的并行計算框架與基于力導(dǎo)引算法的非重疊社區(qū)布局算法結(jié)合可以加快大規(guī)模網(wǎng)絡(luò)的計算速度。

接下來考慮社區(qū)的個數(shù)對基于力導(dǎo)引算法的非重疊社區(qū)布局算法的影響，如圖11所示。

圖11 社區(qū)個數(shù)對NFR的影響

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

4 結(jié) 語

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

[1] 孫揚,蔣遠翔,趙翔,等.網(wǎng)絡(luò)可視化研究綜述[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] 李厚儒,南敬昌.擬牛頓粒子群算法在非線性電路諧波平衡方程中的應(yīng)用[J].計算機應(yīng)用與軟件,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] 伍勇,鐘志農(nóng),景寧,等.適于社區(qū)挖掘分析與可視化的布局算法[J].計算機研究與發(fā)展,2012,49(Suppl.):203-208.

[14] 朱志良,林森,崔坤,等.基于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的網(wǎng)絡(luò)拓撲結(jié)構(gòu)可視化布局算法[J].計算機輔助設(shè)計與圖形學學報,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)。顧惠健，碩士生，主研領(lǐng)域：網(wǎng)絡(luò)可視化。韓忠愿，教授。許加書，碩士生。

TP3

A

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