吳 渝，林 茂，雷大江

(重慶郵電大學(xué)網(wǎng)絡(luò)智能研究所，重慶400065)

0 引言

復(fù)雜網(wǎng)絡(luò)可視化是當(dāng)前的熱門(mén)研究領(lǐng)域，通過(guò)可視化能夠挖掘傳統(tǒng)方法無(wú)法直觀得到的內(nèi)部結(jié)構(gòu)信息，增加對(duì)復(fù)雜網(wǎng)絡(luò)的理解程度。當(dāng)前，主要的可視化方法是Edges［1］提出的力導(dǎo)引布局算法，其基本思想是將整個(gè)網(wǎng)絡(luò)看成一個(gè)彈簧受力系統(tǒng)，系統(tǒng)中受到的彈力總和為系統(tǒng)的總能量。系統(tǒng)中每個(gè)頂點(diǎn)在彈力作用下不斷調(diào)整位置減小受到的彈力，直到系統(tǒng)總能量減少到最小值時(shí)停止。

在傳統(tǒng)的2D平面上，Kamada［2］提出的KK算法使彈力模型遵循“胡克定律”，其可視化結(jié)果美觀度得到了很大提高;Fruchterman［3］在彈力模型中增加了布局空間大小的限制因素，使可視化布局適應(yīng)于布局平面大小的變化;黃競(jìng)偉等［4］通過(guò)采用遺傳算法減少了迭代次數(shù)，降低了可視化布局的時(shí)間復(fù)雜度;黃茂林［5］通過(guò)多層次聚類(lèi)的方法使可視化適用大型網(wǎng)絡(luò)。還有很多其他算法［6-7］改進(jìn)了布局方式使力導(dǎo)引方法適用于不同網(wǎng)絡(luò)類(lèi)型，并使可視化結(jié)果更加方便用戶(hù)獲取網(wǎng)絡(luò)中的隱藏信息。

但是，Ware［8］指出2D平面相對(duì)于3D空間其布局空間較小、深度值不夠從而體現(xiàn)不出立體感，并使可視化結(jié)果缺乏交互性。因此，一些3D可視化算法被提出來(lái)。Bruβ［9］通過(guò)分析3D空間特征，改進(jìn)了能量迭代的方法，大大降低了時(shí)間復(fù)雜度;Harel［10］在3D空間中采用多尺度布局，即每次只顯示源網(wǎng)絡(luò)的部分骨架網(wǎng)絡(luò)，提高了網(wǎng)絡(luò)的布局時(shí)間效率;Gajer［11-12］通過(guò)預(yù)布局的方式能夠快速地在3D空間中得到最終布局;Ahmed［13］分析了復(fù)雜網(wǎng)絡(luò)的冪律特性，并通過(guò)節(jié)點(diǎn)度大小對(duì)網(wǎng)絡(luò)進(jìn)行聚類(lèi)，然后采用較成熟的2D可視化方法把每一個(gè)聚類(lèi)分層次的布局在3D空間中，其可視化布局能夠直觀分辨出重要節(jié)點(diǎn)，且具有較好美觀性;吳鵬［14］在3D中對(duì)社會(huì)網(wǎng)絡(luò)采用多層次布局方式，其可視化結(jié)果能夠顯示社會(huì)網(wǎng)絡(luò)中的子群分布。

綜上所述，目前2D可視化已經(jīng)較為成熟。而由于3D可視化具有更好的交互性，提供了更加生動(dòng)的可視化展示，3D可視化算法逐漸成為可視化研究熱點(diǎn)。然而，目前的3D可視化算法都是采用優(yōu)化迭代算法、預(yù)布局、多尺度布局、多層次布局等方式優(yōu)化布局方式，減小時(shí)間復(fù)雜度，可視化過(guò)程中缺乏復(fù)雜網(wǎng)絡(luò)特征分析，因此不能可視化復(fù)雜網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)，比如社團(tuán)結(jié)構(gòu)。同時(shí)，在國(guó)內(nèi)可視化研究也相對(duì)較少［15］，特別是3D可視化。

