展示網(wǎng)絡(luò)重疊社團結(jié)構(gòu)的可視化布局算法

張銘娜,肖 婧,許小可,2

(1.大連民族大學信息與通信工程學院,遼寧 大連 116600; 2.北京師范大學 a.計算傳播學研究中心,廣東 珠海 519085; b.新聞傳播學院,北京 100875)

0 引言

網(wǎng)絡(luò)可視化技術(shù)以圖形化的方式展示了網(wǎng)絡(luò)數(shù)據(jù),直觀地呈現(xiàn)出網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息。網(wǎng)絡(luò)布局算法是網(wǎng)絡(luò)可視化的基礎(chǔ),主要通過節(jié)點之間的相互作用力更新節(jié)點位置,實現(xiàn)網(wǎng)絡(luò)繪制。最早的布局方法是Eades[1]提出的彈簧布局算法,把網(wǎng)絡(luò)圖形當做物理系統(tǒng),節(jié)點在彈簧彈力的作用下使鋼環(huán)運動,當彈簧的系統(tǒng)能量達到最小時停止移動,但是他的算法沒有遵循胡克定律,而且效率較低。隨后Kamada和Kawai對彈簧布局進行了改進,提出了KK算法[2],通過求能量最小值確定節(jié)點位置,該算法遵循了胡克定律的偏微分方程,提高了算法效率。Frechterman和Reingold[3]提出了FR布局算法,計算相鄰節(jié)點之間的吸引力,以及所有節(jié)點之間的排斥力,節(jié)點在兩者合力下更新位置。力導(dǎo)引布局算法易于理解、容易實現(xiàn)、實用性強,是目前最常用的布局算法,但是不利于用戶發(fā)現(xiàn)社團信息和網(wǎng)絡(luò)特征。

社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個重要拓撲結(jié)構(gòu),即同一社團節(jié)點之間高度互連,不同社團節(jié)點之間連接密度較低[4]。通過對社團結(jié)構(gòu)進行聚類布局,可以使呈現(xiàn)出的社團結(jié)構(gòu)具有對稱性和局部聚合性[5-6]。Nocak[7]提出了Linlog算法,通過計算最小能量來呈現(xiàn)社團結(jié)構(gòu),雖然達到聚類效果,但是無法驗證社團劃分結(jié)果的有效性。鑒于此缺點,朱志良等[8]將社團抽象為節(jié)點,并填充社團內(nèi)部節(jié)點進行網(wǎng)絡(luò)布局。吳渝等[9]提出社團引力導(dǎo)引的布局算法,在FR算法的基礎(chǔ)上加入社團引力,結(jié)合k-means[10]算法通過社團引力和斥力更新節(jié)點位置,采用邊聚類邊布局的方式加快了收斂速度。Zhou等[11]在已知社團劃分結(jié)果的基礎(chǔ)上計算社團引力和斥力,進行節(jié)點聚類,進而清晰地呈現(xiàn)網(wǎng)絡(luò)的社團結(jié)構(gòu)。Huang等[12]通過加權(quán)排斥力和吸引力對節(jié)點位置進行收斂。但是這些社團布局算法主要針對離散社團進行布局,而無法對重疊社團進行可視化呈現(xiàn)。

重疊社團是社團結(jié)構(gòu)的一種特殊形式,對分析網(wǎng)絡(luò)重要節(jié)點在屬性上的多重性特征,理解重疊節(jié)點與社團之間的歸屬性,研究社團功能相似性及差異性等具有重要意義[13-14]。由于重疊節(jié)點與多個社團相互關(guān)聯(lián),使得拓撲結(jié)構(gòu)變得復(fù)雜,如何從中高效解讀和識別重疊節(jié)點信息成為人們研究的熱點。Vehlow等[15]通過層次網(wǎng)絡(luò)布局,展示出重疊社團結(jié)構(gòu),利用視覺映射對重疊社團結(jié)構(gòu)進行編碼,但是忽視了社團內(nèi)部的拓撲結(jié)構(gòu)。針對這一問題,本文先通過重疊社團劃分算法對網(wǎng)絡(luò)進行劃分,然后對其硬劃分并根據(jù)隸屬矩陣加權(quán)求和確定節(jié)點位置,最后對重疊節(jié)點進行精確布局,通過餅圖顏色分配量化節(jié)點信息,實現(xiàn)重疊社團可視化。結(jié)果表明本文的算法可以彌補傳統(tǒng)聚類布局算法的不足,細化重疊節(jié)點位置,呈現(xiàn)出重疊節(jié)點隸屬情況,凸顯了重疊社團結(jié)構(gòu);而且對比實驗證實了本文布局算法符合節(jié)點均勻分布、邊長一致的美學標準。

