基于力導引算法的復雜網絡多細節層級可視化

安沈昊，于榮歡+，薛 瓊

(1.航天工程大學 復雜電子系統仿真重點實驗室，北京 101416；2.中國航天系統科學與工程研究院 信息工程研究所，北京 100032)

0 引 言

網絡拓撲可視化技術能夠以圖形圖像的方式清晰展現復雜網絡中節點的連接情況，幫助人們有效認識和理解網絡內部特征和結構[1]。力導引算法作為目前最常用的網絡拓撲可視化技術，實現簡單、易于理解，適用于大多數復雜網絡結構數據的可視化。但隨著復雜網絡的結構逐漸向多層化、復雜化發展，如何在狹小的屏幕范圍內合理地展現復雜網絡的宏觀整體結構與局部細節結構為基于力導引算法的網絡拓撲可視化帶來了巨大的挑戰。因此，為兼顧復雜網絡拓撲結構在宏觀整體與局部細節方面的可視化分析，本文將力導引算法與層次聚類算法結合，提出了一種能夠在不同細節層級下展示復雜網絡結構特征的可視化方法。首先簡要介紹了幾種經典力導引算法，分析了當前復雜網絡在可視化研究方面的不足。之后在FR(Fruchterman Reingold)算法[2]的基礎上進行改進，提出了一種可變力導引算法(variable force-directed algorithm，VFDA)，通過改變同一層級結構下節點之間的引力來有效展示社團結構與層次結構。最后描述了聚類規則，通過層次聚類算法對節點進行聚類并建立網絡多細節層級模型，實現不同層次下的網絡拓撲結構可視化。通過對復雜網絡實例數據進行實驗與對比分析，驗證了本文可視化方法的有效性與適用性。

1 經典力導引算法

力導引算法又稱彈簧模型，其原理是將網絡中的節點和邊模擬為鋼環和彈簧，二者共同組成為一個物理系統[3]。確定初始狀態之后，彈簧的相互作用會使鋼環位移，當系統總能量消耗至最小值時鋼環保持靜止。彈簧模型為了減小距離過于遠的兩個節點之間的作用力，并沒有遵循胡克定律，且每次迭代都需要計算節點的受力情況，對大規模網絡進行布局時算法運行度較高、布局效果較差。因此，不少學者在原算法的基礎之上進行了改進，例如KK(kamada kawai)算法[4]、DH(davidson harel)算法[5]、FR算法、LinLog算法[6]等。

KK算法在彈簧模型的基礎上引入了胡克定律，建立了能量模型，將節點位置的求解轉換為系統能量最小值的求解。在胡克定律中，單個彈簧的能量為

E=kx2/2

其中，k為彈簧的彈力系數，x為彈簧的被拉伸量。因此，KK算法的能量公式為

其中，kij節點vi與節點vj之間引力的強度，pi與pj分別表示節點vi與節點vj的位置， |pi-pj| 則表示兩個節點之間的笛卡爾距離，lij表示兩個節點之間的理想距離。KK算法的優點是進一步優化了節點布局，并且加快了算法的收斂。

DH算法受到其它優化方法的啟發而采用了模擬退火思想，即將網絡布局的優化過程模擬為某些物質系統的冷卻過程，當系統溫度衰減至閾值時，系統總能量達到最小值，所有節點不再移動。DH算法的能量模型公式為

f(G)=∑λifi(G)

上式包含了5方面要素，分別是點與點的距離、點與邊的距離、點與邊框的距離、邊的長度、邊的交叉程度，λi為每部分權重，并可以根據所要遵守的美學標準來設置。DH算法的優點在于布局結果能夠達到全局最優值，其缺點是所需時間較長。

FR算法在彈簧模型的基礎上引入了粒子物理理論和模擬退火思想，將節點模擬為粒子，將邊模擬為粒子間存在的引力，所有粒子間均存在斥力，引力與斥力的相互作用使粒子獲得速度與加速度，從而不停運動，多次迭代之后系統溫度不斷下降從而達到動態平衡狀態。在這種設定之下，兩個相互連接的節點會趨于靠近，而所有節點因斥力作用又不會距離過近，節點分布整體上較為均勻。首先對初始化所有節點的位置，之后計算每個節點的受力情況并根據受力情況更新節點位置，根據當前系統溫度選擇是否迭代或停止布局。與上述力導引算法相比，FR算法的聚類效果更加突出，其布局結果的美觀程度也更高，因此本文選擇在FR算法的基礎上進行改進。

