王賢剛 姚中華 宋漢辰

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

關(guān)鍵詞：大規(guī)模網(wǎng)絡(luò)；多層次；可視化；社團(tuán)劃分；力導(dǎo)引算法

中圖分類(lèi)號(hào)：TP393.02 文獻(xiàn)標(biāo)志碼：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 引言

大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)規(guī)模龐大、拓?fù)浣Y(jié)構(gòu)復(fù)雜，直接對(duì)其進(jìn)行可視化會(huì)導(dǎo)致顯示重疊、層次信息難以觀察，無(wú)法有效降低網(wǎng)絡(luò)分析人員的負(fù)擔(dān)。為解決這一問(wèn)題，學(xué)者們提出了很多策略和方法，對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行層次劃分和改進(jìn)布局算法是提高網(wǎng)絡(luò)可視化質(zhì)量的有效途徑。

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

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

針對(duì)上述問(wèn)題，本文提出基于社團(tuán)劃分的多層次大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)可視化方法，方法利用社團(tuán)劃分算法將整個(gè)網(wǎng)絡(luò)劃分為多個(gè)層次的社團(tuán)，并對(duì)社團(tuán)集合采用改進(jìn)的力導(dǎo)引布局算法進(jìn)行布局。本文的社團(tuán)劃分與可視化方法主要有以下特點(diǎn)：1）利用社團(tuán)劃分應(yīng)對(duì)大型網(wǎng)絡(luò)的結(jié)構(gòu)顯示問(wèn)題。將大規(guī)模節(jié)點(diǎn)轉(zhuǎn)化為有限社團(tuán)，宏觀拓?fù)浣Y(jié)構(gòu)清晰。2）利用改進(jìn)的力導(dǎo)引算法布局社團(tuán)節(jié)點(diǎn)。基于額外電荷量的方法使布局層次分明，社團(tuán)規(guī)模從內(nèi)到外遞增，便于區(qū)分。3）采用主副窗口協(xié)同交互，支持社團(tuán)逐級(jí)展開(kāi)和跳級(jí)展開(kāi)，在顯示上同時(shí)兼顧網(wǎng)絡(luò)整體結(jié)構(gòu)和局部細(xì)節(jié)、社團(tuán)外部聯(lián)系和內(nèi)部結(jié)構(gòu)。

1 基于社團(tuán)聚類(lèi)的網(wǎng)絡(luò)結(jié)構(gòu)層次劃分算法

社團(tuán)劃分是分析網(wǎng)絡(luò)結(jié)構(gòu)和功能的有效方法。在真實(shí)網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)都與其他節(jié)點(diǎn)產(chǎn)生作用，根據(jù)作用的類(lèi)別和強(qiáng)弱可將網(wǎng)絡(luò)劃分為多個(gè)聚合團(tuán)，每個(gè)聚合團(tuán)內(nèi)節(jié)點(diǎn)互相作用的緊密程度顯著大于團(tuán)間的作用，這些聚合團(tuán)被稱(chēng)為社團(tuán)[5]。大規(guī)模網(wǎng)絡(luò)可以認(rèn)為是由若干個(gè)社團(tuán)構(gòu)成的，社團(tuán)間的結(jié)構(gòu)可以被看成網(wǎng)絡(luò)的整體結(jié)構(gòu)。通過(guò)社團(tuán)劃分，可以更加有效地對(duì)大規(guī)模網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行觀察和分析。

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

Q的取值在0～1，大量實(shí)驗(yàn)表明，Q值一般不可能接近1[6]?，F(xiàn)在學(xué)者認(rèn)為，一個(gè)網(wǎng)絡(luò)的模塊度Q值大于0.3即可說(shuō)明該網(wǎng)絡(luò)具有明顯的社團(tuán)結(jié)構(gòu)[6]。

由于網(wǎng)絡(luò)涉及節(jié)點(diǎn)和邊數(shù)目較大，為提高效率，本文在社團(tuán)劃分之前先對(duì)節(jié)點(diǎn)進(jìn)行分簇，然后再對(duì)這些簇進(jìn)行社團(tuán)劃分，簇劃分依據(jù)為簇內(nèi)節(jié)點(diǎn)可達(dá)，簇間無(wú)連邊。合并兩個(gè)無(wú)關(guān)聯(lián)的簇不會(huì)改變網(wǎng)絡(luò)模塊度，只在簇內(nèi)進(jìn)行社團(tuán)劃分可以避免每次聚類(lèi)都要進(jìn)行全局遍歷。

本文社團(tuán)劃分過(guò)程分為貪婪搜索、遞進(jìn)聚合、終止檢查三個(gè)階段，社團(tuán)劃分算法流程如圖1所示。

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

