一種3D 空間中的兩級力導(dǎo)引可視化算法

吳 渝，林 茂，雷大江

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

0 引言

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

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

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

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

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

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

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

同時，算法首次提出了“理想距離”的概念。2個頂點間的理想距離與2個頂點的最短距離成正比

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

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

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

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

2.1 問題提出和算法基本思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗及結(jié)果分析

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

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

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

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

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

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

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

圖2 Dolphins數(shù)據(jù)集可視化結(jié)果對比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é)果對比Fig.4 Visualization results comparison of Smyth

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

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

3.3 算法效率分析及實驗對比

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

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

表3 算法時間對比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可視化算法。算法首先通過聚類得到源網(wǎng)絡(luò)的多個子網(wǎng)絡(luò)，并構(gòu)建抽象網(wǎng)絡(luò)。然后，分2級分別使用3DKK算法對抽象網(wǎng)絡(luò)和子網(wǎng)絡(luò)進行布局。TTKK算法解決了可視化結(jié)果中不能反映復(fù)雜網(wǎng)絡(luò)特征的問題，能夠清晰的展示復(fù)雜網(wǎng)絡(luò)的社團、節(jié)點重要度等結(jié)構(gòu)特征。同時，通過改進KK算法的迭代方式可減少算法時間消耗。

但是，目前算法最初的可視化布局不能自動調(diào)整視角使布局結(jié)果具有最佳的效果，而需要手動調(diào)整視角。在下一步工作中，主要對算法布局結(jié)果的評定指標(biāo)進行研究，比如說對稱性、信息可見度、結(jié)構(gòu)可視化程度等的定量評定指標(biāo)的研究，使TTKK算法通過指標(biāo)值自動調(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］.軟件學(xué)報，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.用多層次聚類法完成的大規(guī)模關(guān)系圖的可視化［J］.軟件學(xué)報，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］吳鵬，李思昆.適于社會網(wǎng)絡(luò)結(jié)構(gòu)分析與可視化的布局算法［J］.軟件學(xué)報，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］.計算機科學(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.