LinLog算法通過引入Barnes-Hut算法[7]來減少節點的位置與受力計算量，提高了算法的效率，并且提出了表示聚類分離效果的函數，能夠更好地展示網絡內部結構。其能量公式如下所示，等式右邊第一部分和第二部分分別表示相互連接的兩個節點之間的引力與任意兩個節點之間的斥力。采用Barnes-Hut算法對能量最小值得求解進行優化，當ULinLog(p) 達到最小值時，代表布局結果已為最優值

ULinLog(p)=∑(vi,vj)∈E|pi-pj|-∑(vi,vj)∈V2ln|pi-pj|

2 基于力導引算法的復雜網絡可視化

2.1 問題分析

隨著復雜網絡理論研究的不斷深入，其越來越多的結構特征也逐漸被人們發現與關注。社會與科技的發展使某些領域的復雜網絡規模愈加龐大、結構也更加復雜，例如天地一體化網絡[8]，其網絡結構具有明顯的分層特性，若干個一級節點相互連接組成骨干網，每個一級節點連接著若干二級節點，每個二級節點連接著眾多三級節點，之后依次向下疊加。除此之外，大部分復雜網絡的拓撲結構還兼具社團特性，即父節點與其下眾多子節點組成了一個子網絡，或部分子節點組成了一個子網絡，子網絡內部節點聯系緊密從而構成了一個社團，社團外的子節點單獨與父節點相連。而且，子網絡之間還存在聯系稀疏的節點，即相互連接的兩個節點存在于同一層級中的不同社團中。

目前大多數復雜網絡的結構都具有分層特性，其可視化方法一般基于單層網絡可視化方法和技術來解決新問題，即將多個不同層級的網絡聚合到同一層面，形成一個單層網絡，之后通過單層網絡布局算法進行網絡布局，這種方法雖然易于實現，但忽略了節點的異質性與邊的多元性，不能完全展示網絡的層次信息[9]。因此大部分學者將其與聚類算法結合，通過將不同層級的節點依次聚類，根據顯示層級展示網絡多層結構。比如湯穎等[10]結合FR算法與LinLog算法的優點，提出了一種層級視覺抽象方法，基于結合算法的初始布局結果進行多層級視覺抽象，既能清楚地觀察網絡整體結構，也能有效避免大規模數據帶來的視覺雜亂。劉鳳劍等[11]針對樣本的分集處理問題，提出了一種基于力導引模型的聚類算法，通過控制樣本間距與樣本局部密度，提高了聚類的準確率。于少波等[12]結合空間信息網絡的層次性等特征，總結了多層網絡可視化技術的發展現狀與特點，并分析了目前遇到的問題與挑戰，為多層網絡可視化方法的研究提供了參考與技術支持。

但是，多層特征只是復雜網絡結構特征之一，其另外一個重要的結構特征是社團特征。而上述可視化方法的研究幾乎都僅聚焦于體現復雜網絡的層次結構特征，忽略了其社團結構特征的展示。對于兼具多層化特征與社團化特征的復雜網絡來說，父節點與父節點、父節點與子節點、子節點與子節點之間的連接關系都需要被呈現出來，只展示網絡的層次結構而忽略其社團特征并不能完全展現其結構特性。另外，將力導引算法應用于復雜層次數據的研究目前還較少，因此接下來將基于力導引算法和聚類算法對復雜網絡拓撲結構可視化進行研究。

2.2 總體思路