遞進(jìn)聚合階段 將第一階段形成的社團(tuán)視為單個(gè)節(jié)點(diǎn)，社團(tuán)節(jié)點(diǎn)的位置為原社團(tuán)中所有節(jié)點(diǎn)的中心，社團(tuán)節(jié)點(diǎn)間連邊的權(quán)值為原社團(tuán)間連邊權(quán)值的和，并重新對(duì)式（2）中的A進(jìn)行計(jì)算。然后重復(fù)貪婪搜索過(guò)程，形成更高層次的社團(tuán)，逐次迭代得到不同層次的社團(tuán)。

終止檢查階段 每次迭代后計(jì)算當(dāng)前整個(gè)網(wǎng)絡(luò)模塊度QT，并與前一次結(jié)果作比較，當(dāng)QT≤QS或達(dá)到迭代次數(shù)時(shí)停止社團(tuán)劃分，以前一次劃分結(jié)果為最終結(jié)果。

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

2 多層次網(wǎng)絡(luò)結(jié)構(gòu)可視化方法

2.1 面向多層次網(wǎng)絡(luò)改進(jìn)的FDA布局算法

上述社團(tuán)劃分算法兼顧了網(wǎng)絡(luò)整體結(jié)構(gòu)和局部細(xì)節(jié)，但由于劃分層次結(jié)構(gòu)過(guò)多，還存在難以在同一界面有效顯示的問(wèn)題，且目前尚未發(fā)現(xiàn)對(duì)不同層次節(jié)點(diǎn)進(jìn)行統(tǒng)一布局的有效算法。力導(dǎo)引布局算法是一種對(duì)同質(zhì)節(jié)點(diǎn)布局有效的經(jīng)典算法，但無(wú)法分辨不同層次節(jié)點(diǎn)。本文提出了一種基于額外電荷量的力導(dǎo)引改進(jìn)算法，對(duì)不同層次進(jìn)行區(qū)分布局。

算法的基本思想為：在對(duì)原有節(jié)點(diǎn)之間的引力和斥力不造成影響的前提下，通過(guò)額外電荷量對(duì)節(jié)點(diǎn)的布局位置產(chǎn)生影響。例如在窗口的中心固定一個(gè)單位正電荷，同時(shí)在不同社團(tuán)中根據(jù)層次的高低附加額外的正電荷量，層次越高的電荷量越大，從而驅(qū)動(dòng)不同層次的社團(tuán)在界面中呈圓環(huán)狀依次展開(kāi)，越靠近中心的層次等級(jí)越低，反之越高。

按照改進(jìn)的力導(dǎo)引算法實(shí)現(xiàn)的混合層次節(jié)點(diǎn)布局效果如圖3所示。由于原始節(jié)點(diǎn)不受額外電荷斥力影響，展開(kāi)的社團(tuán)可以在中心區(qū)域按照經(jīng)典FDA進(jìn)行布局，其局部結(jié)構(gòu)細(xì)節(jié)得以展示；單層次社團(tuán)中L=Lmin，由式（4）可得社團(tuán)不受電荷斥力影響；多層次社團(tuán)中除了原始節(jié)點(diǎn)，其余不同層次的社團(tuán)受到電荷斥力影響，布局呈環(huán)狀結(jié)構(gòu)，低層社團(tuán)和高層社團(tuán)從內(nèi)到外依次展開(kāi)。

2.2 面向多層次網(wǎng)絡(luò)的交互設(shè)計(jì)

以社團(tuán)劃分和多層次布局算法為基礎(chǔ)，本文開(kāi)發(fā)了多層次網(wǎng)絡(luò)可視化工具M(jìn)SNV（Multilayer Structure Visualization of Network），針對(duì)社團(tuán)可視化中社團(tuán)對(duì)比、多層分解顯示等需求，工具實(shí)現(xiàn)了基于同一數(shù)據(jù)的多視圖方法，通過(guò)主窗口和一系列分窗口完成聯(lián)動(dòng)操作，其中主窗口主要實(shí)現(xiàn)社團(tuán)層次操作，分窗口主要實(shí)現(xiàn)社團(tuán)內(nèi)部結(jié)構(gòu)觀察。主要功能包括：

1）主窗口采用形狀和節(jié)點(diǎn)大小對(duì)社團(tuán)和節(jié)點(diǎn)進(jìn)行區(qū)分，節(jié)點(diǎn)為圓形，社團(tuán)為正六邊形，其面積與N成正比，N為該社團(tuán)包含的節(jié)點(diǎn)數(shù)目。節(jié)點(diǎn)支持鼠標(biāo)觸動(dòng)等一系列操作，通過(guò)節(jié)點(diǎn)標(biāo)簽展示該社團(tuán)的核心節(jié)點(diǎn)和包含節(jié)點(diǎn)數(shù)目。