1 基本布局算法

基本網(wǎng)絡(luò)布局算法傳統(tǒng)上主要采用力導(dǎo)引布局算法,又叫FR算法[3]。力導(dǎo)引布局算法中節(jié)點在引力和斥力作用下進行運動,經(jīng)過不斷迭代,系統(tǒng)最終進入一種動態(tài)平衡狀態(tài),使得節(jié)點分布均勻、邊長統(tǒng)一,符合美學原則。FR算法遵循兩個原則,有邊連接的節(jié)點相互靠近,但是任意節(jié)點不能離得太近。力導(dǎo)引布局節(jié)點之間引力和斥力的定義為

(1)

其中,fa為有邊連接節(jié)點之間的引力,fr為所有節(jié)點之間的斥力,d為2個節(jié)點之間的歐式距離,k為節(jié)點之間的理想距離,理想距離k由畫布的面積和節(jié)點的數(shù)量共同決定,定義為

(2)

其中,C為常數(shù)系數(shù),S為畫布的面積,N為節(jié)點個數(shù)。同時為了限制節(jié)點偏移程度,優(yōu)化網(wǎng)絡(luò)布局,算法使用了“模擬退火”原則。隨著溫度降低,節(jié)點的移動范圍也隨之變小,系統(tǒng)能量降低,當引力和斥力達到平衡且系統(tǒng)到達合適的溫度時,迭代停止,算法實現(xiàn)收斂,達到最佳布局效果。FR算法易于理解實現(xiàn),而且對稱性和聚合性較好。

2 社團布局算法

社團布局算法主要對節(jié)點進行聚類布局,體現(xiàn)節(jié)點的局部聚合性[9]。社團布局算法先計算FR算法的引力和斥力,在此基礎(chǔ)上計算社團中心點斥力和節(jié)點對所屬社團中心節(jié)點的引力,網(wǎng)絡(luò)節(jié)點在有邊連接的節(jié)點間的引力、所有節(jié)點間的斥力、節(jié)點對所屬社團的引力來更新節(jié)點位置。社團布局算法中社團中心節(jié)點之間斥力和節(jié)點對所屬社團的引力定義為

(3)

其中,fca為節(jié)點對所屬社團的引力,fcr為社團中心節(jié)點之間的斥力,g為引力參數(shù),gc為斥力參數(shù),M[v]為節(jié)點的質(zhì)量,由節(jié)點度中心性進行衡量,M[Ci]為社團Ci的質(zhì)量,du為社團中心節(jié)點之間的歐式距離,dv為節(jié)點與社團中心節(jié)點之間的最小歐式距離,定義為

dv=min(d1,d2,…,dk)

(4)

社團布局算法在FR算法基礎(chǔ)上實現(xiàn),符合節(jié)點均勻分布邊長一致的美學原則,而且展示出社團的聚合性。算法使得不同社團節(jié)點彼此遠離,相同社團節(jié)點相互靠近,顯示出明顯的社團結(jié)構(gòu)特性以及社團內(nèi)節(jié)點的相互關(guān)系。

3 重疊社團布局算法

3.1 重疊社團劃分定義