FR算法可以達到一定程度的聚類效果，但由于為不同節點之間定義了一個理想距離k，遵循節點均勻分布和邊長統一的原則[13]，這使得該算法社團結構的展示不明顯，主要表現為邊長相對一致、子節點過于分散、不同社團的子節點交叉遮擋現象嚴重，難以從布局結果發現明顯的層次結構或社團結構特征。為此，提出了可變力導引算法(VFDA)以改善布局效果。首先在FR算法的基礎上增加同一父節點下子節點之間的引力，使同一子樹、同一社團的節點相互聚攏，通過改變同層次節點之間的邊長展示社團結構與層次結構。為優化斥力的計算，在實現布局的過程中引入Barnes-Hut算法。為進一步優化布局結果，為所有節點增加了一個中心力，使最終布局結果處于場景中心，不會發生偏離。此時，節點將受到多個力，包括來自其它所有節點的斥力、與自身相連接節點的引力、位于布局中心位置的引力。最后，在VFDA算法的布局結果上，基于層次聚類算法對同一層次的節點進行聚類，建立網絡多細節層級模型，根據顯示層級展現復雜網絡社團結構與層級結構。

2.3 基于多力導引算法的網絡拓撲結構布局

2.3.1 算法描述

定義一個無向網絡可由二元組G(V,E) 表示，其中V表示節點集，即V={v1,v2,v3,…}， |V|=N1表示節點數量為N1。E表示邊集，連接節點vi與節點vj的邊可用元素eij∈E來表示， |E|=N2表示邊數量為N2。網絡G可以被劃分為多個社團，所有社團的集合可表示為C={c1,c2,c3,…}。

FR算法布局速度快、易于實現，且布局結果能在一定程度上體現出聚類效果，因此本文選擇在FR算法的基礎上進行改進，其相關定義如下

其中，k表示節點之間的理想距離，C為常數，S為網絡布局結果所處邊框的面積，N1為節點總個數，當系統趨近于穩定狀態時，節點之間的距離將趨近于理想距離k。d表示兩個不同節點之間的笛卡爾距離，fa與fr分別表示兩個相互連接的節點之間的引力與兩個節點之間存在的斥力。

由于斥力則存在于所有節點之間，而引力只存在于兩個相互連接的節點之間，因此下一步改進措施：一是在計算節點斥力方面引入Barnes-Hut算法，加快算法收斂速度；二是在計算節點引力方面改變相關聯節點之間的引力，從而凸顯網絡的社團結構；三是增加中心力，進一步提高布局美觀程度。

Barnes-Hut算法是一種解決N體問題的優化算法，即在經典力學規則下，已知多個物體的質量、位置和速度，在此基礎上求解這些物體的后續運動情況。而復雜網絡的布局問題即可模擬為一個N體問題，所有節點的初始狀態位置隨機并保持靜止，在布局過程中節點受到其它節點的作用力而不斷運動，最終保持靜止。引入Barnes-Hut算法的目的是減少節點間斥力的計算量，其基本思想是將相互接近的m個節點模擬為一個節點，這個節點的位置就是這組節點的質心位置，其質量為該m個節點的質量和。這樣，這組節點斥力的計算次數就由m次縮減到了1次，大大減少了每次迭代的計算量[14]。

通過Barnes-Hut算法計算節點斥力分為以下3個步驟：

(1)建立節點四叉樹

四叉樹是一種每一個父節點最多可以有4個子節點的樹形結構。在2D平面上，將布局所在的平面不斷遞歸地分為4個同樣的子區域，每個子區域就代表父節點下的一個子節點。如果某個子區域內沒有節點，該子區域為一個葉子結點，不再對其進行劃分。當某個子區域內存在多個節點時，該子區域為一個非葉子節點，之后繼續對其進行劃分，直至之后的子區域內最多只存在一個節點，完成后的節點四叉樹如圖1所示。

圖1 節點四叉樹

(2)計算質心

按照面積由小至大(從四叉樹底部由下至上)依次計算每個包含節點的子區域的質心位置，只包含一個節點的子區域的質心位置則直接為該節點的坐標。

(3)計算節點斥力

計算節點vi所受斥力時，需要從四叉樹的根節點開始由上至下遍歷樹中所有節點。令w表示非葉子節點所代表的子區域的寬度，dvi表示節點vi到該非葉子節點質心的距離，設定判定距離大小的閾值θ。如果w/dvi<θ， 那么這個非葉子節點距離該節點足夠遠，則將其內部所有節點模擬為一個節點，其位置就是該非葉子節點的質心；如果w/dvi>θ， 則在其子節點遞歸地進行上述操作，最終計算出節點vi所受斥力的合力。

由于計算特定節點所受的斥力可能來自單個節點，也可能來自一組節點，因此對斥力計算公式作出改進