2）社團(tuán)支持主窗口逐級(jí)展開(kāi)和分窗口全部展開(kāi)操作，有利于研究者觀察社團(tuán)在整個(gè)網(wǎng)絡(luò)的外部關(guān)系信息和該社團(tuán)的內(nèi)部結(jié)構(gòu)信息，實(shí)現(xiàn)了整體和局部的結(jié)合。

3）整個(gè)網(wǎng)絡(luò)支持全局操作，可以通過(guò)網(wǎng)絡(luò)社團(tuán)布局得到網(wǎng)絡(luò)整體結(jié)構(gòu)，也可以通過(guò)全局展開(kāi)觀察網(wǎng)絡(luò)的細(xì)節(jié)分布和部分節(jié)點(diǎn)的具體特征。

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文算法，本章使用LFR（LANCICHINETIFORTUNATORADICCHI）基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集[16]對(duì)本文社團(tuán)劃分算法和自包含GN算法[14]進(jìn)行比較驗(yàn)證，并使用2015年中國(guó)可視化與可視分析大會(huì)中舉辦的數(shù)據(jù)可視分析挑戰(zhàn)賽的比賽數(shù)據(jù)（http：//chinavis.tju.edu.cn/sources/data）對(duì)可視化算法和工具進(jìn)行測(cè)試。

3.1 數(shù)據(jù)準(zhǔn)備

LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集是當(dāng)前社團(tuán)研究中最常使用的模擬數(shù)據(jù)集，數(shù)據(jù)集主要包含以下重要參數(shù)：節(jié)點(diǎn)度分布參數(shù)N、最小社團(tuán)節(jié)點(diǎn)數(shù)cmin、最大社團(tuán)節(jié)點(diǎn)數(shù)cmax和混合參數(shù)mp，mp取值為0～1，參數(shù)越大表明社團(tuán)發(fā)現(xiàn)越困難。本節(jié)參數(shù)設(shè)置如下：N=5000，cmin=5，cmax=5000，mp=0.1，0.2，0.3，0.4，0.5。

可視化競(jìng)賽網(wǎng)絡(luò)數(shù)據(jù)由一家互聯(lián)網(wǎng)公司提供，數(shù)據(jù)內(nèi)容包括TCP流的時(shí)間、源IP、目的IP、協(xié)議類(lèi)型、目的端口、上行字節(jié)數(shù)和下行字節(jié)數(shù)7個(gè)維度。數(shù)據(jù)為該公司在某段時(shí)間的正常TCP flow日志數(shù)據(jù)，該公司希望找出網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以便對(duì)網(wǎng)絡(luò)進(jìn)行改進(jìn)。

對(duì)該數(shù)據(jù)進(jìn)行初步統(tǒng)計(jì)表明，該數(shù)據(jù)集節(jié)點(diǎn)數(shù)目眾多、網(wǎng)絡(luò)活動(dòng)頻繁，以2015年4月25日8：00至12：00的數(shù)據(jù)記錄為例，共175706行TCP flow記錄，包含10517個(gè)不同的IP地址，是一個(gè)典型的大規(guī)模網(wǎng)絡(luò)。

實(shí)現(xiàn)結(jié)構(gòu)可視化的關(guān)鍵是IP間的關(guān)聯(lián)及其關(guān)聯(lián)程度，本文利用字節(jié)數(shù)定義IP之間連邊的權(quán)重Auw，不同的IP作為網(wǎng)絡(luò)節(jié)點(diǎn)，根據(jù)IP間的數(shù)據(jù)傳輸和連接情況，使用MSNV工具對(duì)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行可視化。

3.2 社團(tuán)算法比較驗(yàn)證

實(shí)驗(yàn)準(zhǔn)確率為節(jié)點(diǎn)劃分正確數(shù)與節(jié)點(diǎn)總數(shù)之比。由圖4可以看出，本文的社團(tuán)劃分算法在準(zhǔn)確率和網(wǎng)絡(luò)模塊度Q值上均優(yōu)于自包含GN算法，表明該算法具有較好的劃分效果。仿真實(shí)驗(yàn)中，該算法的社團(tuán)劃分時(shí)間為37～39ms，而自包含GN算法劃分時(shí)間為103ms，表明該算法在運(yùn)算效率上優(yōu)于自包含GN算法。仿真實(shí)驗(yàn)機(jī)器參數(shù)如下：處理器i5 4200Hz、內(nèi)存16GB、顯卡NVIDIA GTX850M。

3.3 可視化方法效果分析

采用本文的基于社團(tuán)劃分的多層次大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)可視化方法對(duì)案例網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行可視化，采用終極劃分策略，實(shí)驗(yàn)一共迭代4次形成最終結(jié)果，得到最大模塊度Q=0.5899>0.3，該網(wǎng)絡(luò)具有明顯的社團(tuán)結(jié)構(gòu)。

