MSNV：基于多層次社團劃分的網絡結構可視化方法

王賢剛 姚中華 宋漢辰

摘要：針對大規模網絡節點數目龐大、結構復雜性高，有限的屏幕空間難以展示其結構特征的問題，提出了一種基于社團劃分的多層次網絡可視化方法。首先，使用基于網絡模塊度的社團劃分算法對網絡節點進行劃分，并采用貪婪算法尋找最大模塊度的社團劃分，得到不同層次粒度的社團；其次，通過設置層次約束力以改進經典力導引算法（FDA），使改進的算法能對不同層次粒度的社團實現分層布局，解決FDA無法展示網絡節點層次性的問題；最后，使用多窗口視圖、Overview+Detail等交互方法分別展示高層社團和底層節點，實現兼顧網絡高層次宏觀結構和低層次局部細節的顯示。仿真實驗中，該算法的社團劃分相較于自包含GN算法在效率和準確率上有所提高。案例分析表明，所提方法在大規模網絡結構的顯示和交互方面具有良好的效果和性能。

關鍵詞：大規模網絡；多層次；可視化；社團劃分；力導引算法

中圖分類號：TP393.02 文獻標志碼：A

Abstract：Focused on the issue that largescale network has characteristics of huge number of nodes， high structural complexity and difficulty to demonstrate its structural characteristics by the limited screen space， a multilevel network visualization method based on community detection was proposed. Firstly， a community detection algorithm based on network modularity was used to detect the network node and a greedy algorithm was used to find the community detection with maximum modularity to get different level of granularity communities. Then， in order to solve the problem that the ForceDirected Algorithm （FDA） could not display network nodes hierarchically， the classic FDA was improved by setting the level blinding force to achieve hierarchical layout of different level of granularity communities. Finally， high level communities and low level nodes were displayed respectively by using the interactive method such as multiwindow view and Overview+Detail， meeting the requirement of both network highlevel macrostructure and lowlevel details of the display. In the simulation test， the community detection algorithm is faster and more accurate compared to selfcontained GN （GirvanNewman） algorithm. The theoretical analysis and simulation results show that the proposed method has good effect and performance in display and interaction of largescale network structure.

Key words：largescale network； multilevel； visualization； community detection； ForceDirected Algorithm （FDA）

0 引言

大規模網絡數據規模龐大、拓撲結構復雜，直接對其進行可視化會導致顯示重疊、層次信息難以觀察，無法有效降低網絡分析人員的負擔。為解決這一問題，學者們提出了很多策略和方法，對大規模網絡進行層次劃分和改進布局算法是提高網絡可視化質量的有效途徑。

單純的節點布局無法有效展示大規模網絡的宏觀結構，網絡層次劃分是分析網絡結構和功能的主流方法。Chan等[1]提出了出度布局（Out Degree Layout， ODL）算法，以網絡節點的出度為依據將整個網絡劃分為不同的層次，但沒有考慮節點間的聯系，分級波動性較大。為提高布局質量，展示網絡整體結構，Agapito等[2]提出了網絡節點的分級顯示，通過分級算法將節點分為多個等級，并利用力學模型算法對特定等級的節點進行布局，但難以展示網絡整體層次關系。Palla等[3]和Jaewon等[4]認為社團是一種互聯互通的全耦合網絡的集合，并基于此提出了派系過濾算法（Clique Percolation Method， CPM）方法對網絡的社團進行劃分，但由于其算法復雜度過大難以在大規模網絡中使用。Girvan和Newman提出了基于分裂的GN（GirvanNewman）算法[5]，彌補了一些傳統算法上的不足，但在社團數目未定的情況下，該劃分算法不能自動終止[6]。為了解決社團劃分的終止問題，Newman定義了社團的模塊度Q[7]，Q是社團連接強度的期望值，與社團劃分數目聯系緊密，可以作為社團劃分的依據，是現今使用最廣泛的衡量社團結構劃分優劣的指標[8]。樹狀結構是當前解決多層次網絡較為常用的方法，如TreeNetViz[9]、TreeGraph和DAViewer[10]等，但樹狀結構可視化多用在屬性明確、屬性間層次分明的網絡中，如地域信息網絡、協議信息網絡或上下級關系網絡，本文研究的是基于網絡節點的聯系緊密度的層次劃分，目前的樹狀結構難以展示節點間聯系緊密度。

