一種基于層次化社團結構的網絡可視化方法

談煜，梁潤鵬

0 引言

大型網絡的可視化面臨3個主要問題：第一是如何對節點進行合理的布局。為此，需要保證節點布局的均勻性、對稱性和美觀性[1]，要盡量避免網絡中不相關節點之間的重疊，同時要保證聯系緊密的節點之間位置盡量靠近。二是在展現網絡整體結構的同時又不遺漏重要的局部信息。復雜網絡的規模巨大，信息繁多，所以從整體上對網絡的結構有一定的了解是十分必要的，而有些局部信息能對網絡的形成和演化起到重要作用，因此也必須予以保留。三是要體現網絡的層次化特性。對于大型網絡，由于其規模龐大，如果直接對網絡進行可視化，用戶很難從可視化效果中觀察出有用信息，因此將網絡劃分為層次化社團結構再進行可視化是非常必要的。

網絡可視化領域中最常用的布局算法是力導引算法，該方法最早由Eades于1984年提出[2]。力導引算法不受網絡自身性質的限制，且產生的布局效果對稱美觀，但是由于其復雜度較高而無法適用于大規模網絡。后來，在力導引算法的基礎上產生了多尺度（multiscale）方法[3]以及FADE方法[4]等改進，這些方法都采用了圖劃分的思想，提高了處理速度和處理數據的規模，但由于他們的劃分方法只是將網絡簡單的拆分為子圖，從而很難體現網絡本身的特性。

基于上述考慮，本文提出了一種基于層次化社團結構、力導引算法、局部環形布局算法并可以應用于大型網絡的快速可視化方法，用 JAVA 語言編程對其加以具體實現。層次化社團結構[5]是指網絡中相互連接緊密的節點形成一些小規模的社團，而這些較小的社團再結合成較大的社團，如此依次向上聚合，形成具有層次性的結構。針對上面所提到的3個問題，本文提出的方法都做了相應的考慮。

此外，本文提出的方法可以利用閾值調節來完成力學模型算法和環形布局算法的切換，從而可以使用戶根據處理不同網絡數據的需要進行自由選擇，提高了方法的通用性和便捷性。

1 方法的基本思想

當前主流的可視化軟件和工具大多都提供了力學模型算法進行布局，而力導引算法的局限性導致了它們不適用于較大規模數據的處理。首先采用了 Blondel[5]快速算法對網絡進行處理，將網絡劃分成多個層次的不同社團，然后依次在每一層次分別使用力導引算法，最后再在同一平面上將整個網絡展示出來，如圖1所示：

圖1 Blondel快速算法的處理過程示例，可以看到每次循環中，首先通過模塊度優化得到相應社團，再將屬于同一個社團的節點或子社團合并成更大的社團(取自文獻[5])

選擇的力導引算法是FR算法[6]，該算法雖然只適用于較小規模的網絡，由于事先已經將網絡劃分成社團結構，并將社團視為節點進行處理，而社團的數目比節點的數目要小的多，這樣就大大提高了處理效率，從而能夠較好地處理大規模網絡。

而在社團劃分算法的選擇上，選擇Blondel快速算法。選擇 Blondel快速算法的主要原因有兩個：第一，Blondel快速算法是基于大規模網絡數據的社團劃分算法，在已有社團劃分算法中是速度最快的方法之一；第二，Blondel快速算法可以將網絡劃分為多個層次，這樣有利于將原網絡分為幾個層次分別處理，加快了數據處理速度。

為了能夠更好地將力導引算法和社團方法結合起來，必須要對原來的FR算法的一些參數進行修改。在原文獻中，顯示區域設置為矩形，這樣做的目的其實是為了能夠最大程度的占用電腦屏幕空間。方法中，由于需要在每個層的每個社團中使用布局算法，將顯示區域設置為圓形，以方便對原網絡的層次化處理。同時，原方法中的引力和斥力系數 K的定義為：

其中，為常數。而在我們的方法中，K定義為：

其中，R為社團的半徑大小。

假設Blondel算法將網絡從低到高劃分成N層，上一層中的社團包含下一層之中的社團，以此類推。這樣，第 N層為最低的一層，即為網絡中每個節點所在的層，第1層為最高的一層。在這個方法中，需要在第1層上再加一層，這一層之中只有一個社團，即為整個網絡，視作第0層。在此基礎上，從N-1層開始，由低到高依次對每層中的每個社團內部的社團（或節點）使用彈簧算法，直到第0層為止。

