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

顧惠健 韓忠愿 許加書(shū)

(南京財(cái)經(jīng)大學(xué)信息工程學(xué)院 江蘇 南京 210046)

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

顧惠健 韓忠愿 許加書(shū)

(南京財(cái)經(jīng)大學(xué)信息工程學(xué)院 江蘇 南京 210046)

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

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

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

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

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

2 系統(tǒng)框架

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

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

2.1 存儲(chǔ)層

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

(1) 節(jié)點(diǎn)：表示一個(gè)實(shí)體。例如：人、商品或者一個(gè)帳號(hào)。

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

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

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

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

所有通過(guò)計(jì)算層求出的節(jié)點(diǎn)信息，包括節(jié)點(diǎn)的坐標(biāo)，存儲(chǔ)到圖數(shù)據(jù)庫(kù)Neo4j中。這樣可以根據(jù)展示層用戶(hù)的請(qǐng)求，及時(shí)返回所需展示的社區(qū)的信息。

2.2 計(jì)算層

2.2.1 社區(qū)布局

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

圖3 分層布局模型

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

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

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

NFR算法對(duì)斥力的定義如下：

fr(d)=-k2/d

NFR算法對(duì)引力的定義如下：

fa(d)=d2/k

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

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

//計(jì)算所有點(diǎn)與點(diǎn)V的斥力

v.disp:=0;

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

for u in V do

if(u≠v) then begin

δ:=v.pos-u.pos;

//表示節(jié)點(diǎn)v和u的坐標(biāo)位置

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

//計(jì)算節(jié)點(diǎn)v與其連接邊的節(jié)點(diǎn)的引力

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

//通過(guò)偏移量更新節(jié)點(diǎn)的坐標(biāo)

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

end

t:=cool(t);

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

end

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

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

圖4 Neo4j和Spark通信

2.3 展示層

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

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

3 實(shí)驗(yàn)說(shuō)明

為了對(duì)上述架構(gòu)的有效性進(jìn)行測(cè)試與驗(yàn)證，根據(jù)該架構(gòu)實(shí)現(xiàn)了一個(gè)系統(tǒng)。實(shí)驗(yàn)的硬件平臺(tái)為：8臺(tái)IBM刀片式服務(wù)器，每臺(tái)的CPU為Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60 GHz，內(nèi)存為128 GB。軟件平臺(tái)為：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個(gè)網(wǎng)絡(luò)對(duì)系統(tǒng)的性能進(jìn)行測(cè)試、驗(yàn)證和分析，并將實(shí)驗(yàn)結(jié)果與FR算法、KK算法進(jìn)行比較。實(shí)驗(yàn)中，本文所指的運(yùn)算時(shí)間為從HDFS中讀文件開(kāi)始直至計(jì)算完所有節(jié)點(diǎn)坐標(biāo)，并存入數(shù)據(jù)庫(kù)Neo4j。

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

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

圖6 Karate網(wǎng)絡(luò)布局實(shí)驗(yàn)對(duì)比圖

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

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

圖7 Football網(wǎng)絡(luò)布局實(shí)驗(yàn)對(duì)比圖

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

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

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

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

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

圖9 Amazon和LiveJournal基于Spark比較

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

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

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

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

通過(guò)實(shí)驗(yàn)結(jié)果可以看出，Amazon網(wǎng)絡(luò)在800個(gè)社區(qū)的時(shí)候，計(jì)算速度是最快的，而LiveJournal網(wǎng)絡(luò)則在8000個(gè)社區(qū)的時(shí)候，計(jì)算速度才是最快的。這是因?yàn)榉植际接?jì)算會(huì)隨社區(qū)的個(gè)數(shù)增多而增加計(jì)算次數(shù)，但社區(qū)內(nèi)部節(jié)點(diǎn)少，又浪費(fèi)計(jì)算性能。而當(dāng)社區(qū)個(gè)數(shù)比較少，社區(qū)內(nèi)部節(jié)點(diǎn)就會(huì)增多，這樣雖然計(jì)算次數(shù)會(huì)減少，但是計(jì)算單個(gè)社區(qū)的負(fù)擔(dān)就會(huì)加重。

4 結(jié) 語(yǔ)

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

[1] 孫揚(yáng),蔣遠(yuǎn)翔,趙翔,等.網(wǎng)絡(luò)可視化研究綜述[J].計(jì)算機(jī)科學(xué),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] 李厚儒,南敬昌.擬牛頓粒子群算法在非線(xiàn)性電路諧波平衡方程中的應(yīng)用[J].計(jì)算機(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].計(jì)算機(jī)研究與發(fā)展,2012,49(Suppl.):203-208.

[14] 朱志良,林森,崔坤,等.基于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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。國(guó)家自然科學(xué)基金面上項(xiàng)目(71372188)；國(guó)家科技支撐計(jì)劃項(xiàng)目(2013BAH16F01)。顧惠健，碩士生，主研領(lǐng)域：網(wǎng)絡(luò)可視化。韓忠愿，教授。許加書(shū)，碩士生。

TP3

A

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