frij=-k2MvjA1/d

其中，k與d的定義不變。定義Mvj為該組節點的質量和或單個節點vj的質量，考慮到本文算法的適用對象以及運算量，統一將每個節點的質量設定為一個固定值，因此Mvj的值僅由該組節點的個數決定。定義A1為斥力系數，可通過調整該值控制斥力大小。節點vi所受斥力的合力為

當應用對象與布局范圍確定之后，理想距離k即可作為一個固定值。此時，從原始引力公式可看出最終引力值fa將只受關聯節點間的笛卡爾距離d影響。而引力值fa與笛卡爾距離d成明顯的正比關系，距離的增大會帶來引力的增大，增加的引力會拉近兩個相互連接的節點，此時距離又將減小，從而使引力減小，其它情況亦是如此，最終在多次迭代后節點間的邊長趨近一致，布局結果難以體現明顯的社團結構。因此，需要從發現社團結構的角度出發，針對兩個相互連接的節點是否處于同一個子樹內對原始引力公式進行改進

strength(vi,vj)=1/(min(degree(vi),degree(vj)))faij=(d-k)*strength(vi,vj)+A2*δ(cvi,cvj)

設定節點vi與節點vj相互連接，faij表示二者之間的引力。當d>k時，等式右邊第一部分為正數；當d

為進一步對布局結果進行美化，使其符合人們的觀察方式，在布局場景中心增加了一個中心力Fc，對所有節點產生引力，其中A3表示引力常數。

最終，節點vi所受到的合力為

F(vi)=Fa(vi)+Fr(vj)

2.3.2 算法步驟

VFDA算法具體步驟如下：

(1)讀取多層網絡結構數據，輸入網絡G(V,E)， 初始化所有節點位置 {Pv1,Pv2,Pv3,…} 和系統溫度T。

(2)建立節點四叉樹，并計算每個含有節點的子區域的質心位置。

(3)計算所有節點之間的斥力與相互連接的連個節點之間的引力，獲得其速度與加速度，更新所有節點的位置 {Pv1,Pv2,Pv3,…}。

(4)根據當前迭代次數計算系統溫度T，若溫度達到閾值，則執行下一步，若溫度高于閾值，則從第二步繼續執行。

(5)輸出所有節點的位置，完成布局。

根據模擬退火算法可知，系統在初始狀態具有較高溫度，通過參數T控制迭代過程中節點的運動速度，溫度越高，節點運動越劇烈，位置的改變量就越大。隨著迭代次數的增加，系統溫度逐漸降低，節點位置的改變量逐漸減小。當參數T衰減至閾值時，系統達到穩定狀態，所有節點處于靜止狀態。

2.4 基于層次聚類算法的網絡多細節層級模型

當在有限的屏幕范圍內對大規模復雜網絡進行可視化處理時，大量的節點和邊會發生擁擠、交叉或重疊等現象，從而影響人們辨別和理解復雜網絡的結構。聚類算法在數據挖掘領域應用廣泛，能夠按照某些標準對數據進行分組，生成簇結構，同一簇內的個體存在某特性下相似的現象。將適用于數據分析的聚類算法與數據可視化的力導引算法相結合，能夠有效幫助人們理解、分析其中的信息[15]。

層次聚類算法通過計算不同個體的相似度來逐步生成簇，相似度可以選擇不同的度量標準，最終建立具有嵌套結構的層次樹，適用于層次數據的聚類分析。因此，本文基于層次聚類算法，定義了一個顯示層級結構的參數L，并將同一根節點下子節點之間的拓撲距離作為相似度的度量標準，采用由下至上的方式逐步建立復雜網絡多細節層級模型。參數L決定在相應層級上顯示聚類結果，參數L高時顯示網絡骨干結構，參數L低時則額外顯示骨干結構下的低層級網絡。