復(fù)雜網(wǎng)絡(luò)社團劃分可行搜索空間如圖1所示,可以分為非重疊社團劃分、離散重疊社團劃分和模糊重疊社團劃分3類。非重疊社團劃分又稱為硬劃分,網(wǎng)絡(luò)中每個節(jié)點只能隸屬于一個社團,且與所屬社團之間具有完全的隸屬關(guān)系。離散重疊劃分又稱為脆性重疊劃分或非模糊重疊劃分,網(wǎng)絡(luò)中任意節(jié)點可以隸屬于不同社團,而且對不同社團的隸屬程度可以分為完全隸屬和完全不隸屬[13],隸屬度取值為“0”或“1”,即在劃分中主要考慮節(jié)點與社團的隸屬關(guān)系。模糊重疊劃分中網(wǎng)絡(luò)中任意節(jié)點可以隸屬于多個社團,而且重疊節(jié)點可以對不同社團有不同的隸屬度,隸屬度在[0,1]間取值,即在劃分過程中細化了節(jié)點對社團的隸屬程度。

圖1 社團劃分可行搜索空間

目前國內(nèi)外絕大多數(shù)對重疊社團的研究主要是進行社團檢測優(yōu)化,得到社團劃分結(jié)果,而沒有針對檢測結(jié)果進行延伸,體現(xiàn)網(wǎng)絡(luò)節(jié)點對社團細致的隸屬度分布信息,從而展示重疊社團結(jié)構(gòu)。傳統(tǒng)的社團布局主要是針對非重疊社團進行布局,而沒有對重疊社團可視化。本文一方面對重疊節(jié)點進行精確布局,量化重疊節(jié)點對各社團之間的隸屬程度,展示重疊社團結(jié)構(gòu)的精確性;另一方面,對非重疊節(jié)點進行聚類布局,體現(xiàn)細致、完整的社團結(jié)構(gòu)信息。

3.2 問題提出和改進思路

基于FR算法實現(xiàn)的社團布局算法在一定程度上可以展示社團結(jié)構(gòu),但是現(xiàn)有社團布局算法主要針對離散社團進行可視化,而沒有面向重疊社團結(jié)構(gòu)進行展示。同時主流的FR算法遵循節(jié)點分布均勻、統(tǒng)一邊長的美學原則,在重疊社團結(jié)構(gòu)上的布局效果并不顯著,從而影響用戶對網(wǎng)絡(luò)拓撲結(jié)構(gòu)的分析。目前社團布局算法存在的問題:1)算法不能很好地應(yīng)用于離散重疊社團和模糊重疊社團布局;2)算法沒有針對重疊節(jié)點展現(xiàn)隸屬度和隸屬關(guān)系。本文在FR算法的基礎(chǔ)上加入社團引力和社團斥力,實現(xiàn)了基于社團的力導(dǎo)引布局算法,同時引入節(jié)點隸屬度,通過定位模型對重疊節(jié)點精確布局,利用餅圖體現(xiàn)出多個社團的隸屬程度和隸屬關(guān)系。由于非重疊節(jié)點單獨隸屬于某個社團,而重疊節(jié)點則與多個社團間存在隸屬關(guān)系,所以非重疊節(jié)點采用聚類布局的方式保證社團間布局緊密,重疊節(jié)點則采取精確定位方式確定節(jié)點位置。

3.3 重疊社團布局算法實現(xiàn)

3.3.1 重疊社團節(jié)點定位模型

TOA定位算法基于移動終端與基站的信號傳播時間,獲取終端與基站的距離,通過建立定位關(guān)系,獲得用戶終端位置[16]。復(fù)雜網(wǎng)絡(luò)的重疊節(jié)點則是基于節(jié)點對社團的隸屬度確定節(jié)點的準確位置,本文為了精確地對重疊節(jié)點進行展示,需要對其位置進行細致的定位,通過重疊節(jié)點與社團隸屬關(guān)系與隸屬程度建立定位方程,進而對重疊節(jié)點進行精確布局。

