復雜網絡聚類特征層次布局算法

摘 要： "網絡聚類模式發現是網絡分析中的一項重要任務，好的網絡布局應能體現網絡中的聚類特征，并允許用戶從不同層次探索網絡結構。為此，基于社團劃分和多層次布局思想提出了聚類特征層次布局算法。首先利用種子節點和個性化PageRank對網絡實現社團劃分；其次根據劃分結果對網絡進行粗化，并設計了粗化網絡初始布局；然后利用節點度信息改進力導向模型以完成細化；最后，為驗證所提算法的有效性，設計了從整體到局部的實驗。實驗表明所提算法能夠在有效時間內生成高質量的布局結果，與現有布局算法相比，所提算法更能真實展示網絡聚類特征，同時兼顧網絡微觀結構，能夠滿足用戶從不同層次探索網絡結構的需要。

關鍵詞： "復雜網絡； 聚類特征； 個性化PageRank； 社團劃分； 多層次布局

中圖分類號： "TP931 """文獻標志碼： A

文章編號： "1001-3695（2022）02-026-0479-06

doi：10.19734/j.issn.1001-3695.2021.07.0272

Complex network clustering feature multi-level layout algorithm

Zhou Rui1， Wang Guijuan1， Deng Haotian1， Cai Mengjie1， Zhao Weixin1， Tan Boyou1， Wu Yadong2

（1.College of Computer Science amp; Technology， Southwest University of Science amp; Technology， Mianyang Sichuan 621000， China； 2.College of Computer Science amp; Engineering， Sichuan University of Science amp; Engineering， Zigong Sichuan 643000， China）

Abstract： "The discovery of network clustering patterns is an important task in network analysis.A good network layout should reflect the clustering characteristics of the network and allow users to explore the network structure from different levels.For this reason，based on the idea of community division and multi-level layout，this paper proposed a clustering feature hierarchical layout algorithm.First，used seed nodes and personalized PageRank to divide the network.Secondly，it coarsened the network according to the results of the division，and designed the initial layout of the coarsened network.Then it used the node degree information to improve the force-oriented model to complete the refinement.Finally，in order to verify the effectiveness of the algorithm，experiments from the whole to the part were carried out.The experiment shows that the algorithm can generate high-quality layout results within an effective time.Compared with the existing layout algorithms，the proposed algorithm can truly display the network.Clustering features，while taking into account the network microstructure，it can meet the needs of users to explore the network structure from different levels.

Key words： "complex network； clustering characteristics； personalized PageRank； community detection； multi-level layout

0 引言

復雜網絡是對現實世界復雜系統的抽象，對復雜網絡的分析有助于理解真實的復雜系統。網絡可視化作為分析網絡數據的有力工具之一，其將網絡數據表現為圖形以直觀地展示網絡的結構和特征。網絡布局算法是網絡可視化的基礎，旨在通過優化相關指標來計算網絡中節點的位置，以實現網絡繪制。

在眾多的網絡布局算法中，力導向模型是一類經典布局模型，通過給網絡中的節點、連邊添加力來實現自動布局。Eades［1］將節點模擬為鋼圈、將連邊模擬為彈簧，通過模擬鋼圈在彈簧力作用下的運動來進行布局。文獻［2］在此基礎上引入節點間理想距離，并通過最小化理想距離和歐氏距離差將布局轉換為能量優化問題。FR（Fruchterman-Reingold）算法［3］基于“存在連邊的節點應繪制得比較接近，而同時節點之間不應繪制得太近”這一準則，在所有節點之間添加斥力、在具有連邊的節點間添加引力來實現布局。

網絡數據規模的增加給算法效率和布局質量都帶來了新的挑戰。為了提高布局算法的效率，空間分解［4］被引入網絡布局中來降低斥力計算所花費的時間。Walshaw［5］提出多層次布局方法來加快布局速度，該方法通過遞歸合并節點來將原始網絡粗化以得到規模較小的粗化網絡，并在最粗化網絡上進行布局，最后以該布局為基礎逐級還原展開網絡進而完成布局。此后，一些基于空間分解、多層次布局思想的算法相繼被提出。Jacomy等人［6］整合不同的技術，包括空間分解、依賴度數的排斥力以及局部和全局的自適應溫度提出了ForceAtlas2算法，并作為Gephi［7］的默認布局算法。為同時保證布局質量和算法性能，Hu［8］結合多層次布局思想和空間分解提出了Hu算法。Martin等人［9］通過結合邊切割、多層次思想、平均連接聚類提出了OpenOrd算法。