可視化布局的相關方法廣泛應用于大型網絡的結構發現，經典的網絡布局方法是Eades[11]提出的力導引布局算法（ForceDirected Algorithm，FDA），FDA仿真物理力學，布局結果自然，但無法展示網絡的層次信息。Kamada和Kawai[12]對力導引算法進行了改進，使節點之間的距離與其最短路徑距離成正比，從而確定網絡節點的布局位置，但在多層次網絡中容易產生混亂。胡華全 [13]提出了融合力導引布局算法（Hybrid Force Directed Layout，HFDL），通過循環方式降低布局算法對輸入值的敏感度，從而得到更好的布局結果。實現大規模網絡的可視化有很多困難，主要表現在：1）網絡節點和連邊的數目過大，直接可視化難以有效觀察網絡整體拓撲結構；2）網絡以社團形式展開時，難以尋求合理的自動化布局；3）一般交互策略難以兼顧網絡的整體結構和局部細節，分析人員的工作量太大。

針對上述問題，本文提出基于社團劃分的多層次大規模網絡結構可視化方法，方法利用社團劃分算法將整個網絡劃分為多個層次的社團，并對社團集合采用改進的力導引布局算法進行布局。本文的社團劃分與可視化方法主要有以下特點：1）利用社團劃分應對大型網絡的結構顯示問題。將大規模節點轉化為有限社團，宏觀拓撲結構清晰。2）利用改進的力導引算法布局社團節點?；陬~外電荷量的方法使布局層次分明，社團規模從內到外遞增，便于區分。3）采用主副窗口協同交互，支持社團逐級展開和跳級展開，在顯示上同時兼顧網絡整體結構和局部細節、社團外部聯系和內部結構。

1 基于社團聚類的網絡結構層次劃分算法

社團劃分是分析網絡結構和功能的有效方法。在真實網絡中，每一個節點都與其他節點產生作用，根據作用的類別和強弱可將網絡劃分為多個聚合團，每個聚合團內節點互相作用的緊密程度顯著大于團間的作用，這些聚合團被稱為社團[5]。大規模網絡可以認為是由若干個社團構成的，社團間的結構可以被看成網絡的整體結構。通過社團劃分，可以更加有效地對大規模網絡的結構進行觀察和分析。

由于社團是網絡中聯系緊密節點的集合，具有一定的特征和獨立性，可以采用類似聚類的方式得到，目前社團劃分算法主要包括去邊法和聚點法。去邊法通過循環迭代找到并刪除聯系較弱的邊，最終將網絡分成幾個互不相連的社團，典型算法如Newman的GN算法[5]和Radicchi的自包含GN算法[14]，但GN算法復雜度為O（n3），耗時太大，不適合在大規模網絡中使用，自包含GN算法雖然改進了算法復雜度，但該算法在社會性網絡之外的其他網絡中效果較差；聚點法是將聯系緊密的節點聚類合并，典型算法如Newman在GN算法的基礎上提出了社團快速劃分法[15]，該算法是一種基于網絡模塊度最大化思想的聚類算法，適用于規模較大的復雜網絡，算法復雜度為O（n2）。

Q的取值在0～1，大量實驗表明，Q值一般不可能接近1[6]?，F在學者認為，一個網絡的模塊度Q值大于0.3即可說明該網絡具有明顯的社團結構[6]。

由于網絡涉及節點和邊數目較大，為提高效率，本文在社團劃分之前先對節點進行分簇，然后再對這些簇進行社團劃分，簇劃分依據為簇內節點可達，簇間無連邊。合并兩個無關聯的簇不會改變網絡模塊度，只在簇內進行社團劃分可以避免每次聚類都要進行全局遍歷。