本文引入復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征分析方法，基于Kamada提出的KK算法［2］，提出了兩級(jí)KK 3D力導(dǎo)引算法(two-tier KK，TTKK)。算法改進(jìn)了2D KK算法，使算法適應(yīng)于3D空間布局，并首先對(duì)源網(wǎng)絡(luò)進(jìn)行聚類(lèi)分析，建立抽象網(wǎng)絡(luò)。然后，在3D空間中分2級(jí)依次對(duì)源網(wǎng)絡(luò)的抽象網(wǎng)絡(luò)和子網(wǎng)絡(luò)進(jìn)行KK布局。其最終可視化布局結(jié)果能夠較完整地展示復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征。

1 KK力導(dǎo)引算法基本原理

Edges提出的力導(dǎo)引算法主要分為2部分:建立能量計(jì)算模型，即彈力模型;以及迭代減小系統(tǒng)總能量。在能量計(jì)算模型上，KK算法遵循“胡克定律”

同時(shí)，算法首次提出了“理想距離”的概念。2個(gè)頂點(diǎn)間的理想距離與2個(gè)頂點(diǎn)的最短距離成正比

(1)，(2)式中:pi是頂點(diǎn)vi對(duì)應(yīng)的位置向量;n為頂點(diǎn)數(shù);kij是頂點(diǎn)vi和vj之間的彈力系數(shù);lij是頂點(diǎn)vi和vj之間的理想距離，它由vi和vj的最短距離dij以及布局寬度L0共同決定。

在減小系統(tǒng)能量的方法上，如(3)式所示，KK算法通過(guò)求解每一個(gè)頂點(diǎn)對(duì)E的偏微分方程來(lái)不斷減小系統(tǒng)總能量。在計(jì)算過(guò)程中，KK算法為方便計(jì)算，假定頂點(diǎn)pm(xm，ym)是當(dāng)前Δm值最大的頂點(diǎn)，且在移動(dòng)pm時(shí)其他頂點(diǎn)都相對(duì)固定。則pm的位移向量(δx，δy)可以通過(guò)(4)，(5)式求解，使pm移動(dòng)到(xm+δx，ym+δy)處，更新pm的位置。

(4)－(5)式中，(x(mt)，y(mt))是點(diǎn)pm在第t次迭代后的位置。然后，反復(fù)迭代減小系統(tǒng)中能量，直到每一個(gè)頂點(diǎn)的Δ值都足夠小并滿(mǎn)足要求時(shí)停止，得到最終布局。

2 兩級(jí)KK力導(dǎo)引布局算法

2.1 問(wèn)題提出和算法基本思路

KK 算法能量模型遵循“胡克定律”，最終的布局結(jié)果具有良好的對(duì)稱(chēng)性［16］，在2D平面可視化中得到廣泛應(yīng)用。但是，KK算法在能量減小過(guò)程中迭代次數(shù)較多，時(shí)間效率低。本文在2D平面KK算法的基礎(chǔ)上，把KK算法應(yīng)用到3D空間中，并通過(guò)實(shí)驗(yàn)分析改進(jìn)了KK算法的時(shí)間效率。

另一方面，目前，3D算法主要集中在如何改進(jìn)算法的時(shí)間效率上，且這些可視化算法都是直接對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)間的相互連接關(guān)系進(jìn)行分析，從而進(jìn)一步布局得到可視化結(jié)果。算法布局較缺乏對(duì)復(fù)雜網(wǎng)絡(luò)的內(nèi)部特征的分析，布局結(jié)果破壞了復(fù)雜網(wǎng)絡(luò)的社團(tuán)、節(jié)點(diǎn)重要度等結(jié)構(gòu)特征。

如圖1所示，本文借用復(fù)雜網(wǎng)絡(luò)中社區(qū)劃分的思想，采用能夠較完整地保持網(wǎng)絡(luò)原始物理結(jié)構(gòu)的edge betweenness［17］算法對(duì)網(wǎng)絡(luò)進(jìn)行聚類(lèi)分析，使每個(gè)聚類(lèi)的頂點(diǎn)在100以?xún)?nèi)［11］，并通過(guò)分析聚類(lèi)之間的鏈接關(guān)系構(gòu)建抽象網(wǎng)絡(luò)。得到抽象網(wǎng)絡(luò)后，TTKK算法分2級(jí)分別對(duì)網(wǎng)絡(luò)布局:第1級(jí)抽象網(wǎng)絡(luò)布局和第2級(jí)聚類(lèi)子網(wǎng)布局，TTKK算法流程如圖1所示。在抽象網(wǎng)絡(luò)布局上，算法提取子網(wǎng)絡(luò)的特征向量重新定義“理想距離”，使KK算法適應(yīng)抽象網(wǎng)絡(luò)特性;使用3DKK算法對(duì)抽象網(wǎng)絡(luò)布局得到每個(gè)子網(wǎng)絡(luò)的布局中心點(diǎn)，每個(gè)子網(wǎng)絡(luò)在布局中心點(diǎn)處隨機(jī)初始化頂點(diǎn)位置，然后使用3DKK算法進(jìn)行布局。

