展示網絡重疊社團結構的可視化布局算法

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

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

0 引言

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

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

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

1 基本布局算法

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

(1)

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

(2)

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

2 社團布局算法

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

(3)

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

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

(4)

社團布局算法在FR算法基礎上實現,符合節點均勻分布邊長一致的美學原則,而且展示出社團的聚合性。算法使得不同社團節點彼此遠離,相同社團節點相互靠近,顯示出明顯的社團結構特性以及社團內節點的相互關系。

3 重疊社團布局算法

3.1 重疊社團劃分定義

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

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

目前國內外絕大多數對重疊社團的研究主要是進行社團檢測優化,得到社團劃分結果,而沒有針對檢測結果進行延伸,體現網絡節點對社團細致的隸屬度分布信息,從而展示重疊社團結構。傳統的社團布局主要是針對非重疊社團進行布局,而沒有對重疊社團可視化。本文一方面對重疊節點進行精確布局,量化重疊節點對各社團之間的隸屬程度,展示重疊社團結構的精確性;另一方面,對非重疊節點進行聚類布局,體現細致、完整的社團結構信息。

3.2 問題提出和改進思路

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

3.3 重疊社團布局算法實現

3.3.1 重疊社團節點定位模型

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

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

圖2 2個社團的重疊節點定位

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

(5)

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

圖3 3個社團的重疊節點定位

當網絡節點隸屬于3個社團(x1,y1)和(x2,y2),(x3,y3)時,重疊節點坐標的數學表達式為

(6)

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

圖4 4個社團的重疊節點定位

當網絡節點隸屬于4個社團(x1,y1),(x2,y2),(x3,y3),(x4,y4)時,重疊節點坐標的數學表達式為

(7)

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

3.3.2 重疊社團布局算法

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

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

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

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

(8)

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

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

(9)

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

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

(10)

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

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

3.3.3 重疊社團布局算法步驟

重疊社團布局算法步驟為

輸入:網絡G(V,E),最大迭代次數N,初始溫度T,最小溫度Tmin。

輸出:網絡節點位置坐標{p1,p2,…,pn}。

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

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

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

步驟4 根據式10)計算所有社團內節點對社團的中心節點的引力值,更新節點位置。

步驟5 若系統的溫度小于最小溫度或者迭代次數大于最大迭代次數N,執行下一步,否則轉步驟2。

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

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

4 實驗結果分析

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

4.1 重疊社團可視化結果分析

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

a 文獻[8]布局結果

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

a FR算法布局結果

4.2 實驗指標分析

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

4.2.1 點分布方差

(11)

4.2.2 邊長偏差

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

(12)

4.2.3 節點分布偏差

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

(13)

其中,最佳距離為圖的顯示面積與圖節點數量的比值,定義為

(14)

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

表1 Dolphins網絡的實驗結果

表2 Football網絡的實驗結果

5 結論

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

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