嵌入社區(qū)半徑的力引導(dǎo)與徑向樹混合布局算法

任淑霞， 吳 濤， 張書博

(天津工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院， 天津 300387)

1 引 言

計算機(jī)技術(shù)的快速發(fā)展，讓社會關(guān)系網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、疾病傳播網(wǎng)絡(luò)等網(wǎng)絡(luò)分析在現(xiàn)實生活中起到重要的作用.但要正確地解讀和理解這些網(wǎng)絡(luò)中包含的信息卻非常困難.因此，如何描繪網(wǎng)絡(luò)和節(jié)點結(jié)構(gòu)，讓其便于理解和使用一直是復(fù)雜網(wǎng)絡(luò)布局算法領(lǐng)域研究的熱門.

最早對復(fù)雜網(wǎng)絡(luò)進(jìn)行布局的是1984年P(guān)eter Eades提出的彈力模型[1].Eades的算法雖然簡單，但是效率非常低.Fruchterman和Reingold提出FR(Fruchterman-Reingold)[2]布局算法.FR算法易于實現(xiàn)、降低了計算復(fù)雜度.由于FR算法強(qiáng)調(diào)節(jié)點均勻、邊長一致等美學(xué)標(biāo)準(zhǔn)，因此上述改進(jìn)算法均存在阻礙網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)形成的缺陷.

于是，學(xué)者開始關(guān)注于將聚類方法應(yīng)用于布局算法的研究，Linlog模型[3]是一種計算最小能量來呈現(xiàn)社區(qū)結(jié)構(gòu)的模型，雖然它已經(jīng)實現(xiàn)聚類效果，但沒辦法證明社區(qū)劃分的有效性.吳渝等[4]提出了社團(tuán)引力導(dǎo)引的布局算法，該算法不僅為每個節(jié)點加入社團(tuán)引力，還結(jié)合K-means算法讓節(jié)點向社團(tuán)的中心位置聚攏，該算法無需對節(jié)點分類，可以在布局的同時對節(jié)點聚類.Zhou等[5]提出了基于度中心性的社團(tuán)力導(dǎo)引改進(jìn)算法，從而完成對復(fù)雜網(wǎng)絡(luò)的聚類布局.通過觀察發(fā)現(xiàn)聚類布局算法均能達(dá)成社區(qū)劃分且社區(qū)之間沒有重疊的效果.但是，社區(qū)內(nèi)的節(jié)點由于太過靠攏，用戶很難發(fā)現(xiàn)社區(qū)內(nèi)節(jié)點之間的關(guān)系，不利于用戶對社區(qū)內(nèi)部的信息的探索.

基于上述問題，本文提出嵌入社區(qū)半徑的力引導(dǎo)與徑向樹混合布局算法ERRTH(community radius embedded in force-directed and radial tree hybid layout algorithm)，針對FR布局算法單純追求美學(xué)標(biāo)準(zhǔn)而不利于發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)這一問題，本文采用K-means算法快速進(jìn)行社區(qū)劃分，再用嵌入[6]社區(qū)半徑的社區(qū)引力和斥力來分離社區(qū)，從而完成復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的展示.為彌補(bǔ)聚類布局算法在社區(qū)內(nèi)部節(jié)點結(jié)構(gòu)展示上的缺陷，本文混合徑向樹來層次化顯示社區(qū)內(nèi)節(jié)點結(jié)構(gòu).布局結(jié)果不僅符合對稱性和美學(xué)標(biāo)準(zhǔn)，同時也便于用戶觀察和分析復(fù)雜網(wǎng)絡(luò)中的信息.

2 嵌入社區(qū)半徑的力引導(dǎo)布局算法

2.1 FR布局算法

FR布局算法是一種力引導(dǎo)圖布局算法.它遵循兩個簡單的原則：有邊連接的節(jié)點應(yīng)該相互靠近；節(jié)點之間不能離得太近.

FR算法的每次迭代主要分為兩個部分：

1) 計算節(jié)點之間的斥力

fr(i,j)=-u2/dist(i,j).

2) 計算有邊連接的節(jié)點之間的吸引力

fa(i,j)=dist(i,j)2/u

其中，u代表兩節(jié)點之間的理想距離.