圖1 TTKK算法流程圖Fig.1 Algorithm flow chart of TTKK

2.2 3D空間中的KK力導(dǎo)引算法

在3D空間中，KK算法的能量同樣可以使用(1)式計(jì)算得到。但是在迭代減小系統(tǒng)能量時(shí)，網(wǎng)絡(luò)中每個(gè)頂點(diǎn)的能量Δm的計(jì)算方法需要加入對(duì)深度坐標(biāo)軸z的影響因子

同理，求解頂點(diǎn)pm每次迭代后的位移向量(δx，δy，δz)的方程也有所改變，如(7)－(10)式所示。

另一方面，KK算法在減小能量過(guò)程中迭代次數(shù)太多，使網(wǎng)絡(luò)布局難以在短時(shí)間內(nèi)完成。實(shí)驗(yàn)發(fā)現(xiàn)KK算法在迭代過(guò)程中能量的減小將逐漸減緩。假設(shè)布局網(wǎng)絡(luò)的定點(diǎn)數(shù)為n，則在前n次迭代過(guò)程中能量減小最快，布局中頂點(diǎn)位置變化最強(qiáng)烈;到第4n次迭代時(shí)雖然能量也在減小，但是布局中的頂點(diǎn)變化較小，這時(shí)的布局已近基本穩(wěn)定，接近最終布局;在4n次迭代之后，雖然布局的美觀性逐漸增加，但是頂點(diǎn)位置的改變微弱。

表1展示了使用仿真數(shù)據(jù)K15完全圖和日本空手道Zachary［18］俱樂(lè)部的公開(kāi)數(shù)據(jù)進(jìn)行KK算法布局試驗(yàn)的結(jié)果。其中t為算法迭代的時(shí)間，n是網(wǎng)絡(luò)中的頂點(diǎn)數(shù)，t=n代表迭代n次后所花費(fèi)的時(shí)間，以此類(lèi)推。從表1中可以看出不論是真實(shí)數(shù)據(jù)Zachary，還是仿真數(shù)據(jù)K15，由于初始布局頂點(diǎn)是隨機(jī)分布，布局十分混亂;當(dāng)?shù)鷑次后最終布局的骨架基本顯現(xiàn)出來(lái)，可以很明的看出這個(gè)過(guò)程布局變化激烈。從第3n次布局開(kāi)始，每次迭代后的雖然布局對(duì)稱(chēng)性、美觀度逐漸增加，但是網(wǎng)絡(luò)中各個(gè)點(diǎn)的位置變化卻十分微弱。因此，本文在網(wǎng)絡(luò)布局中限制了KK算法能量減小過(guò)程的最大迭代次數(shù)。根據(jù)實(shí)驗(yàn)，本文在速度和美觀度上進(jìn)行折中選擇，取4n為最大迭代次數(shù)。

設(shè)源網(wǎng)絡(luò)為G=(V，E)，其中V是待布局網(wǎng)絡(luò)的頂點(diǎn)集，E是待布局網(wǎng)絡(luò)的邊集。則3D空間中改進(jìn)后KK布局算法可以描述如下。

表1 3D KK算法迭代過(guò)程布局變化情況Tab.1 Iteration changing situation of 3D KK algorithm

2.3 抽象網(wǎng)絡(luò)特征向量構(gòu)造方法