在布局質量方面，網絡數據規模的增加使得網絡布局結果中出現毛球［10］。傳統網絡布局算法主要優化美學標來增強布局的可讀性，使得網絡結構難以識別，然而最近的研究表明需要更具體的度量來發現網絡中的模式［11］。

聚類是網絡中的一個重要模式，網絡中的聚類體現在網絡中的社團結構，處于同一社團內的節點間連接更為緊密，而位于不同社團的節點間連接更為稀疏。社團結構是復雜網絡普遍存在的特征之一，社團發現也是網絡分析中的一項重要任務。因此在布局的時候屬于同一社團的節點應彼此靠攏而不同社團的節點應相互分開，以體現網絡中的社團結構。為此，一些專注于表達網絡中社團結構的布局算法相繼被提出。文獻［12］改進Louvain算法來防止網絡中大社團的過度合并，同時及時合并小的社團，并引入社區力來展示網絡中的社團結構。文獻［13］結合社團力和K-means算法來實現網絡中的社團展示。這些算法在規模小的網絡數據上有較好的布局效果，但其本身時間復雜度較高難以擴展至較大規模的數據上。文獻［14］將力導向布局算法與社團結構特征相結合，對網絡進行壓縮以展示網絡的中觀尺度結構，但壓縮讓用戶無法觀察到網絡的微觀結構，也導致了社團內部的結構信息丟失。文獻［15，16］利用Infomap、Louvain等社團劃分算法和多層次布局思想來對網絡進行布局，并比較了不同劃分算法對布局結果在算法性能和布局質量上的差異。但其算法主要針對網絡的整體結構而忽略了網絡局部信息，得到的布局結果往往不能很好地兼顧網絡局部結構。Huang等人［17］利用社團劃分算法預先對網絡進行劃分以得到社團結構，并根據社團信息計算社團內部和社團之間節點間的加權引力和斥力以凸顯網絡社團結構。對于規模較大的網絡，該方法還可利用社團結構對網絡進行壓縮，以擴展為多層布局算法。同樣地，該方法未能較好地保持網絡的局部結構。基于社團結構的網絡布局使得社團之間的連接容易察覺，而社團內部的結構往往不能充分呈現。

復雜網絡由眾多社團構成，如果一個布局清晰地展示了網絡社團內部和社團間的結構，那么網絡就會被很好地顯示［17］。基于該思想，本文結合社團劃分算法和多層次布局思想來突出展示網絡中社團結構的聚類特征，同時兼顧網絡社團內部的結構信息。

本文主要貢獻如下：a）結合基于個性化PageRank的局部社團劃分算法和多層次布局提出了復雜網絡聚類特征層次布局算法，用于突出展示網絡中的聚類模式；b）提出了個性化理想距離來改進FR算法以清晰展示網絡社團內部結構，更加真實地還原社團的形狀；c）設計了從整體到局部的實驗驗證了本文算法的有效性。

1 相關算法

1.1 社團劃分算法

社團劃分算法旨在檢測出網絡中存在的社團結構，可分為全局社團劃分和局部社團劃分。全局社團劃分算法從全局出發，通過圖分割、層次聚類來實現社團劃分。常見的全局劃分算法包括基于模塊度優化的社團劃分算法、基于標簽傳播的社團劃分算法等［18］。

而局部社團劃分往往從網絡中的一個或多個節點出發，尋找包含這些節點的社團。局部社團劃分算法主要通過擴展種子節點來實現劃分，因此算法通常包含三個步驟［19］：a）根據策略選中網絡中的種子節點；b）計算所有節點與種子節點的相似度或接近度，并按相似度對所有節點進行降序排序；c）根據排序依次將節點加入種子節點所在社團，并在“合適”的時候停止。

1.2 FR算法

FR算法是經典的力導向算法，因其算法思想簡單、易于實現被廣泛使用。在FR算法中，網絡中的連邊被模擬為彈簧、節點被模擬為具有相同電荷的電子，分別對應這基于胡克定律的引力和基于庫侖力的斥力。在力的作用下，節點會向著力的方向運動直到達到穩定狀態。

通常引力、斥力計算公式為

f r= k2 d

f a= d2 k """"（1）

其中： d 表示節點間的歐氏距離。由式（1）可知，當真實距離 d=k 時，斥力等于引力。因此 k 表示節點間的理想距離，定義為

k= "S |V| """"（2）

其中： S 表示布局面積； |V| 表示網絡節點的數量。

1.3 多層次布局

多層次布局算法通常包括網絡粗化、初始布局和網絡細化［5］三個步驟。在粗化階段，網絡中的節點被逐步壓縮、合并，直到網絡的規模達到某一閾值或壓縮效率比達到某一閾值。粗化階段的產物是最粗化網絡，該網絡規模應遠小于原始網絡。初始布局階段是對最粗化網絡的布局。此后，細化階段以上一階段的布局為基礎，插值、細化網絡直到達到原始網絡。