1)若網(wǎng)絡(luò)被劃分為2個社團,以社團中心節(jié)點C1,C2為圓心,k為兩個社團中心的距離,kμ1,kμ2為半徑畫出兩圓,兩個距離圓相交的點則是重疊社團節(jié)點的坐標,如圖2所示。由于網(wǎng)絡(luò)節(jié)點在布局中具有一定的半徑,為了滿足美學原則,防止節(jié)點出現(xiàn)重疊,則使節(jié)點布局在交點的垂直線上。

圖2 2個社團的重疊節(jié)點定位

當節(jié)點隸屬于2個社團時,由社團中心位置(x1,y1)和(x2,y2)可得出重疊節(jié)點位置的數(shù)學表達式為

(5)

2)若網(wǎng)絡(luò)被劃分為3個社團,以社團中心節(jié)點C1,C2,C3為圓心,k為3個社團中心距離的單位量,以kμ1,kμ2,kμ3為半徑畫圓,3個距離相交的點則是重疊社團節(jié)點的坐標,如圖3所示。

圖3 3個社團的重疊節(jié)點定位

當網(wǎng)絡(luò)節(jié)點隸屬于3個社團(x1,y1)和(x2,y2),(x3,y3)時,重疊節(jié)點坐標的數(shù)學表達式為

(6)

綜上所述,當網(wǎng)絡(luò)被劃分為4個社團時,以社團中心節(jié)點C1,C2,C3,C4為圓心,kμ1,kμ2,kμ3,kμ4為半徑畫出4個圓,4個半徑相交于一點就是重疊社團節(jié)點的坐標,如圖4所示。

圖4 4個社團的重疊節(jié)點定位

當網(wǎng)絡(luò)節(jié)點隸屬于4個社團(x1,y1),(x2,y2),(x3,y3),(x4,y4)時,重疊節(jié)點坐標的數(shù)學表達式為

(7)

如果重疊節(jié)點隸屬社團大于4個,節(jié)點位置則難以進行精確定位,可以采用重疊社團算法直接進行布局,通過調(diào)整幾個社團中心節(jié)點的引力和斥力作用確定節(jié)點位置。若對離散重疊社團中的重疊節(jié)點進行定位,則使得μ1=μ2=…=μm即可確定節(jié)點位置。

3.3.2 重疊社團布局算法

傳統(tǒng)社團布局算法主要計算社團引力和斥力,通過兩者作用力更新節(jié)點位置,進行網(wǎng)絡(luò)布局。為反映重疊社團節(jié)點與社團的關(guān)系,本文布局算法使用了文獻[11]的社團引力和社團斥力計算方式,在此基礎(chǔ)上考慮了節(jié)點對社團的隸屬程度和隸屬關(guān)系。

設(shè)網(wǎng)絡(luò)G為G(V,E),節(jié)點V的集合為{v1,v2,…,vn},節(jié)點對應(yīng)位置為{p1,p2,…,pn},節(jié)點之間邊的集合為{e1,e2,…,en},首先將重疊社團劃分的隸屬矩陣{μ1,μ2,…,μm}進行處理,使得節(jié)點歸屬于占比最大的社團,則G可被劃分為k個社團{C1,C2,…,Ck},每個社團對應(yīng)的社團中心為{u1,u2,…,uk},算法將社團內(nèi)節(jié)點半局部中心性最高的節(jié)點作為該社團的中心節(jié)點。

為了對重疊社團節(jié)點進行進一步布局,首先將重疊社團節(jié)點歸屬于隸屬度最高的社團,計算公式為

max(μ1,μ2,…,μm)∈Cv

(8)

其中,Cv為重疊節(jié)點所屬的社團,μi為節(jié)點對社團的隸屬度,計算得到重疊社團的劃分結(jié)果。

為了進一步展示社團布局效果,本文為不同社團的中心節(jié)點之間添加社團斥力fcr,使得不同社團彼此遠離,防止社團之間過度聚集。任意兩個社團中心點斥力為

(9)

其中,‖pui-puj‖為ui和uj之間的歐氏距離,N(Ci)和N(Cj)分別為社團Ci和Cj的節(jié)點數(shù),由于節(jié)點數(shù)目越多排斥力越大,則社團斥力與社團的規(guī)模呈正比。N為網(wǎng)絡(luò)的總節(jié)點數(shù),gcr為斥力參數(shù),可以阻止不同社團節(jié)點過度靠攏,斥力參數(shù)值的選取主要取決于節(jié)點的數(shù)量和畫布的大小。

