嵌入社區半徑的力引導與徑向樹混合布局算法

任淑霞， 吳 濤， 張書博

(天津工業大學計算機科學與軟件學院， 天津 300387)

1 引 言

計算機技術的快速發展，讓社會關系網絡、生物網絡、疾病傳播網絡等網絡分析在現實生活中起到重要的作用.但要正確地解讀和理解這些網絡中包含的信息卻非常困難.因此，如何描繪網絡和節點結構，讓其便于理解和使用一直是復雜網絡布局算法領域研究的熱門.

最早對復雜網絡進行布局的是1984年Peter Eades提出的彈力模型[1].Eades的算法雖然簡單，但是效率非常低.Fruchterman和Reingold提出FR(Fruchterman-Reingold)[2]布局算法.FR算法易于實現、降低了計算復雜度.由于FR算法強調節點均勻、邊長一致等美學標準，因此上述改進算法均存在阻礙網絡社區結構形成的缺陷.

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

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

2 嵌入社區半徑的力引導布局算法

2.1 FR布局算法

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

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

1) 計算節點之間的斥力

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

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

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

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

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

2.2 嵌入社區半徑的力引導布局算法

大量研究顯示復雜網絡存在社區內連邊眾多，而社區之間連邊較少的特性，因此采用社區劃分[7]來構建社區網絡.當社區數量較多時易產生社區重疊或超出布局區域范圍的現象，為解決該問題，本文提出社區半徑并定義社區網絡的社區斥力和社區引力，同時用社區半徑對社區斥力和引力作用范圍進行合理限制.

嵌入社區半徑的力引導布局算法步驟如下：

(1) 構建社區網絡.

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

(2) 計算社區半徑.

定義1社區半徑ri.社區半徑ri是社區Hi以社區中心為圓心的圓的半徑，社區內節點越多，ri越大.社區半徑的計算公式為

(1)

式中，x和y表示畫布的寬和高；num(v)表示網絡中的節點數量；Mi表示社區Hi的布局區域.

(3) 計算社區斥力.

定義2社區斥力E(HA,HB)，設社區斥力E(HA,HB)是社區網絡G′中社區HA和社區HB之間存在的一種斥力.E(HA,HB)的計算公式為

(2)

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

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

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

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

(c) d

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

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

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

4) 計算社區引力.

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

G(HA,HB)=

(3)

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

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

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

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

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

(4)

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

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

(a) FR算法的布局結果

(b) 嵌入社區半徑的力引導算法的布局結果

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

圖3 布局結果對比圖

Fig.3 Layout result comparison graph

3 混合徑向樹的社區半徑力引導算法

3.1 徑向樹

樹圖[9]關注自動生成關系信息的幾何表示，通常用于分層可視化.用于對分層信息進行建模的典型數據結構是頂點表示實體并且其連邊對應于實體之間關系的樹.層次結構布局可以向用戶有效的傳達信息.徑向樹[10-11]作為樹圖的分支，在展示節點結構層次有著獨特優勢.

3.2 采用徑向樹排列社區節點

為直觀展示社區內節點層次結構，本文采用徑向樹對社區內的節點進行排列，使所有節點都位于社區中心聚焦的同心圓上.徑向樹排列節點的步驟如下.

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

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

(5)

其中，NIwl是層級內的節點索引；As是角度空間.

(3) 計算切線角度.

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

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

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

(6)

式中，Rin是子節點所對應的層級半徑；Rout是父節點所對應的層級半徑.

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

(7)

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

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

ERRTH算法的最終布局結果如圖5所示，較之圖3展示的布局結果，可以看出社區內節點層次結構分明，節點之間擁擠程度不高.其中紅色節點為根節點，其余節點分布在以根節點為圓心的同心圓上，布局結果明顯，且符合對稱性和美學標準.

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

圖5 ERRTH算法布局結果

3.3 ERRTH算法步驟

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