最后，綜合吸引力和斥力，通過最大位移來限制節(jié)點的移動距離.當(dāng)兩個節(jié)點存在覆蓋現(xiàn)象時，F(xiàn)R算法會施加斥力來分開節(jié)點.FR算法在布局時僅僅改變節(jié)點位置，避免重疊，并沒有分離節(jié)點所屬的社區(qū)，不利于用戶的觀察.為達(dá)到分離社區(qū)的目的，本文提出嵌入社區(qū)半徑的力引導(dǎo)布局算法.

2.2 嵌入社區(qū)半徑的力引導(dǎo)布局算法

大量研究顯示復(fù)雜網(wǎng)絡(luò)存在社區(qū)內(nèi)連邊眾多，而社區(qū)之間連邊較少的特性，因此采用社區(qū)劃分[7]來構(gòu)建社區(qū)網(wǎng)絡(luò).當(dāng)社區(qū)數(shù)量較多時易產(chǎn)生社區(qū)重疊或超出布局區(qū)域范圍的現(xiàn)象，為解決該問題，本文提出社區(qū)半徑并定義社區(qū)網(wǎng)絡(luò)的社區(qū)斥力和社區(qū)引力，同時用社區(qū)半徑對社區(qū)斥力和引力作用范圍進(jìn)行合理限制.

嵌入社區(qū)半徑的力引導(dǎo)布局算法步驟如下：

(1) 構(gòu)建社區(qū)網(wǎng)絡(luò).

采用K-means算法[8]，選取m個點作為m個社區(qū)的初始中心點，然后分配節(jié)點到最近的中心點所在的社區(qū)，重新計算中心點，如果中心點不變，則停止計算；否則繼續(xù)直到社區(qū)中心不變?yōu)橹?將復(fù)雜網(wǎng)絡(luò)劃G(V,E)分出m個社區(qū){H1,H2,…,Hm}，構(gòu)建社區(qū)網(wǎng)絡(luò)G′.

(2) 計算社區(qū)半徑.

定義1社區(qū)半徑ri.社區(qū)半徑ri是社區(qū)Hi以社區(qū)中心為圓心的圓的半徑，社區(qū)內(nèi)節(jié)點越多，ri越大.社區(qū)半徑的計算公式為

(1)

式中，x和y表示畫布的寬和高；num(v)表示網(wǎng)絡(luò)中的節(jié)點數(shù)量；Mi表示社區(qū)Hi的布局區(qū)域.

(3) 計算社區(qū)斥力.

定義2社區(qū)斥力E(HA,HB)，設(shè)社區(qū)斥力E(HA,HB)是社區(qū)網(wǎng)絡(luò)G′中社區(qū)HA和社區(qū)HB之間存在的一種斥力.E(HA,HB)的計算公式為

(2)

其中，l(eAB)表示A、B社區(qū)中心的距離；N(HA)表示社區(qū)A所包含的節(jié)點數(shù).

社區(qū)網(wǎng)絡(luò)中社區(qū)之間存在社區(qū)斥力，社區(qū)斥力主要由社區(qū)半徑來限制作用范圍和計算.由圖1可以看出，社區(qū)之間的社區(qū)斥力主要由l(eAB)和d來確定的.

(a) l(eAB)≥2d,d=rA+rB

(b) l(eAB)≤d,d=rA+rB

(c) d

1) 如圖1(a)所示，當(dāng)社區(qū)中心距離l(eAB)≥2d時，兩社區(qū)之間應(yīng)該只有社區(qū)引力而沒有社區(qū)斥力，此時社區(qū)斥力E(HA,HB)=0.

2) 如圖1(b)所示，當(dāng)社區(qū)中心距離l(eAB)≤d時，兩社區(qū)會發(fā)生社區(qū)重疊.因此，需要施加一個固定常量的斥力h來分離兩社區(qū)，此時社區(qū)斥力E(HA,HB)=h.

因此，社區(qū)半徑能將社區(qū)斥力的作用范圍限制在[0,2(rA+rB))之間，社區(qū)斥力能夠分離兩社區(qū)并阻止它們之間的社區(qū)重疊.

4) 計算社區(qū)引力.

定義3社區(qū)引力G(HA,HB)，社區(qū)引力G(HA,HB)是社區(qū)網(wǎng)絡(luò)中社區(qū)和社區(qū)之間存在的一種引力.G(HA,HB)的計算公式為

