基于力導(dǎo)引算法的復(fù)雜網(wǎng)絡(luò)多細(xì)節(jié)層級可視化

安沈昊，于榮歡+，薛 瓊

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

0 引 言

網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)能夠以圖形圖像的方式清晰展現(xiàn)復(fù)雜網(wǎng)絡(luò)中節(jié)點的連接情況，幫助人們有效認(rèn)識和理解網(wǎng)絡(luò)內(nèi)部特征和結(jié)構(gòu)[1]。力導(dǎo)引算法作為目前最常用的網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)，實現(xiàn)簡單、易于理解，適用于大多數(shù)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的可視化。但隨著復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)逐漸向多層化、復(fù)雜化發(fā)展，如何在狹小的屏幕范圍內(nèi)合理地展現(xiàn)復(fù)雜網(wǎng)絡(luò)的宏觀整體結(jié)構(gòu)與局部細(xì)節(jié)結(jié)構(gòu)為基于力導(dǎo)引算法的網(wǎng)絡(luò)拓?fù)淇梢暬瘞砹司薮蟮奶魬?zhàn)。因此，為兼顧復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在宏觀整體與局部細(xì)節(jié)方面的可視化分析，本文將力導(dǎo)引算法與層次聚類算法結(jié)合，提出了一種能夠在不同細(xì)節(jié)層級下展示復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征的可視化方法。首先簡要介紹了幾種經(jīng)典力導(dǎo)引算法，分析了當(dāng)前復(fù)雜網(wǎng)絡(luò)在可視化研究方面的不足。之后在FR(Fruchterman Reingold)算法[2]的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種可變力導(dǎo)引算法(variable force-directed algorithm，VFDA)，通過改變同一層級結(jié)構(gòu)下節(jié)點之間的引力來有效展示社團(tuán)結(jié)構(gòu)與層次結(jié)構(gòu)。最后描述了聚類規(guī)則，通過層次聚類算法對節(jié)點進(jìn)行聚類并建立網(wǎng)絡(luò)多細(xì)節(jié)層級模型，實現(xiàn)不同層次下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化。通過對復(fù)雜網(wǎng)絡(luò)實例數(shù)據(jù)進(jìn)行實驗與對比分析，驗證了本文可視化方法的有效性與適用性。

1 經(jīng)典力導(dǎo)引算法

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

KK算法在彈簧模型的基礎(chǔ)上引入了胡克定律，建立了能量模型，將節(jié)點位置的求解轉(zhuǎn)換為系統(tǒng)能量最小值的求解。在胡克定律中，單個彈簧的能量為

E=kx2/2

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

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

DH算法受到其它優(yōu)化方法的啟發(fā)而采用了模擬退火思想，即將網(wǎng)絡(luò)布局的優(yōu)化過程模擬為某些物質(zhì)系統(tǒng)的冷卻過程，當(dāng)系統(tǒng)溫度衰減至閾值時，系統(tǒng)總能量達(dá)到最小值，所有節(jié)點不再移動。DH算法的能量模型公式為

f(G)=∑λifi(G)

上式包含了5方面要素，分別是點與點的距離、點與邊的距離、點與邊框的距離、邊的長度、邊的交叉程度，λi為每部分權(quán)重，并可以根據(jù)所要遵守的美學(xué)標(biāo)準(zhǔn)來設(shè)置。DH算法的優(yōu)點在于布局結(jié)果能夠達(dá)到全局最優(yōu)值，其缺點是所需時間較長。

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

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

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

2 基于力導(dǎo)引算法的復(fù)雜網(wǎng)絡(luò)可視化

2.1 問題分析

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

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

但是，多層特征只是復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征之一，其另外一個重要的結(jié)構(gòu)特征是社團(tuán)特征。而上述可視化方法的研究幾乎都僅聚焦于體現(xiàn)復(fù)雜網(wǎng)絡(luò)的層次結(jié)構(gòu)特征，忽略了其社團(tuán)結(jié)構(gòu)特征的展示。對于兼具多層化特征與社團(tuán)化特征的復(fù)雜網(wǎng)絡(luò)來說，父節(jié)點與父節(jié)點、父節(jié)點與子節(jié)點、子節(jié)點與子節(jié)點之間的連接關(guān)系都需要被呈現(xiàn)出來，只展示網(wǎng)絡(luò)的層次結(jié)構(gòu)而忽略其社團(tuán)特征并不能完全展現(xiàn)其結(jié)構(gòu)特性。另外，將力導(dǎo)引算法應(yīng)用于復(fù)雜層次數(shù)據(jù)的研究目前還較少，因此接下來將基于力導(dǎo)引算法和聚類算法對復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化進(jìn)行研究。

2.2 總體思路

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

2.3 基于多力導(dǎo)引算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)布局

2.3.1 算法描述

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

FR算法布局速度快、易于實現(xiàn)，且布局結(jié)果能在一定程度上體現(xiàn)出聚類效果，因此本文選擇在FR算法的基礎(chǔ)上進(jìn)行改進(jìn)，其相關(guān)定義如下