定義一個聚類c可由一個六元組 (sc1,sc2,dc,fc,Vc,Lc) 表示，sc1和sc2分別表示聚類c的兩個子聚類，dc表示兩個子聚類之間的距離，fc表示其父聚類，Vc表示此聚類中所包含的所有原始節點的集合，Lc則表示此聚類的結構層級。首先從最底層葉子節點開始聚類，設定葉子節點vi和vj可分別由 (null,null,0,null,vi,Lvj) 和 (null,null,0,null,vj,Lvj) 來表示，null表示空值。如果二者之間距離dij最近，則將二者進行合并，產生新聚類ck，此時ck可由 (vi,vj,dij,null,(vi,vj),Lck) 表示，而葉子節點vi和vj則分別更新為 (null,null,0,ck,vi,Lvi) 和 (null,null,0,ck,vj,Lvj)。 令父聚類的位置由其兩個子聚類的平均位置確定，父聚類之間的連接關系由其子聚類間的連接關系確定。為突出顯示聚類之間規模的差異，對聚類節點的半徑進行可視化編碼，設置其半徑為所包含的原始節點的個數。由下至上遞歸地尋找距離最近且未被合并過的葉子節點或聚類進行合并，最終生成的網絡層級結構可由圖2的網絡層次結構樹狀示意圖表示。每個單獨的葉子節點可看作葉子聚類，中間節點表示葉子節點合并后生成的聚類，根節點cg表示最終生成的聚類。為不同的聚類設置不通的顯示層級L，當L為特定值時，截取當前顯示層級以上的網絡結構進行展示。

圖2 網絡層次結構樹狀示意圖

3 實驗結果展示與分析

3.1 實驗數據

為檢驗上述可視化方法的有效性，基于WebStorm軟件和D3可視化工具開發了復雜網絡可視化插件，進行基于瀏覽器的測試。本文選擇測試的數據見表1，其中Data-1為某衛星網絡結構數據，包含77個節點與254條邊，節點主要為衛星節點與地面測控站，邊可分為星間鏈路、星地鏈路與地地鏈路。Data-2為某大型網絡結構數據，包含1831個節點與3429條邊。上述兩個數據集都為二層網絡結構，為方便觀察，已對不同分支下的節點進行了顏色的可視化編碼，從表1可看出兩個網絡的社團內邊數遠大于社團間邊數，尤其是Data-1數據，二者社團特征較為明顯，社團內部節點之間聯系緊密，各社團之間也存在較為稀疏的聯系。通過FR算法與VFDA算法分別對兩個數據集進行力導引布局，基于Data-2數據的布局結果構建網絡層級結構，觀察不同層級的網絡結構并進行對比分析，期間設置相同的引力系數與斥力系數。

表1 實驗數據集

3.2 可視化結果分析

首先用FR算法對Data-1數據進行布局，布局結果如圖3所示。雖然能在邊緣處分辨出幾個社團結構，但在圖的中間區域節點分布較為分散，導致不同子樹下的子節點相互混雜，個別社團之間存在交叉現象，造成了視覺干擾。對Data-1數據用VFDA算法進行布局，布局結果如圖4所示。Data-1網絡可大致分為若干棵節點樹，若干父節點組成了一個骨干網，每個父節點下連接著眾多子節點，同時二者又與其它父節點或子節點存在著連接關系，大部分父節點與子節點組成了一個社團，也存在部分子節點自行組成一個小社團的情況，符合該衛星網絡的真實形態。從圖4可看出整個區域幾乎不再存在節點混雜的現象，并且邊的長度不再趨于平均化，不同子樹之間的邊長普遍大于某一子樹內部的邊長，層次結構更加明顯。而受社團內外不同引力的作用，同一社團的節點更趨向布局在一起，不同社團在整體上更加分散，每個節點自帶的斥力也避免了因節點過度聚攏而產生節點重疊的情況，這使得社團結構更加明顯。

圖3 Data-1FR算法布局結果

圖4 Data-1VFDA算法布局結果

為進一步驗證上述可視化方法的適用性，通過FR算法與VFDA算法分別對Data-2數據進行布局，并對布局結果(如圖5和圖6所示)進行對比分析。從圖5可看出，當網絡規模過大時，在不進行縮小的情況下，FR算法在有限的屏幕空間無法展示完整的網絡拓撲結構，并且不同子樹下節點之間存在嚴重的混亂交叉現象，節點與邊的布局也呈現為一種雜亂無章的狀態，給用戶觀察網絡整體結構造成極大干擾。而從VFDA算法的布局結果來看，雖然仍有少數節點在屏幕之外，但已不影響用戶對網絡完整拓撲結構的觀察與理解。且VFDA算法對于同一子樹內的節點具有明顯的聚攏作用，從布局結果可明顯看出該網絡的層次結構與各子樹的布局情況，包括子樹的位置分布與子樹內的社團結構等，大部分子樹都存在分支，父節點下的某一個子節點是另外幾條分支子樹的父節點。