G(HA,HB)=

(3)

社區(qū)網(wǎng)絡(luò)中不僅存在社區(qū)斥力，還存在社區(qū)引力，也由社區(qū)半徑來限制其作用范圍和計算的.如圖2所示.

(a) l(eAB)≤d,d=rA+rB

(b)l(eAB)>d,d=rA+rB

1) 如圖2(a)所示，當(dāng)社區(qū)中心距離l(eAB)=d時，如果兩社區(qū)存在社區(qū)引力，那么它們將會發(fā)生社區(qū)重疊，這時只有社區(qū)斥力而無社區(qū)引力.因此，當(dāng)l(eAB)≤d時，社區(qū)引力G(HA,HB)=0.

2) 如圖2(b)所示，當(dāng)社區(qū)中心距離l(eAB)>d時，兩社區(qū)之間就會存在社區(qū)引力.開始時，社區(qū)引力與兩個社區(qū)所包含的節(jié)點數(shù)之差成正比.隨著l(eAB)增大，社區(qū)引力將會變大，而社區(qū)斥力將變小，社區(qū)之間將會吸引來解決超出布局區(qū)域的問題.同時，需要存在一個引力系數(shù)g，方便用戶隨時調(diào)節(jié)社區(qū)引力的值來調(diào)整布局結(jié)果，此時社區(qū)引力為

(4)

因此，可得出社區(qū)引力的作用范圍為(rA+rB,)，社區(qū)引力能解決兩社區(qū)相距太遠(yuǎn)而超出布局區(qū)域的問題.

嵌入社區(qū)半徑的力引導(dǎo)算法在Karate數(shù)據(jù)集的布局結(jié)果如圖3(b)所示.較之FR算法，可以看出復(fù)雜網(wǎng)絡(luò)被劃分成不同社區(qū)，社區(qū)之間相互遠(yuǎn)離，社區(qū)網(wǎng)絡(luò)的結(jié)構(gòu)明顯.但社區(qū)內(nèi)節(jié)點相互擁擠在一起，不利于用戶觀察社區(qū)內(nèi)結(jié)構(gòu)特征與連邊關(guān)系.因此，本文采用徑向樹布局排列各社區(qū)內(nèi)節(jié)點，讓節(jié)點滿足層次結(jié)構(gòu)布局的需求.

(a) FR算法的布局結(jié)果

(b) 嵌入社區(qū)半徑的力引導(dǎo)算法的布局結(jié)果

(b) Layout result of community radius embedded in Force-Directed algorithm

圖3 布局結(jié)果對比圖

Fig.3 Layout result comparison graph

3 混合徑向樹的社區(qū)半徑力引導(dǎo)算法

3.1 徑向樹

樹圖[9]關(guān)注自動生成關(guān)系信息的幾何表示，通常用于分層可視化.用于對分層信息進(jìn)行建模的典型數(shù)據(jù)結(jié)構(gòu)是頂點表示實體并且其連邊對應(yīng)于實體之間關(guān)系的樹.層次結(jié)構(gòu)布局可以向用戶有效的傳達(dá)信息.徑向樹[10-11]作為樹圖的分支，在展示節(jié)點結(jié)構(gòu)層次有著獨特優(yōu)勢.

3.2 采用徑向樹排列社區(qū)節(jié)點

為直觀展示社區(qū)內(nèi)節(jié)點層次結(jié)構(gòu)，本文采用徑向樹對社區(qū)內(nèi)的節(jié)點進(jìn)行排列，使所有節(jié)點都位于社區(qū)中心聚焦的同心圓上.徑向樹排列節(jié)點的步驟如下.

(1) 如要快速搜索出社區(qū)內(nèi)節(jié)點的全部層次結(jié)構(gòu)L，則采用DFS(深度搜索算法)來而不采用BFS(廣度搜索算法)，并從社區(qū)內(nèi)隨機(jī)選出節(jié)點作為根節(jié)點放置在社區(qū)中心，設(shè)各級之間的距離D是將社區(qū)半徑除以社區(qū)中的級數(shù)L來計算的.