在TTKK算法中使用Edge Betweenness算法對(duì)網(wǎng)絡(luò)G進(jìn)行聚類(lèi)得到子網(wǎng)絡(luò)G1，G2，…，Gn，并建立抽象網(wǎng)絡(luò)。抽象網(wǎng)絡(luò)中的一個(gè)頂點(diǎn)代表一個(gè)子網(wǎng)絡(luò)，同時(shí)如果2個(gè)子網(wǎng)絡(luò)中的任意2個(gè)頂點(diǎn)在原網(wǎng)絡(luò)存在連接則在網(wǎng)絡(luò)G'中2個(gè)子網(wǎng)絡(luò)對(duì)應(yīng)的頂點(diǎn)間存在一條邊。建立網(wǎng)絡(luò)后進(jìn)一步使用KK算法對(duì)抽象網(wǎng)絡(luò)布局。

但是，由于抽象網(wǎng)絡(luò)中的每1個(gè)頂點(diǎn)代表1個(gè)子網(wǎng)絡(luò)，而網(wǎng)絡(luò)本身具有的特性與原始的頂點(diǎn)具有不同的屬性，不適合以最短距離來(lái)定義聚類(lèi)間的理想距離。因此，本文通過(guò)子網(wǎng)絡(luò)中每個(gè)頂點(diǎn)在源網(wǎng)絡(luò)G中的聚類(lèi)系數(shù)［19］值的和、Page Rank［20］值的和構(gòu)建子網(wǎng)絡(luò)的特征向量T，如(11)式所示，然后計(jì)算2個(gè)子網(wǎng)絡(luò)之間的余弦相似度來(lái)得到2個(gè)聚類(lèi)間的理想距離

(11)式中，C(v)指聚集系數(shù)值，它表明網(wǎng)絡(luò)中節(jié)點(diǎn)的聚集性，也就是說(shuō)同1個(gè)節(jié)點(diǎn)的2個(gè)相鄰節(jié)點(diǎn)仍然是相鄰節(jié)點(diǎn)的概率有多大，反映了網(wǎng)絡(luò)的局部特性。計(jì)算公式為

(12)式中:kv代表與網(wǎng)絡(luò)中點(diǎn)v連接的節(jié)點(diǎn)數(shù)量，即鄰居數(shù);Ev表示這kv個(gè)鄰居之間的實(shí)際存在的邊數(shù)。

PR(v)指Page Rank值，即節(jié)點(diǎn)的影響力值，它反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。

(13)式中:PR(u)是節(jié)點(diǎn)u的PageRank值;PR(v)是節(jié)點(diǎn)v的PageRank值;Ru是鏈接到節(jié)點(diǎn)u的節(jié)點(diǎn)集合;N(v)為節(jié)點(diǎn)v向外的所有鏈接數(shù);d是與節(jié)點(diǎn)u屬性相關(guān)的隨機(jī)概率，一般情況下d=0.85。

2.4 抽象網(wǎng)絡(luò)布局及子網(wǎng)絡(luò)布局

通過(guò)計(jì)算每個(gè)2個(gè)子網(wǎng)絡(luò)特征向量的余弦相似度得到抽象網(wǎng)絡(luò)G'中相互2個(gè)頂點(diǎn)的理想距離l'ij，計(jì)算公式為

(14)式中，L0是可視化布局的寬度，本文取L0的取值為3D布局空間的直徑。新的“理想距離”定義l'ij加入了復(fù)雜網(wǎng)絡(luò)特征因素，KK算法使用l'ij進(jìn)行布局即可得到每一個(gè)子網(wǎng)絡(luò)的布局中心點(diǎn)，其布局結(jié)果能夠反映出各個(gè)子網(wǎng)絡(luò)在源網(wǎng)絡(luò)中的相互關(guān)系。然后，在子網(wǎng)絡(luò)布局中心點(diǎn)處對(duì)子網(wǎng)絡(luò)進(jìn)行KK布局，得到最終的可視化布局。

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

為對(duì)比TTKK算法可視化布局效果，本文分別選取3DKK算法和Ahmed提出的算法進(jìn)行對(duì)比。其中，3DKK算法遵循胡克定律，是基于2DKK［2］算法在3D空間中的應(yīng)用，TTKK算法的每一級(jí)布局都是基于3DKK算法布局算法的;Ahmed［13］算法基于連接度的聚類(lèi)把網(wǎng)絡(luò)分為3層，并把每一層節(jié)點(diǎn)分層次地布局在3D空間中，每一層上的節(jié)點(diǎn)都采用較成熟的2D布局算法進(jìn)行布局，整個(gè)算法思想與TTKK算法類(lèi)似。因此，文本分別將2種算法作為對(duì)比對(duì)象，用真實(shí)數(shù)據(jù)進(jìn)行可視化布局，以評(píng)估本文算法。

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