算法1 ERRTH算法

輸入：網絡G(V,E)，最大迭代次數N，最大位移M.

輸出：網絡節點位置坐標{D1,D2, …,Dn}.

Begin

1) 初始化節點位置，為節點生成隨機的坐標.

2) 用K-means將網絡G劃分出m個社區，構建社區網絡，確定各社區節點數量，依據式(1)計算出社區半徑.

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

4) 若迭代次數大于最大迭代次數，執行步驟5)，否則，循環步驟3).

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

6) 對于社區內1級節點，依據式(5)計算1級節點位置.

7) 對于社區內2級或更高級別的節點，依據式(6)確定切線角度和式(7)確定等分線角度，明確切線角度和等分線角度的交集范圍，放置節點到交集范圍所對應的圓弧上，循環放社區內節點至最后一層即可.

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

End.

4 實驗結果分析

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

4.1 布局結果分析

(1) Dolphins網絡是依據生活在新西蘭的62只海豚而創建的社會關系網絡，該網絡包含62個節點和159條邊.

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

(2) Football網絡數據集，該數據集表示美國大學生足球俱樂部比賽的網絡，該數據集包含115個節點和616條邊.

圖7為Football數據集的布局結果，由于數據集節點與邊規模比較大，因此選擇適當縮小節點來滿足布局要求.從圖7(a)可以看出FR算法已經不能滿足復雜網絡展示和美學需求，節點之間層次結構，用戶很難明確社區結構和節點層次特征.為了能夠在圖7(b)中清晰地觀察社區結構，本文選擇放大藍色方框內的布局結果如圖8所示.

(a) 文獻[14]的布局結果 (b) ERRTH算法布局結果

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

圖6 Dolphins布局對比圖

Fig.6 Comparison graph of Dolphins layout

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

4.2 算法效率分析

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

4.2.2 實驗指標分析 擁擠度[17]常被用于衡量集成電路布局設計是否合理的，擁擠度需要統計不同區域邊緣的走線數Se和固定邊緣走線數De，但在復雜網絡中很難統計邊緣走線數Se和De，因此不適用對復雜網絡的布局結果進行評價.為對復雜網絡的布局效果進行衡量，本文以區域內節點的數量來判定區域是否為擁擠區域，并提出擁擠區域占比來評價不同算法下的復雜網絡布局效果.

定義5平均節點擁有量(avg_region).每個區域內擁有的平均節點數量，記為avg_region.

(8)

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

定義6擁擠區域(crowd_area).若劃分進某區域內的節點數量高于平均節點擁有量，則此區域被認定擁擠區域，記為crowd_area.

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

(9)

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

圖9 區域節點劃分策略Fig.9 Regional node partitioning strategy

圖10 不同算法的擁擠區域統計圖Fig.10 Crowed area statistics of different algorithms

實驗中的指標數據均采用python語言編程獲得，實驗結果分別如表1和表2所示.

由表1和表2的實驗結果，以及圖10分析得出，在相同的數據集下，采用徑向樹的ERRTH算法產生的擁擠區域明顯少于其他布局算法，說明ERRTH算法可以有效減少復雜網絡中的擁擠區域.再從點分布方差來看，ERRTH算法布局后的節點分布更為合理，可以降低節點擁擠導致的布局混亂和區域內節點的密集程度.

ERRTH算法的邊長偏差和節點分布偏差低于其他布局算法，說明ERRTH算法相較于其他算法社區內的節點布局偏差較少，節點分布結果更均勻，更符合復雜網絡布局的美學標.ERRTH算法為達到明確社區內節點層次結構的目的而采用徑向樹進行二次布局，這部分占用時間過多導致ERRTH算法的時間略高于其他算法，但算法之間差距不大，并且尚在用戶可容忍時間范圍2～8 s之內.

表1 Dolphins網絡的實驗結果

表2 Football網絡的實驗結果

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

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

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