(2) 將根節(jié)點放置在社區(qū)中心，此節(jié)點是下一級中其他節(jié)點的父節(jié)點.由于1級節(jié)點具有相同的父節(jié)點，可以分布在整個2π上.因此計算角度時，將2π除以1級節(jié)點的數(shù)量，這會在1級節(jié)點之間創(chuàng)建角度空間，然后遍歷1級節(jié)點，使用式(5)計算1級節(jié)點的位置.

(5)

其中，NIwl是層級內(nèi)的節(jié)點索引；As是角度空間.

(3) 計算切線角度.

定義4層級半徑.節(jié)點所在的層級到根節(jié)點的距離叫做層級半徑.

節(jié)點N0的子節(jié)點必須落在其所屬層級的一定范圍內(nèi)以防止重疊，切線垂直于N0節(jié)點與根節(jié)點的連線，切線與子節(jié)點所在層級相交的點為切線切點.切線切點與N0節(jié)點的父節(jié)點(根節(jié)點)連線的夾角作為切線角度，使用式(6)來計算切線角度.

TanAn(N0)=2arccos(Rout/Rin)

(6)

式中，Rin是子節(jié)點所對應(yīng)的層級半徑；Rout是父節(jié)點所對應(yīng)的層級半徑.

(4) 計算等分線角度.節(jié)點N0計算等分線角度公式如下.

(7)

其中，N1、N2是N0的相鄰節(jié)點；Arc(N0,N1)為圖4中N0與N1的夾角.子節(jié)點所能分配的范圍為等分線角度與切線角度的交集所對應(yīng)的圓弧上，這能避免子節(jié)點分配重疊的現(xiàn)象.子節(jié)點的分配范圍如圖4所示.

(5) 在2級或更高級別上，由于父節(jié)點限制子節(jié)點的位置，首先得到待分配子節(jié)點的父節(jié)點集合.遍歷該集合，得到父節(jié)點的子節(jié)點列表，明確子節(jié)點的分配范圍，放置子節(jié)點在分配范圍對應(yīng)的圓弧上.

ERRTH算法的最終布局結(jié)果如圖5所示，較之圖3展示的布局結(jié)果，可以看出社區(qū)內(nèi)節(jié)點層次結(jié)構(gòu)分明，節(jié)點之間擁擠程度不高.其中紅色節(jié)點為根節(jié)點，其余節(jié)點分布在以根節(jié)點為圓心的同心圓上，布局結(jié)果明顯，且符合對稱性和美學(xué)標(biāo)準(zhǔn).

圖4 子節(jié)點的分配范圍示意圖Fig.4 Child node allocation range graph

圖5 ERRTH算法布局結(jié)果

3.3 ERRTH算法步驟

ERRTH算法步驟如算法1所示.

算法1 ERRTH算法

輸入：網(wǎng)絡(luò)G(V,E)，最大迭代次數(shù)N，最大位移M.

輸出：網(wǎng)絡(luò)節(jié)點位置坐標(biāo){D1,D2, …,Dn}.

Begin

1) 初始化節(jié)點位置，為節(jié)點生成隨機(jī)的坐標(biāo).

2) 用K-means將網(wǎng)絡(luò)G劃分出m個社區(qū)，構(gòu)建社區(qū)網(wǎng)絡(luò)，確定各社區(qū)節(jié)點數(shù)量，依據(jù)式(1)計算出社區(qū)半徑.

3) 依據(jù)式(2)和式(3)計算社區(qū)網(wǎng)絡(luò)中社區(qū)之間社區(qū)引力和斥力，綜合社區(qū)引力和斥力，用最大位移M限制社區(qū)的最大移動距離，社區(qū)所屬節(jié)點隨著各社區(qū)中心移動.

4) 若迭代次數(shù)大于最大迭代次數(shù)，執(zhí)行步驟5)，否則，循環(huán)步驟3).

5) 對于社區(qū)內(nèi)節(jié)點，用DFS算法明確各社區(qū)層級，然后通過社區(qū)半徑計算出級間距離，放置根節(jié)點.

6) 對于社區(qū)內(nèi)1級節(jié)點，依據(jù)式(5)計算1級節(jié)點位置.

7) 對于社區(qū)內(nèi)2級或更高級別的節(jié)點，依據(jù)式(6)確定切線角度和式(7)確定等分線角度，明確切線角度和等分線角度的交集范圍，放置節(jié)點到交集范圍所對應(yīng)的圓弧上，循環(huán)放社區(qū)內(nèi)節(jié)點至最后一層即可.