本文使用3組公開(kāi)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中Dolphins數(shù)據(jù)是一個(gè)由Lusseau［21］通過(guò)7年的研究，并記錄下海豚社交網(wǎng)絡(luò)數(shù)據(jù)集，Ca-AstroPh(Astro Physics collaboration network)通過(guò)Arxiv在線出版并投稿到Astro的Physics類(lèi)的科研合作網(wǎng)絡(luò)，Smyth是關(guān)于Padhraic Smyth［22］的出版物網(wǎng)絡(luò)，表2展示了各組實(shí)驗(yàn)數(shù)據(jù)的詳細(xì)信息。

表2 實(shí)驗(yàn)數(shù)據(jù)集Tab.2 Dataset in experiments

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

采用3.1節(jié)中的數(shù)據(jù)集，本文分別對(duì)KK算法、TTKK算法和Ahmed提出算法進(jìn)行了實(shí)驗(yàn)。圖2是Dolphins數(shù)據(jù)集可視化對(duì)比情況，其中圖2a是TTKK算法的初始布局，圖2b是TTKK算法可視化結(jié)果，圖2c是Ahmed算法可視化結(jié)果。圖3是TTKK算法采用Ca-AstroPh數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)的結(jié)果，圖3a和圖3b是分別從不同角度下觀看的結(jié)果。圖4是Smyth數(shù)據(jù)集可視化對(duì)比情況，圖4a是TTKK算法可視化結(jié)果，圖4b是TTKK算法可視化布局旋轉(zhuǎn)后的視圖，圖4c是Ahmed算法可視化布局結(jié)果。

從圖2a和圖2b中可見(jiàn)TTKK算法從初始的隨機(jī)布局得到對(duì)稱(chēng)性較好的可視化布局。同時(shí)，可以看到在可視化結(jié)果中清晰地顯現(xiàn)出3個(gè)聚類(lèi)類(lèi)結(jié)構(gòu)，表明Dolphins數(shù)據(jù)集中具有3個(gè)關(guān)系網(wǎng)絡(luò)。在圖2c中由于Ahmed算法通過(guò)節(jié)點(diǎn)度大小來(lái)直接進(jìn)行聚類(lèi)劃分，而Dolphins數(shù)據(jù)集中不存在度大于15的節(jié)點(diǎn)，從而造成可視化結(jié)果只有2層。而且圖2c相對(duì)于圖2b，其可視化結(jié)果并不能很好地反應(yīng)出網(wǎng)絡(luò)的真實(shí)形態(tài)，可視化結(jié)果本身的美觀效果也不夠理想。同樣的，KK算法在Ca-AstroPh(圖3)和Smyth(圖4a和圖4c)數(shù)據(jù)集下的可視化結(jié)果中也能夠清楚完整地展示網(wǎng)絡(luò)的結(jié)構(gòu)特征，而且能夠凸顯出網(wǎng)絡(luò)中的各個(gè)重要節(jié)點(diǎn)。

圖2 Dolphins數(shù)據(jù)集可視化結(jié)果對(duì)比Fig.2 Visualization results comparison of dolphins

圖3 CA-AstroPh數(shù)據(jù)集可視化結(jié)果Fig.3 Visualization results of CA-AstroPh

圖4 Smyth數(shù)據(jù)集結(jié)果對(duì)比Fig.4 Visualization results comparison of Smyth

另一方面，在圖4a的可視化結(jié)果中左邊有一個(gè)子網(wǎng)絡(luò)的布局產(chǎn)生了較嚴(yán)重的點(diǎn)遮擋情況，但是，TTKK算法可視化結(jié)果可以通過(guò)在3D空間中進(jìn)行旋轉(zhuǎn)得到圖4b，從圖4b的角度就能夠清晰地看到這部分子網(wǎng)絡(luò)的結(jié)構(gòu)。而在Ahmed的可視化布局結(jié)果中雖然美觀度在這個(gè)數(shù)據(jù)集中有很大的提高，但是結(jié)構(gòu)上只得到頂層節(jié)點(diǎn)具有較高重要度，而且最底層的節(jié)點(diǎn)之間的關(guān)系混亂。不論在哪一個(gè)角度觀看都不能得到較滿(mǎn)意的結(jié)構(gòu)信息。

