安沈昊，于榮歡+，薛 瓊

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

0 引 言

網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)能夠以圖形圖像的方式清晰展現(xiàn)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的連接情況，幫助人們有效認(rèn)識(shí)和理解網(wǎng)絡(luò)內(nèi)部特征和結(jié)構(gòu)[1]。力導(dǎo)引算法作為目前最常用的網(wǎng)絡(luò)拓?fù)淇梢暬夹g(shù)，實(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é)層級(jí)下展示復(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)，通過改變同一層級(jí)結(jié)構(gòu)下節(jié)點(diǎn)之間的引力來有效展示社團(tuán)結(jié)構(gòu)與層次結(jié)構(gòu)。最后描述了聚類規(guī)則，通過層次聚類算法對(duì)節(jié)點(diǎn)進(jìn)行聚類并建立網(wǎng)絡(luò)多細(xì)節(jié)層級(jí)模型，實(shí)現(xiàn)不同層次下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化。通過對(duì)復(fù)雜網(wǎng)絡(luò)實(shí)例數(shù)據(jù)進(jìn)行實(shí)驗(yàn)與對(duì)比分析，驗(yàn)證了本文可視化方法的有效性與適用性。

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

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

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

E=kx2/2

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

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

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

f(G)=∑λifi(G)

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

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

LinLog算法通過引入Barnes-Hut算法[7]來減少節(jié)點(diǎn)的位置與受力計(jì)算量，提高了算法的效率，并且提出了表示聚類分離效果的函數(shù)，能夠更好地展示網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)。其能量公式如下所示，等式右邊第一部分和第二部分分別表示相互連接的兩個(gè)節(jié)點(diǎn)之間的引力與任意兩個(gè)節(jié)點(diǎn)之間的斥力。采用Barnes-Hut算法對(duì)能量最小值得求解進(jìn)行優(yōu)化，當(dāng)ULinLog(p) 達(dá)到最小值時(shí)，代表布局結(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)注。社會(huì)與科技的發(fā)展使某些領(lǐng)域的復(fù)雜網(wǎng)絡(luò)規(guī)模愈加龐大、結(jié)構(gòu)也更加復(fù)雜，例如天地一體化網(wǎng)絡(luò)[8]，其網(wǎng)絡(luò)結(jié)構(gòu)具有明顯的分層特性，若干個(gè)一級(jí)節(jié)點(diǎn)相互連接組成骨干網(wǎng)，每個(gè)一級(jí)節(jié)點(diǎn)連接著若干二級(jí)節(jié)點(diǎn)，每個(gè)二級(jí)節(jié)點(diǎn)連接著眾多三級(jí)節(jié)點(diǎn)，之后依次向下疊加。除此之外，大部分復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)還兼具社團(tuán)特性，即父節(jié)點(diǎn)與其下眾多子節(jié)點(diǎn)組成了一個(gè)子網(wǎng)絡(luò)，或部分子節(jié)點(diǎn)組成了一個(gè)子網(wǎng)絡(luò)，子網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)聯(lián)系緊密從而構(gòu)成了一個(gè)社團(tuán)，社團(tuán)外的子節(jié)點(diǎn)單獨(dú)與父節(jié)點(diǎn)相連。而且，子網(wǎng)絡(luò)之間還存在聯(lián)系稀疏的節(jié)點(diǎn)，即相互連接的兩個(gè)節(jié)點(diǎn)存在于同一層級(jí)中的不同社團(tuán)中。

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

但是，多層特征只是復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征之一，其另外一個(gè)重要的結(jié)構(gòu)特征是社團(tuán)特征。而上述可視化方法的研究幾乎都僅聚焦于體現(xiàn)復(fù)雜網(wǎng)絡(luò)的層次結(jié)構(gòu)特征，忽略了其社團(tuán)結(jié)構(gòu)特征的展示。對(duì)于兼具多層化特征與社團(tuán)化特征的復(fù)雜網(wǎng)絡(luò)來說，父節(jié)點(diǎn)與父節(jié)點(diǎn)、父節(jié)點(diǎn)與子節(jié)點(diǎn)、子節(jié)點(diǎn)與子節(jié)點(diǎn)之間的連接關(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)引算法和聚類算法對(duì)復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化進(jìn)行研究。

2.2 總體思路

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

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

2.3.1 算法描述

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

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

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

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

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

通過Barnes-Hut算法計(jì)算節(jié)點(diǎn)斥力分為以下3個(gè)步驟：

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

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

圖1 節(jié)點(diǎn)四叉樹

(2)計(jì)算質(zhì)心

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

(3)計(jì)算節(jié)點(diǎn)斥力

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

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

frij=-k2MvjA1/d

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

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

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

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

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

最終，節(jié)點(diǎn)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é)點(diǎn)位置 {Pv1,Pv2,Pv3,…} 和系統(tǒng)溫度T。

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果展示與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

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

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

圖8 交互操作

4 結(jié)束語

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