為了使社團中的子社團不超過以該社團半徑 R為半徑的圓形顯示區域，在力導引布局的過程中，如果某次節點位置更新使得子社團的半徑到圓心的距離超過了R-r(r為子社團自身的半徑)，則將子社團強制移動到距離圓心半徑 R-r的位置，如見圖2、圖3所示：

圖2 子社團在力導引算法布局過程中

圖3 社團半徑取法示意圖

為了更好地應對層次化處理方式，可對于每個社團或節點，都定義了一個半徑值，這個值實際上就是最終可視化結果中每個社團或節點的顯示區域。對于最低層（第 N層）的節點，事先定義好節點的半徑（常數），第N-1層開始直到第 0層，每層中每個社團的半徑取決于它所包含的子社團。采用的計算公式如下：

事實上，這樣的計算方法往往會導致顯示區域過大，從而使整個可視化效果中節點顯得過于稀疏。根據對實際數據的處理經驗，這種情況對于越高的層越明顯。我們也提出了另一種社團半徑的定義方法：

這個公式在一定程度上可以改善顯示區域過大的問題。一般而言，在第 N層可以采用第一種半徑定義方法，而在比較高的層則采用公式（4）所定義的半徑。此外，我們也使用了一種另一種較為簡單卻有效的方法，即在公式（3）和公式（4）定義的基礎上，不同層中的社團半徑乘以一個不同的大于0且小于1的系數。一般而言，越高的層乘以的系數越小，這樣可以有效的減少因為子社團半徑簡單相加而造成的顯示空間浪費。

3 基于力導引算法的改進

以上即為提出方法的基本思想，但是對實際網絡數據的處理經驗顯示，如果僅僅對網絡這樣處理，可視化效果并不理想，尤其對大規模網絡而言。

首先要對FR算法中定義的斥力和引力進行改進。力導引算法原本是用于處理非層次結構的小規模網絡的，特別地，網絡中的每個節點大小都一致。而對于層次化結構，由于同一層中每個社團的大小都不盡相同，而且不同層的顯示區域大小差別巨大，往往都是差一個數量級的，導致原來的斥力引力已經不合適，這也是可視化效果中節點、社團分布不均勻的一個重要原因。

為了使FR算法更加適應層次化結構，分別對斥力和引力的作用范圍做了限定。為了使社團或節點間的重疊盡量減少，當社團或節點過于靠近或者已經有重疊時，需要讓它們之間的引力消失。因此，將社團之間引力的作用范圍設置為：，其中，和分別為社團A和B的半徑大小。這樣，當A和B重疊時，它們之間將只有排斥力而沒有吸引力，如圖4所示：

圖4 排斥力的作用范圍示意圖

為了使社團或節點之間的排斥力不致過大，同時對某些稀疏網絡可以節約一些處理時間，采用了類似于N-body問題[7]的方法。將斥力的作用范圍設置為：，其中，和分別為社團A和B的半徑大小。這樣，當A和B之間的距離超過它們半徑和的兩倍時，它們之間將只有吸引力而沒有排斥力，如圖5所示：

圖5 吸引力的作用范圍示意圖

通過這種限定，可以提高力導引算法在節點布局均勻方面的效率。

以上對斥力和引力作用范圍的限定還有另外一個好處。可以看出，在進行FR算法布局的過程中，大部分社團或節點之間都只有一種力作用，這樣可以使節點或社團位置變化的幅度更小，從而在一定程度上避免了布局時圖的結構出現較大的波動，從一定程度上保證了布局的穩定性。

對非加權網絡而言，在節點之間最多只有一條邊連接。而通過Blondel快速算法得到的多層社團結構中，每層中的社團之間可能存在多條邊連接，也就是說，從第N-1層到第0層，處理的圖已經是加權網絡。相應的，需要在模型中體現加權連邊的存在。在原FR算法中，節點間引力的定義為：

其中，表示節點間的距離，表示節點間的理想平均距離。方法中，需要將引力乘以社團之間連邊的權重，即：

同時，由于多層社團結構中每層中的社團半徑大小不同，一個很自然的想法就是將一個社團所受到的斥力乘以另一個社團的大小。然而，這樣的做法容易引起社團布局的紊亂。特別是當每層中社團半徑大小差異很大時，較大的社團對較小的社團的排斥力將很大，從而將小社團排斥得很遠，導致網絡整體結構的不協調。因此，對于排斥力，不計社團間大小的差異，而采用原算法中排斥力的定義：

3 局部環形布局的修正