圖5 Data-2FR算法布局結果

圖6 Data-2VFDA算法布局結果

對于復雜網絡來說，其拓撲結構的展現效果主要取決于布局結果中是否存在大量節點與邊的交叉混雜的現象，清晰明了的子樹結構則有助于層次結構與社團結構的展示。因此，從比較父節點處的雜亂情況出發，選擇Data-2中若干個父節點，將兩種算法父節點處單位面積內的節點數目進行對比。如表2所示，同一個數據的不同算法結果表明VFDA能夠聚攏同一子樹下的節點，減輕子樹之間的交叉重疊情況。與FR算法布局結果比較，VFDA算法能夠更清晰地展示多層網絡的社團結構與層次結構，其可視化結果更符合網絡真實形態，也更具觀賞性。

表2 FR算法與VFDA算法父節點附近節點數目對比

在VFDA算法布局的基礎上，通過層次聚類算法建立網絡多細節層級模型，展示網絡特定層級結構，Data-2數據聚類后的布局結果如圖7所示。從中可以看出，在該顯示層級下，同一父節點下的子節點都已與其合并為一個聚類節點，其半徑大小即表示所包含子節點的個數，聚類之間的連接關系也代表了所包含的子節點的連接關系。若所選網絡具有更多層級，則可以依次由下至上再次進行聚類，并進行不同層級的視覺抽象。綜上所述，該可視化方法可以讓人們直接從視覺上簡潔明了地清楚復雜網絡不同層級的拓撲結構與同一層級內的社團結構。

圖7 Data-2層次聚類布局結果

3.3 交互方法

考慮到顯示屏面積、數據規模等因素的影響，上述可視化方法不能盡善盡美地展現多層網絡的拓撲結構，需要通過某些交互手段輔助人們獲取、分析感興趣的信息。基于JavaScript語言的D3相較于其它可視化工具，能夠完美結合數據驅動的操作方式與可視化組件，并具有更加靈活的可視化交互方式[16]。

基于D3為上述可視化方法添加了多種交互式操作，如圖8所示，常規的放大、縮小、平移、旋轉操作能幫助用戶從不同角度、不同尺度，觀察不同區域的網絡拓撲結構，兼顧宏觀結構的概覽與局部細節的分析。當用戶對初始布局結果不滿意時，可先用鼠標點擊選中某個節點，再通過拖拽操作調整被選中節點的位置，直到布局結果為滿意為止。由于在此過程中節點位置不斷發生改變，網絡布局也會不斷進行迭代，最終達到穩定狀態。標記操作通過突出顯示特定的節點與邊，有助于用戶獲得某個感興趣的節點或聚類的連接關系。當鼠標懸停于特定節點上時，該節點會被標記并放大，與其相連的邊與節點的邊緣也會被標記，可清楚看出被選中節點與父節點、其它同一層級子節點的連接關系，也可看出該節點在社團內部的連接關系。

圖8 交互操作

4 結束語

本文首先簡要介紹了幾種經典力導引算法的原理與優劣，針對目前復雜網絡可視化研究方面的存在的不足與多層網絡的結構特點，提出了一種基于力導引算法的復雜網絡多細節層級可視化方法。首先對FR算法進行改進，通過引入Barnes-Hut算法優化斥力的計算，根據兩個節點是否處于同一子樹內來改變二者之間的引力，并增加了中心力，實現了多力導引布局，然后在多力導引布局結果上運用層次聚類算法進行網絡多細節層級模型的構建并展示。從可視化結果的展示與分析來看，該可視化方法具有簡便、直觀的特點，能夠良好地展現復雜網絡的不同細節層級拓撲結構與同一細節層級下的社團結構，能允許用戶通過多種靈活的交互操作實現高層次宏觀結構的概覽與低層級局部網絡細節的分析。局限之處在于當網絡規模變大時，難以在低層級網絡結構的布局中分辨關鍵節點或高一層級的父節點。