為了使得社團內(nèi)節(jié)點向社團中心靠攏,對社團內(nèi)的節(jié)點與該社團的中心節(jié)點之間添加社團引力fcao,定義為

(10)

其中,‖pui-pk‖為節(jié)點與社團中心節(jié)點的歐式距離,gca為引力參數(shù),通過調(diào)整該值控制社團引力的大小,與社團數(shù)目成反比,n為社團數(shù)目,μm為節(jié)點對第m個社團的隸屬程度。

本文算法在社團布局算法的基礎(chǔ)上添加了節(jié)點對社團的隸屬度,因此需要先計算FR算法的引力和斥力來維持系統(tǒng)的平衡,隨后將重疊社團節(jié)點先歸屬于占比較多的社團,再計算社團中心節(jié)點之間的斥力,通過節(jié)點對所屬社團中心點的引力進行加權(quán)求和,節(jié)點在兩者合力下更新節(jié)點位置。對節(jié)點位置迭代后,使用重疊社團節(jié)點定位模型對節(jié)點進行精確定位,使得節(jié)點隸屬度與布局位置相對應(yīng)。

3.3.3 重疊社團布局算法步驟

重疊社團布局算法步驟為

輸入:網(wǎng)絡(luò)G(V,E),最大迭代次數(shù)N,初始溫度T,最小溫度Tmin。

輸出:網(wǎng)絡(luò)節(jié)點位置坐標{p1,p2,…,pn}。

步驟1 根據(jù)輸入,隨機初始化節(jié)點位置,生成位置坐標{p1,p2,…,pn}。根據(jù)式8)計算節(jié)點所屬社團,得到社團劃分結(jié)果C。

步驟2 根據(jù)式1)和式2)計算所有節(jié)點之間的斥力和有邊相連節(jié)點之間的引力,更新節(jié)點位置。

步驟3 根據(jù)式9)計算所有社團中心節(jié)點之間的斥力值,更新節(jié)點位置。

步驟4 根據(jù)式10)計算所有社團內(nèi)節(jié)點對社團的中心節(jié)點的引力值,更新節(jié)點位置。

步驟5 若系統(tǒng)的溫度小于最小溫度或者迭代次數(shù)大于最大迭代次數(shù)N,執(zhí)行下一步,否則轉(zhuǎn)步驟2。

步驟6 根據(jù)重疊節(jié)點定位模型對社團重疊節(jié)點進行精確定位,輸出所有節(jié)點的位置,算法結(jié)束。

在重疊網(wǎng)絡(luò)社團布局算法中,通過FR的模擬退火算法進行收斂,初始溫度隨著迭代次數(shù)的增加而不斷下降,當系統(tǒng)溫度趨近于0時表示網(wǎng)絡(luò)布局達到最終的穩(wěn)定狀態(tài)。步驟1為所有節(jié)點隨機生成位置,步驟2至步驟5為循環(huán),通過計算節(jié)點的斥力、引力以及社團中心點的社團斥力、節(jié)點對社團中心點的社團引力,進而更新節(jié)點的位置,直至系統(tǒng)溫度小于給定的下限閾值或者迭代次數(shù)超過N;否則,繼續(xù)調(diào)整節(jié)點位置。最后,通過重疊節(jié)點定位模型對節(jié)點進行精確定位,更新重疊節(jié)點位置。

4 實驗結(jié)果分析