2 本文算法

2.1 設計需求

面對大規模復雜網絡數據，布局算法首先需考慮的仍是效率問題。其次，社團結構作為復雜網絡普遍存在的特征之一，算法布局應能清晰展示網絡中社團和社團間的連接關系，即要求布局能體現網絡的聚類特征；同時應能夠揭示社團內節點是如何組織的，即對應網絡的微觀結構。因此，本文算法提出以下需求：R1表示算法能在有效時間內得到布局；R2表示算法能體現網絡的聚類特征；R3表示算法能兼顧網絡微觀特征。

2.2 設計細節

為體現網絡中的聚類特征，需預先對網絡進行社團劃分以得到社團結構。社團劃分部分會增加算法的總體耗時，為減少該部分的計算時間，需要選擇一個低時間復雜度的社團劃分算法（R1）。相比于全局社團劃分算法，局部社團劃分算法從種子節點出發，通過擴展種子節點來獲得社團結構，具有天然的并行性。此外，局部社團劃分算法自下而上地尋找種子節點所屬的社團，更好地保留了網絡的局部社團結構。

結合多層次布局思想，利用社團結構對網絡進行壓縮以得到規模更小的粗化網絡。為體現網絡中的聚類特征并展示各個聚類間連接關系，利用加權排斥力和吸引力對最粗化網絡進行布局使得布局能體現網絡整體結構（R2）。

在細化階段，為兼顧社團內部的結構，利用節點度信息得到各節點對間個性化理想距離，以改進FR算法完成細化（R3）。

2.2.1 數據預處理

本文算法考慮的復雜網絡為無向、無權的網絡，因此對于有向網絡或帶權網絡需經過預處理轉換為無向、無權的網絡。對于有向網絡，有兩種處理方式：a）如果一對節點之間存在兩條有向邊則合并為一條無向邊，否則刪除。這種方式可能會導致網絡中的連邊大量減少，也會造成部分節點成為孤立節點。b）合并節點間雙向連邊的同時將節點間只有一條有向邊改為無向邊，為了盡可能保留更多的節點和邊，本文選擇了第二種方式。對于帶權的網絡，將所有邊權重設置為1。此外，對于存在自環邊的網絡，刪除其中的自環邊。

2.2.2 基于個性化PageRank社團劃分的粗化

局部社團劃分算法通常包含種子節點選擇、種子節點擴展和社團合并三個步驟。算法首先選擇部分節點作為種子節點，并基于種子節點擴展以獲得包含該種子節點的社團結構。種子節點的選擇較為重要，理想的種子節點應隸屬于不同社團且為社團的中心。有關研究表明，網絡中度高的節點易成為社團的中心節點［20］，因此本文基于節點的度來實現種子節點的選擇。同時，為了使種子節點更好地覆蓋網絡，在選擇種子節點時忽略已經選擇節點的鄰居節點及其二階鄰居節點。種子節點算法步驟描述如下：

算法1 種子節點選擇算法

輸入：鄰接矩陣 A ；種子節點數量K 。

輸出：種子節點集合 seeds 。

a）基于鄰接矩陣 A ，計算出各個節點的度信息。

b）根據度信息對節點進行降序排序，得到節點序列 seq 。

c）根據序列 seq 依次將節點加入 seeds 。

對于節點 i，如其未被標記則加入seeds ，并將其鄰居節點和二階鄰居節點標記；

若 seeds 中節點數量大于 K 或到達 seq 尾部則停止算法，否則繼續執行步驟c）。

值得注意的是，種子節點數量 K 的設置可以根據網絡規模進行調整。同時 K 的設置并不會影響算法的結果，當 K 過大時后續流程會對重合度較高的社團進行合并；當 K 過小時，后續流程會在未覆蓋的節點中選擇新的種子節點以繼續算法。

在得到種子節點后，基于種子節點進行擴展以完成社團劃分。擴展階段需要計算種子節點與其余節點間的相似度，與種子節點越相似則越可能屬于種子節點所屬社團。本文使用個性PageRank來計算網絡中其余節點與種子節點的相關性。個性化PageRank繼承了PageRank的思想，模擬用戶通過鏈接隨機訪問網絡中節點的行為來計算穩定狀態下各個節點受訪問的概率。與PageRank不同的是個性化PageRank在隨機游走中的跳轉行為具有偏好性。因此，個性化PageRank可被用于計算其余節點與種子節點的相關性。基于隨機游走的個性化PageRank給定一個參數 α 表示跳轉概率，則在隨機游走過程中，在任意一個節點式會以 α 的概率選擇該節點的鄰居節點進行游走；以 1-α 的概率回到偏好初始節點。個性化PageRank值計算公式為