綜上，TTKK算法在3D空間下能夠十分完整地展現(xiàn)復(fù)雜網(wǎng)絡(luò)的聚類(lèi)結(jié)構(gòu)特征。

3.3 算法效率分析及實(shí)驗(yàn)對(duì)比

TTKK的運(yùn)行時(shí)間主要受2個(gè)方面影響:聚類(lèi)算法運(yùn)行時(shí)間以及能量迭代運(yùn)行時(shí)間。其中Edge Betweenness算法的時(shí)間復(fù)雜度為O(m2n)，m為邊數(shù)，n為頂點(diǎn)數(shù)。同時(shí)，假設(shè)KK算法的時(shí)間復(fù)雜度為O(KK)，則TTKK算法可以在O(m2n)+k*O(KK)的時(shí)間復(fù)雜度中完成布局，其中k為一個(gè)常數(shù)因子。而且由于限制了最大迭代次數(shù)，KK算法的迭代時(shí)間大大減小。同理，若Ahmed每一層的布局都采用KK算法，則Ahmed的算法時(shí)間復(fù)雜度為O(n)+k*O(KK)。但是，由于復(fù)雜網(wǎng)絡(luò)存在冪律定律，即節(jié)點(diǎn)度數(shù)較大的頂點(diǎn)較少，Ahmed算法的聚類(lèi)方式大部分都會(huì)分布在最底層中，如圖3c所示。因此，Ahmed的時(shí)間復(fù)雜度中的常數(shù)因子k較大，而且隨著網(wǎng)絡(luò)的增大Ahmed的增長(zhǎng)越快。

本文采用Java語(yǔ)言分別實(shí)現(xiàn)了KK，Ahmed，TTKK 3個(gè)算法，并在Windows7(CPU為i3 2.1 GHz)平臺(tái)上分別對(duì)KK算法、Ahmed算法、TTKK算法使用表2的數(shù)據(jù)集進(jìn)行了3次實(shí)驗(yàn)采集算法時(shí)間消耗，對(duì)3次實(shí)驗(yàn)的時(shí)間消耗的平均值作為其最終的時(shí)間消耗，如表3所示?？梢钥闯鯝hmed在網(wǎng)絡(luò)較小時(shí)時(shí)間效率較高，而隨著網(wǎng)絡(luò)的增大時(shí)間消耗劇增;TTKK算法雖然在小型網(wǎng)絡(luò)中復(fù)雜度較高，但卻不會(huì)隨著網(wǎng)絡(luò)的增大而劇烈變化。最終實(shí)驗(yàn)結(jié)果與理論分析一致。

表3 算法時(shí)間對(duì)比Tab.3 Comparison of algorithm efficiency

4 結(jié)論

本文在當(dāng)前廣泛使用的2D平面上的KK力導(dǎo)引可視化算法基礎(chǔ)上，結(jié)合復(fù)雜網(wǎng)絡(luò)特征，提出了適用于復(fù)雜網(wǎng)絡(luò)的TTKK 3D可視化算法。算法首先通過(guò)聚類(lèi)得到源網(wǎng)絡(luò)的多個(gè)子網(wǎng)絡(luò)，并構(gòu)建抽象網(wǎng)絡(luò)。然后，分2級(jí)分別使用3DKK算法對(duì)抽象網(wǎng)絡(luò)和子網(wǎng)絡(luò)進(jìn)行布局。TTKK算法解決了可視化結(jié)果中不能反映復(fù)雜網(wǎng)絡(luò)特征的問(wèn)題，能夠清晰的展示復(fù)雜網(wǎng)絡(luò)的社團(tuán)、節(jié)點(diǎn)重要度等結(jié)構(gòu)特征。同時(shí)，通過(guò)改進(jìn)KK算法的迭代方式可減少算法時(shí)間消耗。

但是，目前算法最初的可視化布局不能自動(dòng)調(diào)整視角使布局結(jié)果具有最佳的效果，而需要手動(dòng)調(diào)整視角。在下一步工作中，主要對(duì)算法布局結(jié)果的評(píng)定指標(biāo)進(jìn)行研究，比如說(shuō)對(duì)稱(chēng)性、信息可見(jiàn)度、結(jié)構(gòu)可視化程度等的定量評(píng)定指標(biāo)的研究，使TTKK算法通過(guò)指標(biāo)值自動(dòng)調(diào)整可視化布局結(jié)果的視角。