一般來說，如果兩個社團間的連邊越多，根據社團的定義[8]，這兩個社團間的聯系就越緊密，在可視化結果中的距離應該越近。但是力導引算法并不能保證連邊多的社團之間擁有合適的距離，盡管在方法中社團間的連邊越多它們之間的吸引力越大。所以需要在使用FR算法布局的同時，對社團的布局進行局部的修正，以彌補力導引算法本身的缺陷。為此，首先引入社團間連邊密度的概念。定義多層社團結構中每層中社團A和B之間的連邊密度為：

其中，表示社團A和B之間的連邊數目，E表示該層中社團之間的連邊總數。

引入了社團間連邊密度的概念之后，就可以在使用力導引布局之前，對社團間的緊密程度先做一個總體的評估。設定一個閾值t(0t1)，當社團間的連邊密度大于t時，就認為社團之間聯系緊密，將這些社團取出，以便進一步的處理。在取出的所有社團中，如果社團之間有鄰邊，則將它們加入一個集合中，這樣就可以得到一個或幾個集合。對于每個集合中的社團，我們在不影響社團本身結構的情況下進行合并。合并的具體含義如下：

1.對于集合中的每個社團，保持其內部子社團的布局不變，而將集合中的所有社團視為一個新的社團，集合外任何社團對集合內部的社團的作用力將視為作用在這個新的社團上；

2.在新社團內部，集合中的所有社團進行環形布局[9]，為此，需要計算出它們的最大半徑r，并通過這個最大半徑計算出新社團的半徑大小R，設集合中的社團個數為n，則定義R的計算公式如下：

設新社團的坐標分別為 x，y,則集合中的社團（m）的坐標為：

通過以上的處理，實現了在全局使用力導引算法而局部使用環形布局的功能。實踐證明，通過這種方法完全可以解決問題3，從而彌補了僅僅使用力導引算法的不足，如圖6所示：

圖6 環形布局示意圖

5 可視化效果

按網絡規模大小，從高到低依次選取3組網絡數據，分別是Zachary's karate club，US Air97和Power grid，作為用于測試的網絡。網絡具體信息，如表1所示：

表1 用于可視化對比的網絡數據信息表

使用本文提出的方法分別對以上 3個網絡進行可視化布局，來考察其方法對于不同規模不同性質的網絡可視化效果，如圖7、圖8、圖9所示：

圖7 對karate網絡的布局效果

圖8 對US air 97網絡的布局效果

圖9 對power grid網絡的布局效果

以上3個圖都取閾值等于0.3，可以看到，無論是對于大型網絡，還是小型網絡，我們提出的方法中社團之間的距離都較為合適，而且無論是節點還是社團分布都較為均勻，用戶可以很輕松的辨認出不同的社團。由此可見，本文所提出的方法對不同規模、不同特性的網絡都具有較好的布局效果，具有很好的適應性和通用性。

小結

本文提出了一種基于層次化社團結構的可視化處理方法，采用力導引算法和環形布局算法相結合的方式。這種方法既保證了聯系緊密的社團之間距離合適，又能夠發揮布局算法的優勢，較為合理的更新節點的位置，在兩種布局之間達到一種最佳平衡。同時，該方法算法復雜度并不高，從而可以更加有效地處理大規模數據。由此可見，本文所提出的方法對不同規模、不同特性的網絡都具有較好的布局效果，具有很好的適應性和通用性。

[1]Battista G,Eades P,Tamassia R,Tollis I.Graph drawing:Algorithms for the visualization of graphs [M].1998,Prentice-Hall,Englewood Cliffs.

[2]Eades P.A heuristic for graph drawing [J].CongressusNumerantum,1984,42: 149-160.

[3]HadanyR,Harel D.A multi-scale algorithm for drawing graphs nicely [J].Discrete Applied Mathematics,2001,113(1):3-21.

[4]Quigley A,Eades P.FADE: graph drawing,clustering,and visualabstraction [J].Lecture Notes in Computer Science,2000,1984: 197-210.

[5]Blondel V,Guillaume J,Lambiotte R,Lefebvre E.Fast unfolding of communities in large networks [J].J.Stat.Mech.,2008,P10008.

[6]Fruchterman T,Reingold E.Graph drawing by force-directed placement [J].Software - Practice & Experience,1991,21(11): 1129–1164.

[7]Josh Barnes and Piet Hut.A hierarchical O(NlogN)force calculation algorithm [J].Nature,1986,324:446-449.

[8]Fortunato S.Community detection in graphs [J].Physics Reports,2010,486: 75-174.

[9]Breitkreutz B,Stark C,Tyers M.Osprey: A network visualization system [J].Genome Biology,2003,4(3):R22-0012.6.