8) 輸出節(jié)點位置{D1,D2…,Dn}.

End.

4 實驗結(jié)果分析

為證明算法的合理性和有效性，本文選用復(fù)雜網(wǎng)絡(luò)中的Dolphins[12]，Karate[13]，F(xiàn)ootball[5]網(wǎng)絡(luò)來展示復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，選取FR算法和朱志良等人算法[14]的布局結(jié)果進(jìn)行對比.為定量分析本文算法的合理性，將ERRTH算法與FR算法、CGDA算法[13]、文獻(xiàn)[14]算法和文獻(xiàn)[5]算法采用相同數(shù)據(jù)集進(jìn)行對比，并用點分布方差[14]、擁擠區(qū)域占比、邊長偏差[15]、節(jié)點分布偏差[16]和時間進(jìn)行實驗分析.實驗的運(yùn)行環(huán)境是intenl(R)Core(TM)2 Quad CPU Q8300@2.50 GHz、內(nèi)存為16 G、64位Win10的PC.

4.1 布局結(jié)果分析

(1) Dolphins網(wǎng)絡(luò)是依據(jù)生活在新西蘭的62只海豚而創(chuàng)建的社會關(guān)系網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含62個節(jié)點和159條邊.

ERRTH算法與朱志良等人的算法在Dolphins數(shù)據(jù)集上的布局結(jié)果如圖6所示.圖6(a)是文獻(xiàn)[14]的可視化布局結(jié)果，該算法雖然阻止不同社區(qū)節(jié)點的交錯，但社區(qū)位置過于靠近，網(wǎng)絡(luò)變得非常擁擠，若沒有顏色加以區(qū)分，用戶無法觀察出社區(qū)結(jié)構(gòu).而圖6(b)可以看出ERRTH算法不僅能夠阻止不同社區(qū)的覆蓋，而且社區(qū)之間相互遠(yuǎn)離且層次結(jié)構(gòu)明顯.兩者比較，ERRTH算法能清晰地展示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)和社區(qū)層次結(jié)構(gòu).

(2) Football網(wǎng)絡(luò)數(shù)據(jù)集，該數(shù)據(jù)集表示美國大學(xué)生足球俱樂部比賽的網(wǎng)絡(luò)，該數(shù)據(jù)集包含115個節(jié)點和616條邊.

圖7為Football數(shù)據(jù)集的布局結(jié)果，由于數(shù)據(jù)集節(jié)點與邊規(guī)模比較大，因此選擇適當(dāng)縮小節(jié)點來滿足布局要求.從圖7(a)可以看出FR算法已經(jīng)不能滿足復(fù)雜網(wǎng)絡(luò)展示和美學(xué)需求，節(jié)點之間層次結(jié)構(gòu)，用戶很難明確社區(qū)結(jié)構(gòu)和節(jié)點層次特征.為了能夠在圖7(b)中清晰地觀察社區(qū)結(jié)構(gòu)，本文選擇放大藍(lán)色方框內(nèi)的布局結(jié)果如圖8所示.

(a) 文獻(xiàn)[14]的布局結(jié)果 (b) ERRTH算法布局結(jié)果

(a) The layout result of document [14] (b) The layout result of ERRTH

圖6 Dolphins布局對比圖

Fig.6 Comparison graph of Dolphins layout

圖8(b)可以清晰顯示根節(jié)點17與下一層級的20、70等節(jié)點相連，而圖8(c)節(jié)點20與相同層級的62、65、87、70等節(jié)點和下一層級的76、75、36等節(jié)點相連，用戶分析網(wǎng)絡(luò)時可以優(yōu)先著眼于社區(qū)內(nèi)部的關(guān)鍵信息，然后再與不同社區(qū)的節(jié)點聯(lián)合分析.從而提高用戶獲得復(fù)雜網(wǎng)絡(luò)關(guān)鍵信息的效率，方便用戶的使用.最后，綜合圖7(a)和(b)可以看出ERRTH算法不僅能夠分離不同的社區(qū)，還能展示社區(qū)內(nèi)的層次結(jié)構(gòu)和連邊關(guān)系，便于用戶探索復(fù)雜網(wǎng)絡(luò)的信息.