本文社團劃分過程分為貪婪搜索、遞進聚合、終止檢查三個階段，社團劃分算法流程如圖1所示。

其中：m由式（3）確定，∑CwiAui是節點u和節點w所在社團C中所有節點連邊權值的總和，ku為節點u與整個網絡其他節點連邊權值的總和，∑Cwiki是社團C中所有節點與整個網絡其他節點連邊權值的總和。得到網絡模塊度的改變量ΔQuw后采用貪婪算法，找到最大的max ΔQuw，且max ΔQuw>0，刪除原社團X，將節點u加入到節點w所在的社團C；如果社團X中存在多個節點，由于社團內的節點聯系緊密，可認定該社團的節點具有單個節點的性質，此時將該社團的節點全部移出，加入到相鄰節點j所在的社團，并計算此時的網絡模塊度Q的改變量QXw=∑XuΔQuw，之后采用單節點社團的方法對節點進行歸類。

遞進聚合階段 將第一階段形成的社團視為單個節點，社團節點的位置為原社團中所有節點的中心，社團節點間連邊的權值為原社團間連邊權值的和，并重新對式（2）中的A進行計算。然后重復貪婪搜索過程，形成更高層次的社團，逐次迭代得到不同層次的社團。

終止檢查階段 每次迭代后計算當前整個網絡模塊度QT，并與前一次結果作比較，當QT≤QS或達到迭代次數時停止社團劃分，以前一次劃分結果為最終結果。

上述社團劃分流程通過計算整個網絡的模塊度并找到其最大值，并在得到最大值位置停止迭代；必要時也可由觀察者自己交互指定社團劃分迭代次數，根據分析需求確定迭代終止條件。兩種劃分方式分別記為終極劃分和逐級劃分，二者關系如圖2所示。

2 多層次網絡結構可視化方法

2.1 面向多層次網絡改進的FDA布局算法

上述社團劃分算法兼顧了網絡整體結構和局部細節，但由于劃分層次結構過多，還存在難以在同一界面有效顯示的問題，且目前尚未發現對不同層次節點進行統一布局的有效算法。力導引布局算法是一種對同質節點布局有效的經典算法，但無法分辨不同層次節點。本文提出了一種基于額外電荷量的力導引改進算法，對不同層次進行區分布局。

算法的基本思想為：在對原有節點之間的引力和斥力不造成影響的前提下，通過額外電荷量對節點的布局位置產生影響。例如在窗口的中心固定一個單位正電荷，同時在不同社團中根據層次的高低附加額外的正電荷量，層次越高的電荷量越大，從而驅動不同層次的社團在界面中呈圓環狀依次展開，越靠近中心的層次等級越低，反之越高。

按照改進的力導引算法實現的混合層次節點布局效果如圖3所示。由于原始節點不受額外電荷斥力影響，展開的社團可以在中心區域按照經典FDA進行布局，其局部結構細節得以展示；單層次社團中L=Lmin，由式（4）可得社團不受電荷斥力影響；多層次社團中除了原始節點，其余不同層次的社團受到電荷斥力影響，布局呈環狀結構，低層社團和高層社團從內到外依次展開。

2.2 面向多層次網絡的交互設計

以社團劃分和多層次布局算法為基礎，本文開發了多層次網絡可視化工具MSNV（Multilayer Structure Visualization of Network），針對社團可視化中社團對比、多層分解顯示等需求，工具實現了基于同一數據的多視圖方法，通過主窗口和一系列分窗口完成聯動操作，其中主窗口主要實現社團層次操作，分窗口主要實現社團內部結構觀察。主要功能包括：

1）主窗口采用形狀和節點大小對社團和節點進行區分，節點為圓形，社團為正六邊形，其面積與N成正比，N為該社團包含的節點數目。節點支持鼠標觸動等一系列操作，通過節點標簽展示該社團的核心節點和包含節點數目。

2）社團支持主窗口逐級展開和分窗口全部展開操作，有利于研究者觀察社團在整個網絡的外部關系信息和該社團的內部結構信息，實現了整體和局部的結合。