為了驗證重疊社團布局算法的可視化效果,本文選取了FR算法和文獻[8]等布局結(jié)果進行對比,FR算法、文獻[8]和文獻[11]算法是先劃分社團再可視化布局,CGDA算法[9]是邊聚類邊布局方式,可以從兩個方面與本文算法形成明顯對比。由于本文算法采用的社團劃分算法為模糊重疊社團發(fā)現(xiàn)算法,不同于對比算法硬劃分的方式,因此社團劃分的結(jié)果與之不同,但最終可視化結(jié)果主要針對網(wǎng)絡(luò)社團結(jié)構(gòu)進行有效展示。網(wǎng)絡(luò)擁擠程度可以刻畫節(jié)點分布的均勻性,邊長偏差可以體現(xiàn)邊長的勻稱性,為定量分析本文算法的合理性,選取點分布方差、邊長偏差、節(jié)點分布偏差實驗指標進行實驗,為真實反映實驗結(jié)果,算法對比數(shù)據(jù)源于文獻[17]。

4.1 重疊社團可視化結(jié)果分析

Dolphins網(wǎng)絡(luò)數(shù)據(jù)集描述的是生活在新西蘭的62只海豚形成的社會關(guān)系網(wǎng)絡(luò),節(jié)點代表海豚,邊代表海豚之間的接觸次數(shù),網(wǎng)絡(luò)包含62個節(jié)點和152條邊。本文算法與文獻[8]算法、CGDA算法[9]在Dolphins網(wǎng)絡(luò)數(shù)據(jù)集的布局結(jié)果如圖5所示。文獻[8]算法只能針對非重疊社團進行布局,而且該算法雖然阻止了不同社團節(jié)點位置錯雜現(xiàn)象,但是網(wǎng)絡(luò)節(jié)點過于擁擠,若無顏色區(qū)分,用戶很難發(fā)現(xiàn)社團結(jié)構(gòu)。CGDA算法相較于朱志良算法清晰地展示了社團結(jié)構(gòu),但是難以對重疊社團進行展示。本文通過餅圖形式精確表示出社團隸屬度,直觀展示出重疊網(wǎng)絡(luò)節(jié)點以及重疊程度,用不同的顏色標識社團信息,在布局上隸屬于某個社團的隸屬程度越大則距離該社團更近。從圖5c可視化結(jié)果中可以看出,節(jié)點8,19,20,37,39等節(jié)點為網(wǎng)絡(luò)中的共享節(jié)點,這些節(jié)點位于社團邊界位置,展示了對幾個社團的貢獻程度和歸屬關(guān)系。本文的重疊社團布局算法能夠很好地應(yīng)用于重疊社團,清晰地展示了重疊社團節(jié)點且社團結(jié)構(gòu)較為顯著,整個網(wǎng)絡(luò)圖具有很強的對稱性。

a 文獻[8]布局結(jié)果

Football網(wǎng)絡(luò)數(shù)據(jù)集描述的是美國足球聯(lián)賽構(gòu)成的社交網(wǎng)絡(luò),節(jié)點代表足球隊,邊代表兩只球隊進行過一次比賽,網(wǎng)絡(luò)包含115個節(jié)點和616條邊。與Dolphins網(wǎng)絡(luò)相比,數(shù)據(jù)集較為龐大,需要對網(wǎng)絡(luò)節(jié)點進行縮小來展示。從圖6可以看出FR算法無法滿足復(fù)雜的網(wǎng)絡(luò)展示的美學需求,難以對社團結(jié)構(gòu)進行展示。文獻[11]的算法雖然對網(wǎng)絡(luò)層次結(jié)構(gòu)進行了明顯的區(qū)分,但是它只針對非重疊社團結(jié)構(gòu)進行可視化,本文布局算法既展示了網(wǎng)絡(luò)的層次結(jié)構(gòu),又對重疊節(jié)點的隸屬程度和隸屬關(guān)系進行了很好的呈現(xiàn)。

a FR算法布局結(jié)果

4.2 實驗指標分析

為了驗證布局效果的有效性,通過美學標準以及布局結(jié)果帶給人的直觀感受分析布局效果。Sugiyama、Sindre和Purchase等在幾年的時間里提出了16項網(wǎng)絡(luò)繪圖的美學標準,其中5項美學標準是普遍適用的,包括最少的邊交叉數(shù)量、相鄰節(jié)點位置相接近、直線邊、節(jié)點密度均勻及對稱性[18]。對于網(wǎng)絡(luò)社團結(jié)構(gòu)可視化而言,希望最終的布局效果盡可能滿足上述指標。本文主要通過文獻[8]、文獻[19]提出的點分布方差、邊長偏差、節(jié)點偏差對相同數(shù)據(jù)集進行對比分析。