4.2 算法效率分析

4.2.1 時間復(fù)雜度分析 ERRTH算法由嵌入社區(qū)半徑的力引導(dǎo)和徑向樹布局算法兩部分組成.針對嵌入社區(qū)半徑的力引導(dǎo)布局算法，在每一次迭代過程中，社區(qū)網(wǎng)絡(luò)中的k個社區(qū)都要計算各自的社區(qū)引力和斥力，社區(qū)內(nèi)的節(jié)點v′采用引力的方式隨著社區(qū)中心移動，所以這部分的時間復(fù)雜度為Ο(k2+k|v′|).針對徑向樹布局，每個社區(qū)內(nèi)的節(jié)點都采用DFS算法明確節(jié)點層級結(jié)構(gòu).循環(huán)節(jié)點層級結(jié)構(gòu)L，依據(jù)父節(jié)點v′來確定可分配節(jié)點的圓弧并放置相應(yīng)的子節(jié)點vn，徑向樹的時間復(fù)雜度為Ο(|v′|2+L|v′||vn|).由此可得，ERRTH算法的時間復(fù)雜度為Ο(k2+k|v′|)+Ο(|v′|2+L|v′||vn|).

4.2.2 實驗指標(biāo)分析 擁擠度[17]常被用于衡量集成電路布局設(shè)計是否合理的，擁擠度需要統(tǒng)計不同區(qū)域邊緣的走線數(shù)Se和固定邊緣走線數(shù)De，但在復(fù)雜網(wǎng)絡(luò)中很難統(tǒng)計邊緣走線數(shù)Se和De，因此不適用對復(fù)雜網(wǎng)絡(luò)的布局結(jié)果進(jìn)行評價.為對復(fù)雜網(wǎng)絡(luò)的布局效果進(jìn)行衡量，本文以區(qū)域內(nèi)節(jié)點的數(shù)量來判定區(qū)域是否為擁擠區(qū)域，并提出擁擠區(qū)域占比來評價不同算法下的復(fù)雜網(wǎng)絡(luò)布局效果.

定義5平均節(jié)點擁有量(avg_region).每個區(qū)域內(nèi)擁有的平均節(jié)點數(shù)量，記為avg_region.

(8)

式中，num(v)表示節(jié)點總數(shù)；region表示區(qū)域總數(shù)；s和t表示布局圖被劃分出的行、列數(shù).

定義6擁擠區(qū)域(crowd_area).若劃分進(jìn)某區(qū)域內(nèi)的節(jié)點數(shù)量高于平均節(jié)點擁有量，則此區(qū)域被認(rèn)定擁擠區(qū)域，記為crowd_area.

定義7擁擠區(qū)域占比(crowd_area_rate).擁擠區(qū)域的數(shù)量占所有區(qū)域的比例，記為crowd_area_rate.

(9)

如圖9所示，給區(qū)域分配節(jié)點時，部分節(jié)點位于區(qū)域的邊緣上，為將這部分節(jié)點劃分至指定區(qū)域，本文提出一個“左部優(yōu)先，上部優(yōu)先”的節(jié)點劃分策略. 節(jié)點1位于B，C兩個區(qū)域，按照“左部優(yōu)先”原則，節(jié)點1劃分進(jìn)了B區(qū)域.同樣，節(jié)點3因“上部優(yōu)先”原則被劃分進(jìn)E區(qū)域.但少數(shù)特殊節(jié)點如節(jié)點2，它位于區(qū)域A、B、D、E的邊緣交叉處，按照劃分策略，它會被劃分進(jìn)區(qū)域A.循環(huán)處理邊緣節(jié)點至每個節(jié)點都被分配到相應(yīng)區(qū)域，并依據(jù)式(9)計算出擁擠區(qū)域占比.擁擠區(qū)域占比越高，說明復(fù)雜網(wǎng)絡(luò)的部分區(qū)域相對較擁擠，節(jié)點過于密集，不利于用戶觀察復(fù)雜網(wǎng)絡(luò).

圖9 區(qū)域節(jié)點劃分策略Fig.9 Regional node partitioning strategy

圖10 不同算法的擁擠區(qū)域統(tǒng)計圖Fig.10 Crowed area statistics of different algorithms