其中，k表示節(jié)點之間的理想距離，C為常數(shù)，S為網(wǎng)絡(luò)布局結(jié)果所處邊框的面積，N1為節(jié)點總個數(shù)，當(dāng)系統(tǒng)趨近于穩(wěn)定狀態(tài)時，節(jié)點之間的距離將趨近于理想距離k。d表示兩個不同節(jié)點之間的笛卡爾距離，fa與fr分別表示兩個相互連接的節(jié)點之間的引力與兩個節(jié)點之間存在的斥力。

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

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

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

(1)建立節(jié)點四叉樹

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

圖1 節(jié)點四叉樹

(2)計算質(zhì)心

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

(3)計算節(jié)點斥力

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

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

frij=-k2MvjA1/d

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

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

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

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

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

最終，節(jié)點vi所受到的合力為

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

2.3.2 算法步驟

VFDA算法具體步驟如下：

(1)讀取多層網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)，輸入網(wǎng)絡(luò)G(V,E)， 初始化所有節(jié)點位置 {Pv1,Pv2,Pv3,…} 和系統(tǒng)溫度T。

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

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

(4)根據(jù)當(dāng)前迭代次數(shù)計算系統(tǒng)溫度T，若溫度達(dá)到閾值，則執(zhí)行下一步，若溫度高于閾值，則從第二步繼續(xù)執(zhí)行。

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

根據(jù)模擬退火算法可知，系統(tǒng)在初始狀態(tài)具有較高溫度，通過參數(shù)T控制迭代過程中節(jié)點的運動速度，溫度越高，節(jié)點運動越劇烈，位置的改變量就越大。隨著迭代次數(shù)的增加，系統(tǒng)溫度逐漸降低，節(jié)點位置的改變量逐漸減小。當(dāng)參數(shù)T衰減至閾值時，系統(tǒng)達(dá)到穩(wěn)定狀態(tài)，所有節(jié)點處于靜止?fàn)顟B(tài)。

2.4 基于層次聚類算法的網(wǎng)絡(luò)多細(xì)節(jié)層級模型

當(dāng)在有限的屏幕范圍內(nèi)對大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行可視化處理時，大量的節(jié)點和邊會發(fā)生擁擠、交叉或重疊等現(xiàn)象，從而影響人們辨別和理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)。聚類算法在數(shù)據(jù)挖掘領(lǐng)域應(yīng)用廣泛，能夠按照某些標(biāo)準(zhǔn)對數(shù)據(jù)進(jìn)行分組，生成簇結(jié)構(gòu)，同一簇內(nèi)的個體存在某特性下相似的現(xiàn)象。將適用于數(shù)據(jù)分析的聚類算法與數(shù)據(jù)可視化的力導(dǎo)引算法相結(jié)合，能夠有效幫助人們理解、分析其中的信息[15]。

層次聚類算法通過計算不同個體的相似度來逐步生成簇，相似度可以選擇不同的度量標(biāo)準(zhǔn)，最終建立具有嵌套結(jié)構(gòu)的層次樹，適用于層次數(shù)據(jù)的聚類分析。因此，本文基于層次聚類算法，定義了一個顯示層級結(jié)構(gòu)的參數(shù)L，并將同一根節(jié)點下子節(jié)點之間的拓?fù)渚嚯x作為相似度的度量標(biāo)準(zhǔn)，采用由下至上的方式逐步建立復(fù)雜網(wǎng)絡(luò)多細(xì)節(jié)層級模型。參數(shù)L決定在相應(yīng)層級上顯示聚類結(jié)果，參數(shù)L高時顯示網(wǎng)絡(luò)骨干結(jié)構(gòu)，參數(shù)L低時則額外顯示骨干結(jié)構(gòu)下的低層級網(wǎng)絡(luò)。

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

圖2 網(wǎng)絡(luò)層次結(jié)構(gòu)樹狀示意圖

3 實驗結(jié)果展示與分析

3.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)集

3.2 可視化結(jié)果分析

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

圖3 Data-1FR算法布局結(jié)果

圖4 Data-1VFDA算法布局結(jié)果

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

圖5 Data-2FR算法布局結(jié)果

圖6 Data-2VFDA算法布局結(jié)果

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

表2 FR算法與VFDA算法父節(jié)點附近節(jié)點數(shù)目對比

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

圖7 Data-2層次聚類布局結(jié)果

3.3 交互方法

考慮到顯示屏面積、數(shù)據(jù)規(guī)模等因素的影響，上述可視化方法不能盡善盡美地展現(xiàn)多層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，需要通過某些交互手段輔助人們獲取、分析感興趣的信息?；贘avaScript語言的D3相較于其它可視化工具，能夠完美結(jié)合數(shù)據(jù)驅(qū)動的操作方式與可視化組件，并具有更加靈活的可視化交互方式[16]。

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

圖8 交互操作

4 結(jié)束語

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