網(wǎng)絡(luò)由22個(gè)相對(duì)獨(dú)立的社團(tuán)構(gòu)成，最大的社團(tuán)以10.59.21.10為核心，共包含9637個(gè)節(jié)點(diǎn)，占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的91.63%，該社團(tuán)與標(biāo)簽為10.73.26.141和10.64.223.132社團(tuán)有連接，是整個(gè)網(wǎng)絡(luò)的主體社團(tuán)。其他社團(tuán)之間相互獨(dú)立，網(wǎng)絡(luò)整體結(jié)構(gòu)是分離的，社團(tuán)的規(guī)模如表1所示。

將最大的社團(tuán)逐級(jí)展開(kāi)可以觀察到該社團(tuán)主要由12個(gè)子社團(tuán)構(gòu)成，呈星形結(jié)構(gòu)，如圖5（a）所示，其中標(biāo)簽為10.59.21.10的子社團(tuán)與所有社團(tuán)都有聯(lián)系，可以判定此社團(tuán)包含整個(gè)網(wǎng)絡(luò)的核心節(jié)點(diǎn)。將標(biāo)簽為10.59.21.10的子社團(tuán)再次展開(kāi)得到更接近星形結(jié)構(gòu)的拓?fù)鋱D，如圖5（b）所示，標(biāo)簽為10.59.21.10依然是二級(jí)子社團(tuán)核心，對(duì)所有二級(jí)子社團(tuán)都有輻射，可以確定10.59.21.10社團(tuán)是整個(gè)網(wǎng)絡(luò)至關(guān)重要的社團(tuán)。

圖5（a）中，標(biāo)簽為10.59.212.16、10.66.206.174、10.66.148.181的子社團(tuán)和10.59.21.10子社團(tuán)互相連接，連線較粗表明這4個(gè)子社團(tuán)之間聯(lián)系較為緊密，4個(gè)子社團(tuán)包含8069個(gè)節(jié)點(diǎn)，占主體社團(tuán)的83.73%，是最大社團(tuán)的主體。將這4個(gè)社團(tuán)同時(shí)展開(kāi)至下一級(jí)可得到如圖6所示的結(jié)構(gòu)（此處為了便于觀察只展示關(guān)鍵部分），圖中的7個(gè)二級(jí)子社團(tuán)互相連接，其網(wǎng)絡(luò)吞吐量在整個(gè)網(wǎng)絡(luò)中所占比例都在8%以上，其他二級(jí)子社團(tuán)都小于1.6%，可以確定這7個(gè)二級(jí)子社團(tuán)是整個(gè)網(wǎng)絡(luò)最重要的部分，對(duì)網(wǎng)絡(luò)起支配作用。

對(duì)小社團(tuán)逐個(gè)進(jìn)行分窗口展開(kāi)可以發(fā)現(xiàn)該網(wǎng)絡(luò)除了主體部分，其他社團(tuán)拓?fù)浣Y(jié)構(gòu)大多為星形結(jié)構(gòu)，如圖7所示，其中心節(jié)點(diǎn)是該社團(tuán)的關(guān)鍵節(jié)點(diǎn)，如10.59.45.221、10.93.26.48、10.59.22.149等。

4 結(jié)語(yǔ)

本文針對(duì)大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)可視化問(wèn)題提出了一種基于社團(tuán)劃分的多層次網(wǎng)絡(luò)結(jié)構(gòu)可視化方法。該方法通過(guò)基于貪婪算法的社團(tuán)劃分將網(wǎng)絡(luò)劃分為層次分明的若干社團(tuán)；在社團(tuán)的層次上對(duì)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行可視化布局，并改進(jìn)經(jīng)典力導(dǎo)引算法實(shí)現(xiàn)了多層次節(jié)點(diǎn)在同一界面的有效分層布局；在可視化工具上采用了主副窗口和Overview + Detail等交互探索，兼顧網(wǎng)絡(luò)整體結(jié)構(gòu)、社團(tuán)間聯(lián)系以及該網(wǎng)絡(luò)局部細(xì)節(jié)的需求。通過(guò)LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集對(duì)社團(tuán)劃分和自包含GN算法進(jìn)行仿真對(duì)比說(shuō)明該方法在大規(guī)模網(wǎng)絡(luò)社團(tuán)劃分上有著明顯優(yōu)勢(shì)，最后將此方法應(yīng)用在某互聯(lián)網(wǎng)公司的計(jì)算機(jī)網(wǎng)絡(luò)數(shù)據(jù)可視化中并取得了良好的可視化效果。

參考文獻(xiàn)：

[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]解， 汪小凡. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)分析算法研究綜述[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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]胡華全. 基于時(shí)變特征的天基網(wǎng)絡(luò)可視化方法研究[D]. 長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)， 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.