ppr "s（v）=（1-α） 1 |S| +α∑ n u=1 "A uv d u "ppr "s（v） ""（3）

式（3）表示，隨機游走過程中，對于當前點 u 會以 αA uv/d u 跳轉到點 v ，同時有 1-α 的概率回到種子節點集 s 。其中向量 ppr "s 被稱為與種子節點集 s 相關聯的個性化PageRank向量。

對于種子節點 s ，首先基于種子節點 s 計算網絡中所有節點與之相關聯的個性化PageRank值。直接使用冪迭代計算個性化PageRank向量所花費的時間開銷太大，因此本文使用書簽著色法［21］來計算。然后根據 ppr "s 對節點進行降序得到序列 n 1，n 2，…，n m，其中 ppr "s（n i）gt; ppr "s（n i+1） 。并根據排序依次將節點 n i 加入種子節點所處的社團 c ，并計算此刻的傳導率。選擇取得最大傳導率的節點作為切點，將切點及切點前的節點所構成的社團作為基于種子節點 s 擴展得到的社團 c s 。傳導率計算公式為

cond（ c i） = cut （c i） "min（links （c i，V） ，links（ "V c i ，V））

cut （c i） =links（ c i， V c i ） """"（4）

其中：links（ c i，c j） 表示集合 c i 中節點與集合 c j 中節點間連邊之和； V 表示全體節點組成的集合。算法步驟描述如下：

算法2 基于個性化PageRank的社團劃分算法

輸入：鄰接矩陣 A ，種子節點集S 。

輸出：種子節點集 S 擴展得到的社團 c s 。

a）適用書簽著色算法得到基于 S 的個性化PageRank值 ppr "s 。

b）根據 ppr "s 對節點進行降序排序得到序列 seq 。

c）根據序列 seq 依次將節點加入社團 C 。

對于節點 i "，將其加入社團 C ；

計算此時的傳導率 Con i ；

若已達到序列尾則執行步驟d），否則繼續執行步驟c）。

d）尋找 Con 中的最大值 Con max ，以 max 作為切點，將 seq 中 max 及 max 前的節點組成的社團記為 c s ，并返回以結束算法。

對于 K 個種子節點，經過上述步驟可得到 K 個社團，若網絡中節點重復率過低可繼續在未覆蓋的節點中選擇新的種子并重復上述步驟，直到所有節點均被覆蓋或節點覆蓋率超過預設定的值。然而，基于種子節點擴展得到的社團可能存在高度重合的情況，為此，在完成社團劃分后需對重合度高的社團進行合并。本文使用式（5）來計算社團間的重合度

overlap= |c i∩c j| "max （|c i|，|c j|） """（5）

當兩個社團的重合度較高時，對其進行合并。同時對于一些規模超大的網絡，劃分后的社團仍具有大量節點，可對社團內部進行二次劃分以形成多層結構。

為粗化網絡，根據劃分結果對網絡中的節點進行壓縮。將網絡中的社團 c i 抽象為節點 n i ，則 n i 與 n j 間的連邊權重為社團 c i 與 c j 的連邊和。由于劃分得到的社團結構可能重疊，所以在對網絡進行抽象時需要考慮重疊社團的處理。本文將屬于且僅屬于同一個社團的節點抽象為一個節點，并將重疊的社團單獨抽象為節點。即將全部屬于且僅屬于社團 i 的節點抽象為節點 c i ，把同時屬于且僅屬于社團 i 和 j 的節點抽象為 c ij ，依此類推，以得到一個節點代表一個社團的粗化網絡。

2.2.3 改進FR算法的多層次布局

在粗化網絡中，一個節點代表一個或多個社團，為了清晰地展示網絡各個社團間的連接關系、使社團邊界明顯，設計了粗化網絡初始布局。計算粗化網絡布局時引力、斥力及重力公式為

f r=k×num i×num j/d

f a=d2×w ij/（ k×num i×num j ×w max）

f g=k g×num i×d """"（6）

其中： num i 表示社團 i 內部的節點數量； w ij 表示邊權重； k 為距離系數用于調節節點間距離。

在得到初始布局后，根據初始布局對網絡進行細化、還原，即對應社團內部節點的布局。傳統FR布局算法基于節點均勻分布和邊長統一等原則， 因此不能很好地體現網絡的結構信息，如網絡中的中心節點、網絡形狀等信息。本文利用節點度來改進FR布局，即度大的節點之間的距離應較大，度小的節點之間的距離應較小。為了實現這一目標，本文改變了FR算法中節點間統一理想距離，為每一對節點分別計算理想距離 tk 。

tk（i，j）= k d id j "|V| """（7）