3）整個網絡支持全局操作，可以通過網絡社團布局得到網絡整體結構，也可以通過全局展開觀察網絡的細節分布和部分節點的具體特征。

3 實驗分析

為了驗證本文算法，本章使用LFR（LANCICHINETIFORTUNATORADICCHI）基準網絡數據集[16]對本文社團劃分算法和自包含GN算法[14]進行比較驗證，并使用2015年中國可視化與可視分析大會中舉辦的數據可視分析挑戰賽的比賽數據（http：//chinavis.tju.edu.cn/sources/data）對可視化算法和工具進行測試。

3.1 數據準備

LFR基準網絡數據集是當前社團研究中最常使用的模擬數據集，數據集主要包含以下重要參數：節點度分布參數N、最小社團節點數cmin、最大社團節點數cmax和混合參數mp，mp取值為0～1，參數越大表明社團發現越困難。本節參數設置如下：N=5000，cmin=5，cmax=5000，mp=0.1，0.2，0.3，0.4，0.5。

可視化競賽網絡數據由一家互聯網公司提供，數據內容包括TCP流的時間、源IP、目的IP、協議類型、目的端口、上行字節數和下行字節數7個維度。數據為該公司在某段時間的正常TCP flow日志數據，該公司希望找出網絡的拓撲結構，以便對網絡進行改進。

對該數據進行初步統計表明，該數據集節點數目眾多、網絡活動頻繁，以2015年4月25日8：00至12：00的數據記錄為例，共175706行TCP flow記錄，包含10517個不同的IP地址，是一個典型的大規模網絡。

實現結構可視化的關鍵是IP間的關聯及其關聯程度，本文利用字節數定義IP之間連邊的權重Auw，不同的IP作為網絡節點，根據IP間的數據傳輸和連接情況，使用MSNV工具對整個網絡的結構進行可視化。

3.2 社團算法比較驗證

實驗準確率為節點劃分正確數與節點總數之比。由圖4可以看出，本文的社團劃分算法在準確率和網絡模塊度Q值上均優于自包含GN算法，表明該算法具有較好的劃分效果。仿真實驗中，該算法的社團劃分時間為37～39ms，而自包含GN算法劃分時間為103ms，表明該算法在運算效率上優于自包含GN算法。仿真實驗機器參數如下：處理器i5 4200Hz、內存16GB、顯卡NVIDIA GTX850M。

3.3 可視化方法效果分析

采用本文的基于社團劃分的多層次大規模網絡結構可視化方法對案例網絡數據進行可視化，采用終極劃分策略，實驗一共迭代4次形成最終結果，得到最大模塊度Q=0.5899>0.3，該網絡具有明顯的社團結構。

網絡由22個相對獨立的社團構成，最大的社團以10.59.21.10為核心，共包含9637個節點，占整個網絡節點數的91.63%，該社團與標簽為10.73.26.141和10.64.223.132社團有連接，是整個網絡的主體社團。其他社團之間相互獨立，網絡整體結構是分離的，社團的規模如表1所示。

將最大的社團逐級展開可以觀察到該社團主要由12個子社團構成，呈星形結構，如圖5（a）所示，其中標簽為10.59.21.10的子社團與所有社團都有聯系，可以判定此社團包含整個網絡的核心節點。將標簽為10.59.21.10的子社團再次展開得到更接近星形結構的拓撲圖，如圖5（b）所示，標簽為10.59.21.10依然是二級子社團核心，對所有二級子社團都有輻射，可以確定10.59.21.10社團是整個網絡至關重要的社團。

圖5（a）中，標簽為10.59.212.16、10.66.206.174、10.66.148.181的子社團和10.59.21.10子社團互相連接，連線較粗表明這4個子社團之間聯系較為緊密，4個子社團包含8069個節點，占主體社團的83.73%，是最大社團的主體。將這4個社團同時展開至下一級可得到如圖6所示的結構（此處為了便于觀察只展示關鍵部分），圖中的7個二級子社團互相連接，其網絡吞吐量在整個網絡中所占比例都在8%以上，其他二級子社團都小于1.6%，可以確定這7個二級子社團是整個網絡最重要的部分，對網絡起支配作用。

