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

任淑霞， 吳 濤， 張書博

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

1 引 言

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

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

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

基于上述問題，本文提出嵌入社區(qū)半徑的力引導(dǎo)與徑向樹混合布局算法ERRTH(community radius embedded in force-directed and radial tree hybid layout algorithm)，針對(duì)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é)點(diǎn)結(jié)構(gòu)展示上的缺陷，本文混合徑向樹來層次化顯示社區(qū)內(nèi)節(jié)點(diǎn)結(jié)構(gòu).布局結(jié)果不僅符合對(duì)稱性和美學(xué)標(biāo)準(zhǔn)，同時(shí)也便于用戶觀察和分析復(fù)雜網(wǎng)絡(luò)中的信息.

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

2.1 FR布局算法

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

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

1) 計(jì)算節(jié)點(diǎn)之間的斥力

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

2) 計(jì)算有邊連接的節(jié)點(diǎn)之間的吸引力

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

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

最后，綜合吸引力和斥力，通過最大位移來限制節(jié)點(diǎn)的移動(dòng)距離.當(dāng)兩個(gè)節(jié)點(diǎn)存在覆蓋現(xiàn)象時(shí)，F(xiàn)R算法會(huì)施加斥力來分開節(jié)點(diǎn).FR算法在布局時(shí)僅僅改變節(jié)點(diǎn)位置，避免重疊，并沒有分離節(jié)點(diǎn)所屬的社區(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ù)量較多時(shí)易產(chǎn)生社區(qū)重疊或超出布局區(qū)域范圍的現(xiàn)象，為解決該問題，本文提出社區(qū)半徑并定義社區(qū)網(wǎng)絡(luò)的社區(qū)斥力和社區(qū)引力，同時(shí)用社區(qū)半徑對(duì)社區(qū)斥力和引力作用范圍進(jìn)行合理限制.

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

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

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

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

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

(1)

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

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

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

(2)

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

社區(qū)網(wǎng)絡(luò)中社區(qū)之間存在社區(qū)斥力，社區(qū)斥力主要由社區(qū)半徑來限制作用范圍和計(jì)算.由圖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時(shí)，兩社區(qū)之間應(yīng)該只有社區(qū)引力而沒有社區(qū)斥力，此時(shí)社區(qū)斥力E(HA,HB)=0.

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

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

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

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

G(HA,HB)=

(3)

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

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

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

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

2) 如圖2(b)所示，當(dāng)社區(qū)中心距離l(eAB)>d時(shí)，兩社區(qū)之間就會(huì)存在社區(qū)引力.開始時(shí)，社區(qū)引力與兩個(gè)社區(qū)所包含的節(jié)點(diǎn)數(shù)之差成正比.隨著l(eAB)增大，社區(qū)引力將會(huì)變大，而社區(qū)斥力將變小，社區(qū)之間將會(huì)吸引來解決超出布局區(qū)域的問題.同時(shí)，需要存在一個(gè)引力系數(shù)g，方便用戶隨時(shí)調(diào)節(jié)社區(qū)引力的值來調(diào)整布局結(jié)果，此時(shí)社區(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é)點(diǎn)相互擁擠在一起，不利于用戶觀察社區(qū)內(nèi)結(jié)構(gòu)特征與連邊關(guān)系.因此，本文采用徑向樹布局排列各社區(qū)內(nèi)節(jié)點(diǎn)，讓節(jié)點(diǎn)滿足層次結(jié)構(gòu)布局的需求.

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

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

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

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

Fig.3 Layout result comparison graph

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

3.1 徑向樹

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

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

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

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

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

(5)

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

(3) 計(jì)算切線角度.

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

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

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

(6)

式中，Rin是子節(jié)點(diǎn)所對(duì)應(yīng)的層級(jí)半徑；Rout是父節(jié)點(diǎn)所對(duì)應(yīng)的層級(jí)半徑.

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

(7)

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

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

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

圖4 子節(jié)點(diǎn)的分配范圍示意圖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é)點(diǎn)位置坐標(biāo){D1,D2, …,Dn}.