其中： d i 表示節點 i 在社團內的度； |V| 表示節點 i 所屬社團內節點的數量； k 為距離系數，與節點的數量相關。

引力、斥力計算公式為

f r= tk2 dis

f a= dis2 tk """"（8）

其中： dis 表示節點之間的歐氏距離；同時為了使布局位于畫圖中心，為每個節點添加了指向布局中心的重力。

f g=k g×dis×d i ""（9）

其中： dis 表示節點 i 與畫布中心的歐氏距離； k g 為系數用于控制重力的強度。如此，網絡中度大的節點所受到的重力越大、越容易處于布局中心。

圖1中展示本文提出的個性化理想邊長度布局和統一理想邊長度布局，對比可知圖（a）中度大的節點間距離遠大于度小的節點間距離，突出展示了網絡中度大的中心節點。

此外，基于隨機初始節點位置的布局算法得到的布局結果不唯一，因此本文使用初始化布局來唯一確定布局結果。同時，一個好的初始化布局有利于節點快速達到收斂位置。

初始化布局算法基于“度大的節點應位于布局中心，與外部社團有連接的節點應位于相應方向的布局邊緣”這一原則來實現對社團內部節點位置的初始化。此時節點的度指社團內部的度，即計算節點度時僅考慮與社團內節點間的連邊。如圖2所示，初始布局使用圓形布局，并根據社團內節點數量來計算初始布局面積。首先將社團內的節點分為只與社團內節點相連的節點和與其他社團內節點有連邊的節點兩類，分別記為內部節點和邊緣節點。社團內與其他社團相連的邊緣節點的理想分布位置是區域A和B所組成的扇形，而其余內部節點的分布位置應在區域C和D中。其中邊緣節點中度大的節點表示與社團聯系較為緊密，應放置在區域B，而其他度較小的節點應放置在區域A。區域A和B所組成扇形的面積由邊緣節點占所有節點比例計算而得。

因此，社團內部節點的初始位置計算公式為

x i=r× cos "α

y i=r× sin "α

r= d i d max

α= "2π- （θ 1-θ 2） |V inner| ×i ""（10）

邊緣節點的初始位置計算為

x i=r× cos "α

y i=r× sin "α "r= d i d max

α= （θ 1-θ 2） |V outer| ×i ""（11）

此外，為了提高算法效率，在細化階段本文還使用了四叉樹空間分解［4］來加速布局算法。

2.3 算法復雜度分析

本文算法耗時主要由粗化階段、初始布局和細化階段組成。 對于一個網絡 G=（V，E） ，在粗化階段中，局部社團劃分使用標簽著色法來計算基于某一種子節點的個性化PageRank向量，其時間復雜度接近線性。則社團劃分階段通過 K 種子進行社團劃分的時間復雜度為 O（|V|） ；對于初始布局階段，最粗化網絡往往僅包含少量的節點和邊，記為 G 1=（V 1，E 1） ，則初始布局階段斥力、引力計算時間復雜度為 O（|V 1|2+|E 1|） ；在細化階段，布局的規模變成了某個社團內部，記為 G 2=（V 2，E 2） ，其中 |V 2|lt;|V|/K ，由于使用了空間分解來近似計算斥力，其布局時間復雜度為 O（|V 2| "log "|V 2|+|E 2|） 。

3 實驗結果與分析

3.1 實驗設計

為展示本文算法的布局效果并驗證算法的有效性，選取了如表1所示的不同規模、 不同類型的復雜網絡數據集進行實驗。所選數據集［22，23］主要包括社交網絡、引文網絡以及樹型網絡等。表1中所示的模塊度和社團數量均是louvain算法［24］計算得到的結果，其中部分數據為有向網絡、帶權網絡，統計的信息均為經過數據預處理后得到無向、無權網絡信息。

其次，為進行對比實驗，選取了FM3［25］、OpenOrd［9］、Hu［8］、ForceAtlas2［6］以及GRA［17］算法用做對比。其中FM3、OpenOrd、Hu、GRA均是基于多層次布局思想實現的、用于大規模網絡的經典布局算法；同時GRA算法還利用社團信息來計算社團內部與社團間節點之間的加權排斥力和吸引力。

對應第2章提出的三個需求設計了如下三部分實驗。首先在算法的效率方面，統計并比較不同數據在不同算法上的運行時間；其次，在布局質量方面，從整體上主要驗證本文算法是否能有效展示網絡中的聚類特征以及各個聚類間的連接關系；在局部上主要驗證本文算法生成的布局是否能夠清晰地展示各個聚類內結構信息。

所有實驗結果均在同一設備上運行所得，設備相關配置如下：CPU為Intel i5-8500@3.00 GHz，內存大小為12 GB。其中OpenOrd、Hu、ForceAtlas2算法布局結果通過Gephi［7］運行得到，FM3算法代碼來自OGDF［26］。

3.2 實驗結果

3.2.1 算法耗時對比

各算法在不同數據集上運行時間如表2所示，其中由于ForceAtlas2算法為持續式算法，需人為停止算法，其收斂較快，所以本文將其停止條件設置為算法迭代500次；GRA算法收斂速度較慢，迭代次數太多，在此統計了最多2 000次迭代時間。再者，GRA算法在部分數據上耗時太久，在有限時間內未得到結果，故未統計。

實驗結果如表2所示， 除部分規模較小的網絡外，本文算法的耗時均低于其他算法。本文算法利用社團劃分對網絡進行粗化以實現多層次布局，而對于小規模的網絡而言，使用社團劃分所帶來的耗時遠高于多層次布局所節約的時間。隨著網絡規模的增加，使用多層次布局思想的算法會體現出更好的優越性。

3.2.2 網絡聚類特征展示評估

blogs數據集是2005年記錄的關于美國政治的博客之間超鏈接組成的網絡。由表1可知，該網絡共包含12個社團。但除兩個社團外其余社團均只包含少量的節點。因此，其布局結果能明顯地被分為兩部分。如圖3所示，除FM3和Hu算法外，其余算法的布局結構都能明顯地將網絡分為兩部分，但OpenOrd和ForceAtlas2算法的布局節點分布密集以至于較多重疊。相比而言，本文算法的布局結果中兩個聚類邊界更為清晰。

圖4展示了Facebook_4039數據集在不同布局算法下得到的布局結果，該數據是典型性的社交網絡數據，具有較強的社團結構。對比可知，ForceAtlas2的布局結果和OpenOrd的布局結果中聚類內的節點布局過于緊湊，以至于出現大量節點重疊，無法從中獲取聚類規模和內部結構等信息；GRA得到的布局符合傳統美學標準，具有對稱性、節點分布均勻等特點，但各個聚類邊界較為模糊，同時各個聚類間存在邊大量交叉的情況；Hu和FM3的布局能有效展示網絡的骨架結構，同時在一定程度上兼顧網絡宏觀和中觀結構，但不能體現各個聚類內的結構特征。與這些算法相比，本文算法能同時展示網絡整體結構、各個聚類間的結構信息，兼顧整體與局部。并且能體現各個聚類的規模以及形狀，這一點將在后續進一步驗證。

除視覺效果外，本文采用文獻［11］的度量指標來定量評估本文算法在聚類模式展示的有效性，該度量指標被提出用于衡量布局算法是否真實表現了網絡的聚類模式。對于一個布局，首先忽略其連邊、僅考慮節點位置，并根據節點位置對其聚類，通過計算聚類結果與網絡真實社團結構相似度來評價布局的好壞。根據其思想，對于沒有真實社團結構的網絡可使用社團劃分算法得到的結果作為真實社團結構。本文使用的聚類算法是DBSCAN，使用調整互信息（adjusted mutual information，AMI）來衡量聚類間的相似性，該值越高表示兩組聚類越相似，即布局算法越能真實表現網絡聚類特征。

實驗結果如表3所示。由于DBSCAN需設置參數，表中的AMI值均是循環多次不同參數得到的最高值。由表3可知，與其他算法相比，本文算法在大部分數據集上能取得最高的AMI值。在少部分數據集上的AMI值接近或略低于取得最高值的算法，但遠高于最低值。說明本文算法在布局上能夠較好地還原網絡的真實社團結構，有效反映網絡中的真實聚類特征。

3.2.3 網絡局部結構展示評估

在上述實驗中，一個布局可通過聚類算法得到多個的聚類，本文算法能夠較好地體現網絡的聚類特征。然而一個好的布局算法還應能清晰、正確地展示網絡聚類即社團內部結構，以給予用戶探索網絡局部結構的能力。為驗證本文算法展示網絡局部結構的有效性，選擇了FM3、Hu以及GRA算法與本文算法進行對比實驗，因在3.2.2節實驗中OpenOrd和ForceAtlas2算法的布局結果中社團內部節點重疊過多，難以體現局部結構，故未選擇。

對于Facebook_4039數據集，FM3算法的布局被劃分為八個聚類；Hu算法的布局被劃分為九個聚類；GRA算法的布局被劃分為11個聚類；而本文算法的布局被劃分為14個聚類。其中，聚類的數量均為有效聚類，即刪除掉部分僅包含小于10個節點的聚類。

圖5分別展示了本文算法、FM3、Hu和GRA算法在Facebook_4039上的三個聚類。對比可知GRA算法的布局圖（l）（n）中節點分布較為均勻、邊長較為統一；FM3算法的布局圖（d）（f）未能完全展開，無法體現聚類本來的結構和形狀；圖（g）（h）（m）同理；而本文算法的布局中，其結構相對展開完全，能還原局部結構的形狀、特征。

文獻［17］中列舉了社團常見的三種結構，其中包括中心節點—邊緣節點結構和類全連接結構。圖5中，對于中心節點—邊緣節點這一結構，例如圖（c）（f）（k）以及（h），所有算法的布局均能體現出中心節點，而本文算法的布局圖（c）更還原了其原本的形狀。對于類全連接結構，例如圖（a）（e）（m），FM3和GRA算法的布局節點重疊較多，以至于無法判斷節點數量，呈現“毛球”形狀，與本文算法相比，其無法體現聚類的規模。

進一步，本文使用了以下三個指標［27］來評估上述算法在各個聚類上的布局質量：a） M c 邊交叉最小化，用于衡量布局中邊交叉數量的多少；b） M s 形狀度量指標，用于衡量布局是否真實反映了網絡的形狀；c） M a 該指標的量化標準為最大化節點連邊的最小入射角，通過計算相鄰入邊射角度的平均差獲得。

實驗結果從圖6中可知，對于 M c 指標而言，四個算法都能取得較高的值且差異不大；而對于 M s和M a 指標，FM3、Hu和GRA算法大部分聚類評分較低，僅個別聚類分值較高。

取平均值后結果見表4，可知本文算法的平均值在各個指標上均高于其他算法。其中 M s和M a 顯著高于其他算法。表明本文算法生成的布局在局部上與其他算法相比表現出邊交叉更少、相鄰邊入射邊角度差更小，同時能更好還原其局部結構的形狀，表現出較好的布局效果。

綜上，本文算法能在有效時間內生成較高質量的布局，在整體上本文算法能夠突出網絡的聚類特征，在局部上也能清晰展示聚類內部結構，給予用戶從不同層次探索網絡結構的能力。

4 結束語

針對復雜網絡聚類特征展示需要，本文基于局部社團劃分和多層次布局思想提出了一個兼顧網絡整體結構和局部細節的網絡布局算法。算法利用種子節點和個性化PageRank對網絡進行社團劃分，并利用社團結構對網絡進行粗化。設計加權引力和斥力來計算粗化網絡布局，并利用節點度信息改進FR算法來細化網絡。實驗結果表明，在效率方面，本文算法在絕大部分網絡上運行時間少于其他的算法；在布局質量方面，整體上能較好地體現網絡的真實聚類特征，在局部上兼顧了聚類內的網絡結構、真實還原其結構形狀。滿足用戶對不同層次探索復雜網絡結構的需要。在后續的工作中，將繼續改進本文算法，并結合動態網絡布局，將基于社團結構的布局算法擴展到動態網絡中。相較于靜態網絡而言，時變的動態網絡更加貼切真實變化的復雜系統。

參考文獻：

［1］ "Eades P.A heuristic for graph drawing［J］. Congressus Numerantium ，1984， 42 ：149-160.

［2］ Kamada T，Kawai S.An algorithm for drawing general undirected graphs［J］. Information Processing Letters ，1989， 31 （1）：7-15.

［3］ Fruchterman T M J，Reingold E M.Graph drawing by force-directed placement［J］. Software：Practice and Experience ，1991， 21 （11）：1129-1164.

［4］ Barnes J，Hut P.A hierarchical "O（N "log "N ） force-calculation algorithm［J］. Nature ，1986， 324 （6096）：446-449.

［5］ Walshaw C.A multilevel algorithm for force-directed graph drawing［C］//Proc of the 19th International Symposium on Graph Drawing.Heidelberg，Berlin：Springer，2011：171-182.

［6］ Jacomy M，Venturini T，Heymann S， et al. "ForceAtlas2，a continuous graph layout algorithm for handy network visualization designed for the Gephi software［J］. PLoS One ，2014， 9 （6）：e98679.

［7］ Bastian M，Heymann S，Jacomy M.Gephi：an open source software for exploring and manipulating networks［C］//Proc of the 3rd International AAAI Conference on Weblogs and Social Media.Palo Alto，CA：AAAI Press，2009：361-362.

［8］ Hu Yifan.Efficient，high-quality force-directed graph drawing［J］. Mathematica Journal ，2005， 10 （1）：37-71.

［9］ Martin S，Brown W M，Klavans R， et al. OpenOrd：an open-source toolbox for large graph layout［C］//Proc of Visualization and Data Analysis.2011：786806.

［10］ Eades P，Hong S H，Klein K， et al. Shape-based quality metrics for large graph visualization［C］//Proc of the 23rd International Symposium on Graph Drawing and Network Visualization.2015：502-514.

［11］ Meidiana A，Hong S H，Eades P， et al. A quality metric for visualization of clusters in graphs［M］//Archambault D，Tóth C.Graph Drawing and Network Visualization.Cham：Springer，2019：125-138.

［12］ 趙潤乾，吳渝，陳昕.大規模社交網絡社區發現及可視化算法［J］.計算機輔助設計與圖形學學報，2017， 29 （2）：328-336. （Zhao Runqian，Wu yu，Chen Xin.Large-scale social network community discovery and visualization algorithm［J］. Journal of Computer-Aided Design and Computer Graphics ，2017， 29 （2）：328-336.）

［13］ 吳渝，李藻旭，李紅波，等.展示復雜網絡社團結構的社團引力導引的布局算法［J］.計算機輔助設計與圖形學學報，2015， 27 （8）：1460-1467. （Wu Yu，Li Zaoxu，Li Hongbo， et al. "Layout algorithm of community gravitational guidance showing complex network community structure［J］. Journal of Computer-Aided Design and Computer Graphics ，2015， 27 （8）：1460-1467.）

［14］ 吳玲達，張喜濤，孟祥利.基于社團結構節點重要性的網絡可視化壓縮布局［J］.北京航空航天大學學報，2019， 45 （12）：2423-2430. （Wu lingda，Zhang Xitao，Meng Xiangli.Compression layout for network visualization based on node importance for community structure［J］. Journal of Beijing University of Aeronautics and Astronautics ，2019， 45 （12）：2423-2430.）

［15］ Hong S H，Eades P，Torkel M， et al. Multi-level graph drawing using infomap clustering［C］//Proc of International Symposium on Graph Drawing and Network Visualization.Berlin：Springer，2019：139-146.

［16］ Hong S H，Eades P，Torkel M， et al .Louvain-based multi-level graph drawing［C］//Proc of the 14th Pacific Visualization Symposium.Piscataway，NJ：IEEE Press，2021：151-155.

［17］ Huang Zhenhua，Wu Junxian，Zhu Wentao， et al. Visualizing complex networks by leveraging community structures［J］. Physica A：Statistical Mechanics and its Applications ，2021， 565 （3）：125506.

［18］ 李輝，陳福才，張建朋，等.復雜網絡中的社團發現算法綜述［J］.計算機應用研究，2021， 38 （6）：1611-1618. （Li Hui，Chen Fucai，Zhang Jianpeng， et al. Survey of community detection algorithms in complex network［J］. Application Research of Computers ，2021， 38 （6）：1611-1618.）

［19］ Hollocou A，Bonald T，Lelarge M.Multiple local community detection［J］. ACM SIGMETRICS Performance Evaluation Review ，2018， 45 （3）：76-83.

［20］ Whang J J，Gleich D F，Dhillon I S.Overlapping community detection using neighborhood-inflated seed expansion［J］. IEEE Trans on Knowledge and Data Engineering ，2016， 28 （5）：1272-1284.

［21］ Berkhin P.Bookmark-coloring algorithm for personalized PageRank computing［J］. Internet Mathematics ，2006， 3 （1）：41-62.

［22］ Leskovec J，Krevl A.SNAP datasets：Stanford large network dataset collection［DB/OL］. （2014）.http：//snap.stanford.edu/data/.

［23］ Davis T A，Hu Yifan.The University of Florida sparse matrix collection［J］. ACM Trans on Mathematical Software ，2011， 38 （1）：article No.1.

［24］ Blondel V D，Guillaume J L，Lambiotte R， et al. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics：Theory and Experiment ，2008， 10 ：P10008.

［25］ Hachul S，Jünger M.Drawing large graphs with a potential-field-based multilevel algorithm［C］//Proc of the 12th International Symposium of Graph Drawing.Heidelberg，Berlin：Springer，2004：285-295.

［26］ Chimani M，Gutwenger C，Jünger M， et al. The open graph drawing framework（OGDF）［M］//Tamassia R.Handbook of Graph Drawing and Visualization.2014.

［27］ Kwon O H，Crnovrsanin T，Ma K L.What would a graph look like in this layout？A machine learning approach to large graph visualization［J］. IEEE Trans on Visualization and Computer Graphics， 2018， 24 （1）：478-488. "