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

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

0 引言

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

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

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

1 基本布局算法

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

(1)

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

(2)

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

2 社團(tuán)布局算法

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

(3)

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

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

(4)

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

3 重疊社團(tuán)布局算法

3.1 重疊社團(tuán)劃分定義

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

圖1 社團(tuán)劃分可行搜索空間

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

3.2 問題提出和改進(jìn)思路

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

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

3.3.1 重疊社團(tuán)節(jié)點(diǎn)定位模型

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

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

圖2 2個社團(tuán)的重疊節(jié)點(diǎn)定位

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

(5)

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

圖3 3個社團(tuán)的重疊節(jié)點(diǎn)定位

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

(6)

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

圖4 4個社團(tuán)的重疊節(jié)點(diǎn)定位

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

(7)

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

3.3.2 重疊社團(tuán)布局算法

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

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

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

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

(8)

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

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

(9)

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

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

(10)

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

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

3.3.3 重疊社團(tuán)布局算法步驟

重疊社團(tuán)布局算法步驟為

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果分析

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

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

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

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

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

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

4.2 實驗指標(biāo)分析

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

4.2.1 點(diǎn)分布方差

(11)

4.2.2 邊長偏差

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

(12)

4.2.3 節(jié)點(diǎn)分布偏差

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

(13)

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

(14)

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

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

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

5 結(jié)論

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

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