4.2.1 點分布方差

(11)

4.2.2 邊長偏差

邊長的均勻程度體現(xiàn)了布局算法的美學原則,因此將最小邊長和最大邊長和平均邊長的差值作為衡量標準,將邊長記為l,將邊長偏差記side_length_deviation。公式定義為

(12)

4.2.3 節(jié)點分布偏差

節(jié)點的最小距離展現(xiàn)了布局算法中斥力的作用效果,將最佳分布距離減去最小節(jié)點距離的絕對值與圖的顯示面積的比值作為節(jié)點分布偏差,記為node_distribution_deviation。公式定義為

(13)

其中,最佳距離為圖的顯示面積與圖節(jié)點數(shù)量的比值,定義為

(14)

由表1和表2以及可視化結(jié)果分析可知,選取相同網(wǎng)絡(luò)數(shù)據(jù)集進行實驗,本文算法相較于其他算法點分布方差較小,說明算法布局可以有效減少節(jié)點錯雜以及降低局部拓撲結(jié)構(gòu)的混亂現(xiàn)象。同時本文算法節(jié)點分布方差較低,表明節(jié)點分布更為均勻,符合網(wǎng)絡(luò)布局的美學標準,而且可以降低布局的擁擠程度。由于重疊社團布局算法將重疊節(jié)點分布在幾個社團之間,相較于其他布局算法節(jié)點分布偏差較小,對重疊節(jié)點進行精確布局可能會使得邊長出現(xiàn)少量拉伸現(xiàn)象,但重疊節(jié)點相較于整個網(wǎng)絡(luò)節(jié)點較少,尚在用戶可接受范圍。

表1 Dolphins網(wǎng)絡(luò)的實驗結(jié)果

表2 Football網(wǎng)絡(luò)的實驗結(jié)果

5 結(jié)論

針對復(fù)雜網(wǎng)絡(luò)重疊社團結(jié)構(gòu)的可視化需求,本文在傳統(tǒng)的社團結(jié)構(gòu)布局算法基礎(chǔ)上融入了社團隸屬度,在布局上對重疊節(jié)點進行精確布局,在視覺展示上通過餅圖對重疊節(jié)點進行編碼,選取不同顏色對節(jié)點隸屬程度進行著色。實驗結(jié)果表明本文算法節(jié)點分布均勻,而且降低了節(jié)點密集程度,滿足了美學標準,在位置布局以及視覺上對重疊節(jié)點的展示提高了重疊節(jié)點的辨識度,體現(xiàn)出重疊社團的網(wǎng)絡(luò)特征。與傳統(tǒng)社團布局算法相比,本文算法可以直觀呈現(xiàn)出重疊社團節(jié)點的隸屬程度以及隸屬關(guān)系,同時保留了網(wǎng)絡(luò)的聚類布局效果,彌補了傳統(tǒng)社團布局算法不能對重疊社團結(jié)構(gòu)展示的缺陷,豐富了網(wǎng)絡(luò)布局。

本文主要針對全局社團結(jié)構(gòu)進行可視化,而沒有考慮局部社團結(jié)構(gòu),區(qū)域內(nèi)的節(jié)點聚類是分析網(wǎng)絡(luò)社團的重要方式。因此,在下一步工作中,可以采用相應(yīng)布局算法對局部社團結(jié)構(gòu)進行布局,體現(xiàn)出局部拓撲結(jié)構(gòu)信息。本文算法可以對重疊社團進行很好的呈現(xiàn),但是由于需要對重疊節(jié)點進行二次布局,使得該布局算法時間略高于其它布局算法,今后可以結(jié)合網(wǎng)絡(luò)拓撲結(jié)構(gòu),在社團劃分的同時進行布局,加快算法布局速度。