對小社團逐個進行分窗口展開可以發現該網絡除了主體部分，其他社團拓撲結構大多為星形結構，如圖7所示，其中心節點是該社團的關鍵節點，如10.59.45.221、10.93.26.48、10.59.22.149等。

4 結語

本文針對大規模網絡結構可視化問題提出了一種基于社團劃分的多層次網絡結構可視化方法。該方法通過基于貪婪算法的社團劃分將網絡劃分為層次分明的若干社團；在社團的層次上對整個網絡的結構進行可視化布局，并改進經典力導引算法實現了多層次節點在同一界面的有效分層布局；在可視化工具上采用了主副窗口和Overview + Detail等交互探索，兼顧網絡整體結構、社團間聯系以及該網絡局部細節的需求。通過LFR基準網絡數據集對社團劃分和自包含GN算法進行仿真對比說明該方法在大規模網絡社團劃分上有著明顯優勢，最后將此方法應用在某互聯網公司的計算機網絡數據可視化中并取得了良好的可視化效果。

參考文獻：

[1]CHAN D SM， CHUA K S， LECKIE C. Visualization of powerlaw network topologies[C]// Proceedings of the 11th IEEE International Conference on Networks. Piscataway， NJ： IEEE， 2003： 69-74.

[2]AGAPITO G， GUZZI P H， CANNATARO M. Visualization of protein interaction networks： problems and solutions[J]. BMC Bioinformatics， 2013， 14（S1）： 1-30.

[3]PALLA J， VICESEK G， VICSEK T. Uncovering the overlapping community structure of complex network in nature and society[J]. Nature， 2005， 435（7043）：814-818.

[4]JAEWON Y， JURE L. Defining and evaluating network communities based on groundtruth[J]. Knowledge and Information Systems， 2015， 42（1）： 181-213.

[5]GIVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）：7821-7826.

[6]解， 汪小凡. 復雜網絡中的社團結構分析算法研究綜述[J]. 復雜系統與復雜性科學， 2005， 2（3）： 1-12.（XIE Z， WANG X F. An overview of algorithms for analyzing community structure in complex networks[J]. Complex Systems and Complexity Science， 2005， 2（3）： 1-12.）

[7]AARON C， NEWMAN M E J， CRISTOPHER M. Finding community structure in very large network[J]. Physical Review E， 2004， 70（6）：264-277.

[8]CAFIERI S， COSTA A， HANSEN P. Reformulation of a model for hierarchical divisive graph modularity maximization[J]. Annals of Operations Research， 2014， 222（1）： 213-226.

[9]LIANG G， LUKE X L. TreeNetViz： revealing patterns of networks over tree structures[J]. IEEE Transactions on Visualization & Computer Graphics， 2011， 17（12）：2449-2458.

[10]ZHAO J， CHEVELIER F， COLLINS C， et al. Facilitating discourse analysis with interactive visualization[J]. IEEE Transactions on Visualization & Computer Graphics， 2012， 18（12）：2639-2648.

[11]EADES P A. A heuristics for graph drawing[J]. Congressus Numerantium， 1984， 42： 149-160.

[12]KAMADA T， KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters， 1989， 31（1）：7-15.

[13]胡華全. 基于時變特征的天基網絡可視化方法研究[D]. 長沙：國防科學技術大學， 2014： 48. （HU H Q. Research on visualization method of spacebased networks based on timevarying characteristic[D]. Changsha： National University of Defense Technology， 2014：48.）

[14]RADICCHI F， CASTELLANE C， CECCONI F， et al. Defining and identifying communities in network[J]. Proceedings of the National Academy of Sciences， 2004， 101（9）： 2658-2663.

[15]NEWMAN M E J. Fast algorithm for detecting community structure in network[J]. Physical Review E， 2004， 69（6）： 066133.

[16]ANDREA L， SANTO F， FILIPPO R. Benchmark graphs for testing community detection algorithms[J]. Physical Review E， 2008， 78（4）： 046110.