實驗中的指標(biāo)數(shù)據(jù)均采用python語言編程獲得，實驗結(jié)果分別如表1和表2所示.

由表1和表2的實驗結(jié)果，以及圖10分析得出，在相同的數(shù)據(jù)集下，采用徑向樹的ERRTH算法產(chǎn)生的擁擠區(qū)域明顯少于其他布局算法，說明ERRTH算法可以有效減少復(fù)雜網(wǎng)絡(luò)中的擁擠區(qū)域.再從點分布方差來看，ERRTH算法布局后的節(jié)點分布更為合理，可以降低節(jié)點擁擠導(dǎo)致的布局混亂和區(qū)域內(nèi)節(jié)點的密集程度.

ERRTH算法的邊長偏差和節(jié)點分布偏差低于其他布局算法，說明ERRTH算法相較于其他算法社區(qū)內(nèi)的節(jié)點布局偏差較少，節(jié)點分布結(jié)果更均勻，更符合復(fù)雜網(wǎng)絡(luò)布局的美學(xué)標(biāo).ERRTH算法為達(dá)到明確社區(qū)內(nèi)節(jié)點層次結(jié)構(gòu)的目的而采用徑向樹進(jìn)行二次布局，這部分占用時間過多導(dǎo)致ERRTH算法的時間略高于其他算法，但算法之間差距不大，并且尚在用戶可容忍時間范圍2～8 s之內(nèi).

表1 Dolphins網(wǎng)絡(luò)的實驗結(jié)果

表2 Football網(wǎng)絡(luò)的實驗結(jié)果

此外，本文還采用ERRTH算法對線蟲的神經(jīng)網(wǎng)絡(luò)(299個節(jié)點，2 359條邊，數(shù)據(jù)集來源于Newman教授的個人網(wǎng)站)進(jìn)行布局，運(yùn)行時間穩(wěn)定在16 s左右，擁擠區(qū)域的占比為0.4，遠(yuǎn)低于其他布局算法.可以推出ERRTH算法尤其適用于500個以下節(jié)點的布局，布局后的擁擠區(qū)域較少，節(jié)點分布較為合理.

最終從布局分析和算法效率分析的結(jié)果來看，ERRTH算法可以顯著地分離兩個社區(qū)，且高效地展示各個社區(qū)內(nèi)網(wǎng)絡(luò)層次結(jié)構(gòu)，提高復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的辨識度，對于網(wǎng)絡(luò)布局較之傳統(tǒng)布局有著較強(qiáng)可讀性和可解釋性，具有很強(qiáng)的使用價值.本文基于FR算法，提出嵌入社區(qū)半徑的社區(qū)斥力和引力來分離復(fù)雜網(wǎng)絡(luò)的社區(qū)，接著又采用徑向樹來排列各個社區(qū)內(nèi)節(jié)點位置.前者可以避免各社區(qū)的聚攏和重疊，后者可以直觀展示各個社區(qū)內(nèi)層次結(jié)構(gòu)，便于用戶理解社區(qū)內(nèi)節(jié)點之間的層次關(guān)系.與力引導(dǎo)算法和聚類布局算法相比，ERRTH算法可避免力引導(dǎo)算法不能分離社區(qū)以及現(xiàn)有的聚類布局算法不能顯示社區(qū)內(nèi)部節(jié)點結(jié)構(gòu)關(guān)系的缺陷.

在對復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)劃分時，網(wǎng)絡(luò)中可能會存在一些同時與幾個社區(qū)有聯(lián)系，但又不屬于任何社區(qū)的節(jié)點，它常位于社區(qū)的邊緣區(qū)域被稱為邊緣節(jié)點.由于本文采用Kmeans算法來劃分社區(qū)，該方法不能準(zhǔn)確識別邊緣節(jié)點和需要先給出聚類數(shù)目m.因此，在下一步工作中，將選用能識別邊緣節(jié)點的社區(qū)劃分算法來替代Kmeans算法，同時將本文布局算法運(yùn)用到時變復(fù)雜網(wǎng)絡(luò)[18]分析上去，使時變網(wǎng)絡(luò)在布局時能保持網(wǎng)絡(luò)結(jié)構(gòu)和心智圖[19]的穩(wěn)定.