Begin

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

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

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

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

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

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

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

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

End.

4 實(shí)驗(yàn)結(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)行對(duì)比.為定量分析本文算法的合理性，將ERRTH算法與FR算法、CGDA算法[13]、文獻(xiàn)[14]算法和文獻(xiàn)[5]算法采用相同數(shù)據(jù)集進(jìn)行對(duì)比，并用點(diǎn)分布方差[14]、擁擠區(qū)域占比、邊長(zhǎng)偏差[15]、節(jié)點(diǎn)分布偏差[16]和時(shí)間進(jìn)行實(shí)驗(yàn)分析.實(shí)驗(yà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)建的社會(huì)關(guān)系網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含62個(gè)節(jié)點(diǎn)和159條邊.

ERRTH算法與朱志良等人的算法在Dolphins數(shù)據(jù)集上的布局結(jié)果如圖6所示.圖6(a)是文獻(xiàn)[14]的可視化布局結(jié)果，該算法雖然阻止不同社區(qū)節(jié)點(diǎn)的交錯(cuò)，但社區(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ù)集表示美國(guó)大學(xué)生足球俱樂部比賽的網(wǎng)絡(luò)，該數(shù)據(jù)集包含115個(gè)節(jié)點(diǎn)和616條邊.

圖7為Football數(shù)據(jù)集的布局結(jié)果，由于數(shù)據(jù)集節(jié)點(diǎn)與邊規(guī)模比較大，因此選擇適當(dāng)縮小節(jié)點(diǎn)來滿足布局要求.從圖7(a)可以看出FR算法已經(jīng)不能滿足復(fù)雜網(wǎng)絡(luò)展示和美學(xué)需求，節(jié)點(diǎn)之間層次結(jié)構(gòu)，用戶很難明確社區(qū)結(jié)構(gòu)和節(jié)點(diǎn)層次特征.為了能夠在圖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布局對(duì)比圖

Fig.6 Comparison graph of Dolphins layout

圖8(b)可以清晰顯示根節(jié)點(diǎn)17與下一層級(jí)的20、70等節(jié)點(diǎn)相連，而圖8(c)節(jié)點(diǎn)20與相同層級(jí)的62、65、87、70等節(jié)點(diǎn)和下一層級(jí)的76、75、36等節(jié)點(diǎn)相連，用戶分析網(wǎng)絡(luò)時(shí)可以優(yōu)先著眼于社區(qū)內(nèi)部的關(guān)鍵信息，然后再與不同社區(qū)的節(jié)點(diǎn)聯(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 時(shí)間復(fù)雜度分析 ERRTH算法由嵌入社區(qū)半徑的力引導(dǎo)和徑向樹布局算法兩部分組成.針對(duì)嵌入社區(qū)半徑的力引導(dǎo)布局算法，在每一次迭代過程中，社區(qū)網(wǎng)絡(luò)中的k個(gè)社區(qū)都要計(jì)算各自的社區(qū)引力和斥力，社區(qū)內(nèi)的節(jié)點(diǎn)v′采用引力的方式隨著社區(qū)中心移動(dòng)，所以這部分的時(shí)間復(fù)雜度為Ο(k2+k|v′|).針對(duì)徑向樹布局，每個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)都采用DFS算法明確節(jié)點(diǎn)層級(jí)結(jié)構(gòu).循環(huán)節(jié)點(diǎn)層級(jí)結(jié)構(gòu)L，依據(jù)父節(jié)點(diǎn)v′來確定可分配節(jié)點(diǎn)的圓弧并放置相應(yīng)的子節(jié)點(diǎn)vn，徑向樹的時(shí)間復(fù)雜度為Ο(|v′|2+L|v′||vn|).由此可得，ERRTH算法的時(shí)間復(fù)雜度為Ο(k2+k|v′|)+Ο(|v′|2+L|v′||vn|).

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

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

(8)

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

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

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

(9)

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

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

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

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

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

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

表1 Dolphins網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

表2 Football網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

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

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

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