任淑霞, 吳 濤, 張書博
(天津工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院, 天津 300387)
計算機(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ò)中的信息.
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)布局算法.
大量研究顯示復(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 樹圖[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)勢. 為直觀展示社區(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é)果 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. 為證明算法的合理性和有效性,本文選用復(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. (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.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)定.




3 混合徑向樹的社區(qū)半徑力引導(dǎo)算法
3.1 徑向樹
3.2 采用徑向樹排列社區(qū)節(jié)點


3.3 ERRTH算法步驟
4 實驗結(jié)果分析
4.1 布局結(jié)果分析



4.2 算法效率分析