［1］EADES P.A heuristic for graph drawing.Congressus Nutnerantiunt，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］黃競(jìng)偉，康立山，陳毓屏.一個(gè)新的無(wú)向圖畫(huà)圖算法［J］.軟件學(xué)報(bào)，2000，11(1):138-142.

HHUANG J W，KANG L S，CHEN Y P.A new graph drawing algorithm for undirected graphs［J］.Journal of Software，2000，11(1):138-142.

［5］黃茂林，NGUYEN Q V.用多層次聚類(lèi)法完成的大規(guī)模關(guān)系圖的可視化［J］.軟件學(xué)報(bào)，2008，19(8):1933.

HHUANG M L，NGUYEN Q V.Large graph visualization by hierarchical clustering［J］.Journal of Software，2008，19(8):1933.

［6］CHAN D S M，CHUA K S，LECKIE C，et al.Visualization of power-law network topologies［C］//，2003 IEEE 11th International Conference on Networks.Sydney:IEEE Press，2003:69-74.

［7］HOLTEN D，ISENBERG P，VAN WIJK J J，et al.An extended evaluation of the readability of tapered，animated，and textured directed-edge representations in nodelink graphs［C］//2011 IEEE Pacific Visualization Sym-posium.Hong Kong:IEEE Press，2011:195-202.

［8］WARE C.Designing with a 2 1/2d attitude［J］.Information Design Journal，2001，10(3):171–182.

［9］BRUB I，F(xiàn)RICK A.Fast interactive 3-D graph visualization［C］//Lecture Notes in Computer Science，Graph Drawing.Berlin Heidelberg:Springer，1996，99-110.

［10］HAREL D，KOREN Y.A fast multi-scale method for drawing large graphs［C］//Lecture Notes in Computer Science，Graph Drawing.Berlin Heidelberg:Springer 2001，183-196.

［11］GAJER P，GOODRICH M T，KOBOUROV S G.A multi-dimensional approach to force-directed layouts of large graphs［C］//Lecture Notes in-Computer Science，Graph Drawing.Berlin Heidelberg:Springer 2001，211-221.

［12］GAJER P，KOBOUROV S G.Grip:graph drawing with intelligent placement［C］//Lecture Notes in Computer Science，Graph Drawing.Berlin Heidelberg:Springer 2001，222-228.

［13］AHMED A，DYWER T，HONG S H，et al.Visualization and analysis of large and complex scale-free networks［C］//Proceedings of the 7th Joint Eurographics/IEEE VGTC conference on Visualization.Switzerland:Eurographics Association Press，2005:239-246.

［14］吳鵬，李思昆.適于社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)分析與可視化的布局算法［J］.軟件學(xué)報(bào)，2011，22(10):2467-2475.

WU P，LI S K.Layout algorithm suitable for structural analysis and visualization of social network［J］.Journal of Software，2011，22(10):2467-2475.

［15］王柏，吳巍，徐超群，等.復(fù)雜網(wǎng)絡(luò)可視化研究綜述［J］.計(jì)算機(jī)科學(xué)，2007，34(4):17-23.

WANG B，WU W，XU C Q，et al.A survey on visualization of complex network［J］.Computer Science，2007，34(4):17-23.

［16］BATTISTA G D，EADES P，TAMASSIA R，et al.Algorithms for drawing graphs:an annotated bibliography［J］.Computational Geometry，1994，4(5):235-282.

［17］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69(2):026113.

［18］ZACHARY W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33(4):452-473.

［19］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京:清華大學(xué)出版社，2006.

WANG X F，LI X，CHEN G R.Complex network theories and applications［M］.Beijing，China:Tsinghua U-niversity Press，2006.

［20］BRIN S，PAGE L.The anatomy of a large-scale hypertextual web search engine［J］.Computer Networks and ISDN Systems，1998，30(1):107-117.

［21］LUSSEAU D.The emergent properties of a dolphin social network［J］.Proceedings of the Royal Society of London，Series B:Biological Sciences，2003，270(2):186-188.

［22］WU A Y，GARLAND M，HAN J.Mining scale-free networks using geodesic clustering［C］//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Texas:ACM，2004:719-724.