吳玲達，張喜濤，2，*，孟祥利

（1.航天工程大學(xué) 航天信息學(xué)院，北京101416； 2.航天工程大學(xué) 航天指揮系，北京101416）

網(wǎng)絡(luò)可視化的目的是輔助用戶感知網(wǎng)絡(luò)結(jié)構(gòu)，理解和探索隱藏在網(wǎng)絡(luò)數(shù)據(jù)內(nèi)部的規(guī)律、模式等［1-2］。然而，如果將所有節(jié)點和連邊的細節(jié)信息完全展示在有限尺寸的屏幕中，會導(dǎo)致以下問題：①受屏幕尺寸限制，對于具有大量節(jié)點和高密度連邊的大規(guī)模網(wǎng)絡(luò)可視化來說，用戶會陷入混亂重疊的節(jié)點-連接圖中，難以識別和感知網(wǎng)絡(luò)的整體結(jié)構(gòu)，更不能引導(dǎo)用戶發(fā)現(xiàn)感興趣的元素；②大規(guī)模的數(shù)據(jù)量必然帶來更大的計算壓力，對算法和硬件都會有更高的要求。低效、耗時的網(wǎng)絡(luò)可視化就失去了應(yīng)有的意義。

因此，為了達到有效展示信息和輔助用戶感知網(wǎng)絡(luò)整體結(jié)構(gòu)的目的，必須對大規(guī)模網(wǎng)絡(luò)進行一定的縮減處理，以降低用戶的感知復(fù)雜度和布局過程的計算復(fù)雜度。根據(jù)縮減目的，可將網(wǎng)絡(luò)縮減處理方法分為3類：過濾、抽樣和壓縮。

過濾就是通過網(wǎng)絡(luò)中節(jié)點或連邊的單個屬性或多個屬性的組合篩選滿足條件的節(jié)點和連邊，從而降低節(jié)點數(shù)量和連邊密度。過濾技術(shù)更多的是在對網(wǎng)絡(luò)結(jié)構(gòu)有了一定了解的基礎(chǔ)上，對網(wǎng)絡(luò)數(shù)據(jù)進行的進一步細化探索，如根據(jù)節(jié)點的度、介數(shù)中心性、中介中心性及連邊的權(quán)重等屬性，有針對性地將滿足條件的元素篩選并顯示在屏幕中。

抽樣是根據(jù)一定的抽樣策略篩選有代表性的節(jié)點和連邊，用盡可能少的節(jié)點和連邊最大限度地反映原始網(wǎng)絡(luò)的結(jié)構(gòu)特征。常用的抽樣策略包括隨機選點、隨機選邊、隨機游走和基于拓撲分層模型的抽樣策略等［3-4］。

相對于過濾和抽樣，壓縮則是通過把具有一定相似性的節(jié)點或連邊聚合，并采用新的節(jié)點來代替聚集，在降低節(jié)點規(guī)模的同時還能夠保證網(wǎng)絡(luò)的完整性和展示網(wǎng)絡(luò)的子圖構(gòu)成等特征，更有助于用戶從中觀尺度感知網(wǎng)絡(luò)整體結(jié)構(gòu)［5-6］。

本文以有效展示網(wǎng)絡(luò)的中觀尺度結(jié)構(gòu)特征為目標開展網(wǎng)絡(luò)可視化壓縮布局方法研究，將力導(dǎo)引布局算法與網(wǎng)絡(luò)社團結(jié)構(gòu)特征相結(jié)合，提出了一種基于社團結(jié)構(gòu)節(jié)點重要性的網(wǎng)絡(luò)可視化壓縮布局方法。將基于拓撲勢的社團結(jié)構(gòu)壓縮方法應(yīng)用于網(wǎng)絡(luò)拓撲結(jié)構(gòu)可視化，通過原始網(wǎng)絡(luò)的社團構(gòu)成和社團內(nèi)部結(jié)構(gòu)等中觀尺度結(jié)構(gòu)的清晰展示，輔助用戶分析社團和重要節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)中的位置和作用。

1 相關(guān)工作

在網(wǎng)絡(luò)可視化壓縮布局方法中，由于彈簧模型［7］具有簡潔高效和易于理解等優(yōu)勢，國內(nèi)外學(xué)者基于彈簧模型對網(wǎng)絡(luò)可視化壓縮布局方法進行了大量探索。該方法將整個網(wǎng)絡(luò)模擬為彈簧系統(tǒng)，通過計算節(jié)點受到的彈力控制節(jié)點間的距離最終達到節(jié)點的受力平衡。KK（Kamada-Kawai）算法［8］在彈簧模型的基礎(chǔ)上引入胡克定律，根據(jù)節(jié)點受力狀態(tài)計算系統(tǒng)能量，將節(jié)點最優(yōu)布局問題轉(zhuǎn)化為系統(tǒng)能量最小化的求解問題，使布局過程的收斂速度有了明顯的增加。Davidson和Harel［9］在DH（Davidson-Harel）算法中考慮了節(jié)點位置、連邊長度和連邊交叉等多種美學(xué)標準的約束來構(gòu)建能量函數(shù)，通過能量函數(shù)模型參數(shù)可達到不同的布局效果。FR（Fruchterman-Reingold）算法［10］將節(jié)點建模為物理系統(tǒng)中的帶電粒子，將粒子間的電荷斥力引入彈簧模型，粒子間距越小斥力越大，在一定程度上降低了密集節(jié)點的重疊現(xiàn)象，為使算法快速收斂，通過引入“冷卻函數(shù)”，采用模擬退火算法，逐步降低節(jié)點移動步長，使系統(tǒng)能量快速減小，從而實現(xiàn)快速布局的目標［11-12］。

相比于KK算法和DH算法，F(xiàn)R算法在大多數(shù)網(wǎng)絡(luò)數(shù)據(jù)的可視化應(yīng)用中具有更好的對稱性和聚類布局效果，繪制結(jié)果更加符合美學(xué)標準，得到廣泛的應(yīng)用。

國內(nèi)外有關(guān)網(wǎng)絡(luò)壓縮的研究主要是基于節(jié)點或者連邊重要性進行壓縮。Gilbert和Levchenko［5］基于節(jié)點的重要性提出了網(wǎng)絡(luò)壓縮的一般框架，該框架指出，通過刪除非重要節(jié)點及與之關(guān)聯(lián)的連邊可以達到壓縮網(wǎng)絡(luò)拓撲的目的。王曉華等［13］基于幾何多尺度分析，提出了網(wǎng)絡(luò)數(shù)據(jù)和結(jié)構(gòu)的稀疏表示方式，有效幫助人們憑借盡可能少的信息來分析網(wǎng)絡(luò)。李甜甜等［14］基于復(fù)雜網(wǎng)絡(luò)中的k-core概念劃分網(wǎng)絡(luò)節(jié)點，利用力導(dǎo)引布局算法實現(xiàn)壓縮后的大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的布局顯示。上述方法基于網(wǎng)絡(luò)全局對節(jié)點的重要性進行評估，選擇重要節(jié)點作為網(wǎng)絡(luò)整體結(jié)構(gòu)的代表節(jié)點，同時壓縮非重要節(jié)點，最終實現(xiàn)網(wǎng)絡(luò)壓縮的目的。這類方法從節(jié)點尺度（微觀尺度）上保留了網(wǎng)絡(luò)的核心結(jié)構(gòu)，但是忽略了網(wǎng)絡(luò)的社團結(jié)構(gòu)，不能從中觀尺度展示網(wǎng)絡(luò)的結(jié)構(gòu)特征。

基于數(shù)據(jù)場理論，文獻［15］通過計算節(jié)點的拓撲勢刻畫了節(jié)點在網(wǎng)絡(luò)中受自身和鄰居節(jié)點的影響多具有的勢值，能夠更加真實地描述節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)成中的重要性。肖俐平等［15］和王戩［16］將其分別應(yīng)用于多種真實網(wǎng)絡(luò)數(shù)據(jù)，并于基于度、介數(shù)和PageRank等典型的節(jié)點重要性測度指標進行對比，指出拓撲勢在考慮節(jié)點度重要性的同時，還能突出節(jié)點在網(wǎng)絡(luò)中位置的差異性，在反映節(jié)點重要性方面更加精細和真實。

類似地，在同一社團結(jié)構(gòu)中，不同節(jié)點對社團結(jié)構(gòu)構(gòu)成的貢獻度不盡相同，度值越大并且離社團中心點越近的節(jié)點往往比其他節(jié)點更重要。因此，本文考慮根據(jù)節(jié)點的度和節(jié)點之間的最短路徑長度確定節(jié)點在社團結(jié)構(gòu)中的位置，將基于拓撲勢的節(jié)點重要性評估應(yīng)用于社團結(jié)構(gòu)，通過選擇社團結(jié)構(gòu)中節(jié)點重要性高的節(jié)點作為社團結(jié)構(gòu)代表節(jié)點，實現(xiàn)網(wǎng)絡(luò)社團結(jié)構(gòu)壓縮。

2 網(wǎng)絡(luò)可視化壓縮布局方法

2.1 多粒度社團結(jié)構(gòu)探測

相比于其他社團結(jié)構(gòu)探測算法，Louvain算法的運算速度更快，可以快速處理具有數(shù)以億計節(jié)點的網(wǎng)絡(luò)，另外基于層次聚類可以輸出不同粒度的社團結(jié)構(gòu)劃分結(jié)果。因此，本文采用Louvain算法實現(xiàn)多粒度社團結(jié)構(gòu)探測。

模塊度是刻畫網(wǎng)絡(luò)中社團劃分質(zhì)量的重要指標之一，可通過如下公式計算：

式中：m為網(wǎng)絡(luò)中的連邊總數(shù)；Aij為節(jié)點對（vi，vj）連邊的權(quán)值；ki為節(jié)點度；cvi為節(jié)點vi隸屬的社團；δ（cvi，cvj）為狄拉克函數(shù)，如果節(jié)點隸屬于同一社團，則為1，否則為0。

基于模塊度優(yōu)化的社團結(jié)構(gòu)探測算法屬于凝聚算法的一種，其通過優(yōu)化模塊度增益函數(shù)不斷地凝聚節(jié)點，最終獲得社團結(jié)構(gòu)劃分結(jié)果。文獻［17］將模塊度增量函數(shù)定義為

式中：Cin為社團C中所有內(nèi)部邊權(quán)重的總和；Cout為所有與社團C中節(jié)點鄰接的邊權(quán)重總和；Ki為所有鄰接節(jié)點i的邊權(quán)重的總和；Ki，in為所有從節(jié)點i與社團C中節(jié)點鄰接的邊權(quán)重總和；M 為網(wǎng)絡(luò)中所有邊的權(quán)重之和。

如圖1所示，Louvain算法主要分為2個階段。首先，初始化每個節(jié)點為一個社團，不斷遍歷網(wǎng)絡(luò)中的所有節(jié)點，計算該點加入到各個社團產(chǎn)生的模塊度增量，如果模塊度增量大于0，則從這些大于0的模塊度增量所對應(yīng)的社團中選出對應(yīng)模塊增量最大的社團，將該點與之合并。重復(fù)上述過程，直到網(wǎng)絡(luò)中社團兩兩之間不再合并為止。然后，基于第1層社團劃分結(jié)果，將每個社團抽象為“節(jié)點”，并構(gòu)建新的網(wǎng)絡(luò)，新節(jié)點之間的權(quán)重是原始網(wǎng)絡(luò)中社團之間的權(quán)重。重復(fù)上一階段的過程，直到社團之間不能再合并為止。

圖1 Louvain算法示意圖Fig.1 Schematic diagram of Louvain algorithm

2.2 基于拓撲勢的社團結(jié)構(gòu)節(jié)點重要性評估

節(jié)點拓撲勢的大小描述了網(wǎng)絡(luò)拓撲中的某個節(jié)點受自身和近鄰節(jié)點共同影響所具有的勢值。類似地，對于一個給定的社團C=（VC，EC）（VC為社團C中的所有節(jié)點集合，EC為社團C中的所有連邊集合），社團中任意一個節(jié)點的拓撲勢的計算公式為

從式（1）可知，社團中任一節(jié)點的勢實際上等于社團內(nèi)其他所有節(jié)點對其作用力之和，并且作用力隨著到節(jié)點距離的增大而逐漸衰減。社團中某點周圍的節(jié)點越多，距離越短，則該節(jié)點的勢就越大。因此，可以判斷勢值最高的節(jié)點即為處于社團中心位置的節(jié)點，該節(jié)點可以看作是社團中心節(jié)點；反之，處于社團邊緣的節(jié)點往往具有的連邊較少，勢值相對較低。

根據(jù)節(jié)點的度和節(jié)點到社團中心節(jié)點的最短路徑長度確定的社團結(jié)構(gòu)中節(jié)點的拓撲位置反映了節(jié)點對社團結(jié)構(gòu)構(gòu)成的貢獻度大小。如圖2中左圖所示，通過計算節(jié)點在社團結(jié)構(gòu)中的勢來評估節(jié)點的重要性，根據(jù)重要性排序?qū)⑸鐖F內(nèi)部節(jié)點分為3類：①節(jié)點9最重要，是拓撲勢極值點，也是社團中心點，圖2中左圖用紅色標注，用VCA表示；②節(jié)點7，19，21，22，25，26，10，16對拓撲勢極值點影響較大，圖2中左圖用黃色標注，用VCB表示；③其余節(jié)點為邊緣節(jié)點，圖2中左圖采用灰色標注，用VCC表示。選擇社團中拓撲勢的極值點作為社團代表點，選擇對代表點拓撲勢貢獻大的節(jié)點作為相對重要節(jié)點。

圖2 社團節(jié)點分類與社團壓縮示意圖Fig.2 Schematic diagram of community node classification and community compression

2.3 壓縮布局算法

在社團結(jié)構(gòu)壓縮時，選擇盡可能少的節(jié)點最大限度地保持社區(qū)結(jié)構(gòu)。圖2中右圖為在社團節(jié)點分類基礎(chǔ)上對社團進行壓縮后的社團結(jié)構(gòu)。將社團代表點VCA和相對重要節(jié)點集合VCB作為社團結(jié)構(gòu)代表點集合V′CA。社團壓縮主要是為邊緣節(jié)點VCC設(shè)置替代節(jié)點，從而將邊緣節(jié)點與社團結(jié)構(gòu)代表點合并，壓縮到網(wǎng)絡(luò)中只留下社團結(jié)構(gòu)代表點。

對于vi∈VCC，用VN（vi）表示節(jié)點vi的鄰居節(jié)點集合，當(dāng)節(jié)點vi滿足式（2）時，將節(jié)點vi和社區(qū)結(jié)構(gòu)代表節(jié)點vj壓縮為一個節(jié)點，并將vj設(shè)置為vi的替代節(jié)點。

采用廣度優(yōu)先算法為VCC集合中的節(jié)點查找并設(shè)置替代節(jié)點，具體方法如算法1所示，其中IfReplaced（vi）標記節(jié)點vi是否被V′CA中的節(jié)點代替，用replace（vi）表示節(jié)點vi的代替點。

算法1 廣度優(yōu)先遍歷替代節(jié)點設(shè)置算法。

輸入：原始節(jié)點vi、鄰居節(jié)點集合VN（vi）、社團結(jié)構(gòu)代表點集合V′CA。

輸出：替代節(jié)點replace（vi）。

為VCC中的所有節(jié)點設(shè)置替代節(jié)點，生成新的社團結(jié)構(gòu)代表節(jié)點集合V′C。如算法1所示，VCC中的任一節(jié)點vi，其替代節(jié)點的設(shè)置可分為2步：

1）如果節(jié)點vi的鄰居節(jié)點vj屬于社團結(jié)構(gòu)代表點集合V′CA，則把節(jié)點vj設(shè)置為節(jié)點vi的替代節(jié)點。

2）如果節(jié)點vj不是社團結(jié)構(gòu)代表節(jié)點，則將節(jié)點vj的所有鄰居節(jié)點添加到訪問列表中，遍歷查找直到找到節(jié)點vi的替代節(jié)點。

在對所有社團中的所有邊緣節(jié)點進行壓縮處理后，首先，合并所有新的社團結(jié)構(gòu)代表點集合構(gòu)建新的網(wǎng)絡(luò)節(jié)點集V′；然后，遍歷原始網(wǎng)絡(luò)中的所有連邊，把連邊的端點用替代節(jié)點替換，刪除重復(fù)邊，得到壓縮網(wǎng)絡(luò)G′=（V′，E′）；最后，采用經(jīng)典的FR算法布局壓縮網(wǎng)絡(luò)中的節(jié)點，實現(xiàn)網(wǎng)絡(luò)可視化壓縮布局。

3 實驗結(jié)果與分析

本文選擇網(wǎng)絡(luò)社團分析領(lǐng)域3組標準數(shù)據(jù)集：dolphin、football及karat。其中，dolphin為海豚社會網(wǎng)絡(luò)，football為美國大學(xué)生足球聯(lián)賽社會網(wǎng)絡(luò)，karat為美國空手道俱樂部社會網(wǎng)絡(luò)。對應(yīng)網(wǎng)絡(luò)的節(jié)點數(shù)和連邊數(shù)如表1所示。

將本文方法的壓縮布局結(jié)果分別與基于節(jié)點度值（方法1）、PageRank（方法2）排序的網(wǎng)絡(luò)壓縮布局方法進行對比。首先，通過節(jié)點數(shù)、連邊數(shù)、平均聚類系數(shù)和社團數(shù)等指標的變化定量評估不同壓縮方法的壓縮效果；然后，通過對壓縮前后拓撲結(jié)構(gòu)的可視化布局效果對比，定性分析本文方法的優(yōu)勢。其中，節(jié)點數(shù)和連邊數(shù)的變化量表示網(wǎng)絡(luò)的壓縮規(guī)模；平均聚類系數(shù)的變化描述了網(wǎng)絡(luò)中節(jié)點間連接關(guān)系的緊密程度，平均聚類系數(shù)越大，節(jié)點連接關(guān)系越緊密；社團數(shù)的變化反映了壓縮網(wǎng)絡(luò)是否保留了原始網(wǎng)絡(luò)的社團構(gòu)成。

實驗中選擇的節(jié)點壓縮比為0.2，即方法1和方法2按照全網(wǎng)節(jié)點總數(shù)的20%篩選網(wǎng)絡(luò)代表節(jié)點，本文方法按照每個社團中節(jié)點總數(shù)的20%篩選社團結(jié)構(gòu)代表節(jié)點。

表1為不同方法的壓縮結(jié)果對比。可知，不同壓縮方法通過合并非重要節(jié)點，較大程度地降低了節(jié)點和連邊數(shù)量，實現(xiàn)了網(wǎng)絡(luò)壓縮的目的。

另外，壓縮網(wǎng)絡(luò)的平均聚類系數(shù)較壓縮前有較大程度的升高，也表明了上述3種壓縮方法都保留聯(lián)系比較緊密的重要節(jié)點，這些節(jié)點及其之間的連邊反映了網(wǎng)絡(luò)的骨架結(jié)構(gòu)。其中，基于節(jié)點度值（方法1）、PageRank（方法2）排序的壓縮網(wǎng)絡(luò)的平均聚類系數(shù)相對接近，且都大于本文方法。這是因為前2種方法雖然采用的節(jié)點重要性評估模型不同，節(jié)點重要性排序結(jié)果并不一樣，但對于整體網(wǎng)絡(luò)而言，重要節(jié)點都分布在排名靠前的區(qū)域。因此，基于網(wǎng)絡(luò)全局節(jié)點重要性的壓縮獲得了相同或基本相同的代表節(jié)點集合。而本文方法對不同社團結(jié)構(gòu)中的節(jié)點重要性分別排序，保留的節(jié)點是各個社團結(jié)構(gòu)中的重要節(jié)點，代表了各社團的內(nèi)部結(jié)構(gòu)。雖然本文方法中壓縮網(wǎng)絡(luò)的平均聚類系數(shù)相對較低，但是社團數(shù)量沒有減少，比較完整地保留了網(wǎng)絡(luò)的社團構(gòu)成，從中尺度上保留了網(wǎng)絡(luò)的整體結(jié)構(gòu)。而前2種方法都丟失了部分社團，造成網(wǎng)絡(luò)整體結(jié)構(gòu)的不完整。

圖3～圖5為分別采用上述3種方法對不同網(wǎng)絡(luò)進行可視化壓縮布局前后的效果圖。將不同方法的布局效果進行對比，可以看出本文方法的優(yōu)勢主要體現(xiàn)在以下2個方面：

1）基于社團結(jié)構(gòu)進行壓縮，能夠保留網(wǎng)絡(luò)的社團構(gòu)成，突出中觀尺度結(jié)構(gòu)特征。

圖3（b）、（c）、（d）分別為方法1、方法2和本文方法的dolphin壓縮網(wǎng)絡(luò)的布局結(jié)果，圖4（b）、（c）、（d）分別為方法1、方法2和本文方法的football壓縮網(wǎng)絡(luò)的布局結(jié)果。與圖3（a）和圖4（a）中的原始網(wǎng)絡(luò)布局結(jié)果對比，圖3（b）、（c）、（d）和圖4（b）、（c）、（d）中的節(jié)點數(shù)和連邊數(shù)都有較大程度的壓縮。圖3（a）和圖4（a）中的原始網(wǎng)絡(luò)受屏幕尺寸限制，節(jié)點較小，連邊密集，節(jié)點和連邊重疊交叉現(xiàn)象嚴重。在混亂重疊的視圖中，用戶難以感知網(wǎng)絡(luò)的整體結(jié)構(gòu)。而上述3種方法通過縮減節(jié)點和連邊規(guī)模，可以降低節(jié)點和連邊重疊覆蓋造成的視覺雜亂。但是，由于方法1（圖3（b）和圖4（b））和方法2（圖3（c）和圖4（c））基于全局結(jié)構(gòu)評估節(jié)點的重要性和選擇網(wǎng)絡(luò)代表節(jié)點，對節(jié)點數(shù)量較少或者連邊相對稀疏的社團沒有保留有效的代表節(jié)點。在壓縮過程中，這部分社團被壓縮合并，造成社團數(shù)量減少，無法準確展示原始網(wǎng)絡(luò)的社團構(gòu)成。而本文方法（圖3（d）和圖4（d））基于社團結(jié)構(gòu)進行壓縮，保證每個社團結(jié)構(gòu)都有代表節(jié)點，避免壓縮過程中的社團丟失現(xiàn)象，能夠反映網(wǎng)絡(luò)在社團尺度（中觀尺度）上的結(jié)構(gòu)特征。

表1 壓縮結(jié)果對比Table 1 Comparison of compression results

圖3 dolphin網(wǎng)絡(luò)壓縮前后布局效果Fig.3 Layout effect of dolphin network before and after compression

另外，基于社團結(jié)構(gòu)的壓縮更有助于感知網(wǎng)絡(luò)整體結(jié)構(gòu)和社團間的相互作用。以圖3（d）為例，可以發(fā)現(xiàn)，原始網(wǎng)絡(luò)可劃分為5個社團。其中，社團C1、C5包含節(jié)點數(shù)量較多，其他3個社團節(jié)點數(shù)量較少；社團C1、C5間的交互主要通過C2、C3這2個社團實現(xiàn)。C2、C3社團中的節(jié)點雖少，但是承擔(dān)著全網(wǎng)節(jié)點交互的“橋梁”作用，對網(wǎng)絡(luò)的拓撲構(gòu)成十分重要。而圖3（b）、（c）中沒有保留C2、C3社團，不能準確反映C2、C3社團的“橋梁”作用，C4直接與C1交互，容易對用戶理解網(wǎng)絡(luò)在中觀尺度上的結(jié)構(gòu)特征造成偏差。

2）采用多粒度社團結(jié)構(gòu)劃分算法，展示社團基本結(jié)構(gòu)，并實現(xiàn)網(wǎng)絡(luò)的多粒度壓縮布局。

本文方法在壓縮邊緣節(jié)點的同時保留了必要的社團結(jié)構(gòu)代表節(jié)點。由于基于拓撲勢對節(jié)點的重要性進行分析，保留的節(jié)點對社團構(gòu)成的貢獻較大，反映了社團的基本結(jié)構(gòu)。通過保留這部分節(jié)點及連接關(guān)系，可以清晰地展示社團內(nèi)部基本結(jié)構(gòu)。同時，通過壓縮非重要節(jié)點和刪除重復(fù)連邊，降低社團內(nèi)部連邊數(shù)量，有助于在視覺上感知社團結(jié)構(gòu)，發(fā)現(xiàn)社團或網(wǎng)絡(luò)結(jié)構(gòu)中的重要節(jié)點。

根據(jù)社團結(jié)構(gòu)劃分的粒度，本文方法通過壓縮合并邊緣節(jié)點，有效降低網(wǎng)絡(luò)規(guī)模、節(jié)點數(shù)和連邊數(shù)，實現(xiàn)多粒度的壓縮布局。圖5為對karat網(wǎng)絡(luò)數(shù)據(jù)進行3級壓縮布局的效果圖。如圖5（d）所示，根據(jù)節(jié)點壓縮比例的不同可以控制網(wǎng)絡(luò)壓縮比例，最多可將一個社團壓縮為1個節(jié)點。如圖5（d）中每個節(jié)點代表一個社團，“節(jié)點”1、32、34之間能夠直接交互，而“節(jié)點”6只能通過“節(jié)點”1與其他“節(jié)點”交互。

圖4 football網(wǎng)絡(luò)壓縮前后布局效果Fig.4 Layout effect of football network before and after compression

圖5 采用本文方法對karat網(wǎng)絡(luò)進行多粒度壓縮前后布局效果Fig.5 Layout effect of karat network before and after multi-granularity compression by proposed method

4 結(jié) 論

為有效展示網(wǎng)絡(luò)的中尺度結(jié)構(gòu)特征，將力導(dǎo)引布局算法與網(wǎng)絡(luò)社團結(jié)構(gòu)特征相結(jié)合，提出了一種基于社團結(jié)構(gòu)節(jié)點重要性的網(wǎng)絡(luò)可視化壓縮布局方法。實驗結(jié)果和分析表明，該方法的優(yōu)勢體現(xiàn)在3個方面：

1）有效壓縮節(jié)點和連邊數(shù)量，降低視覺雜亂現(xiàn)象。

2）比較完整地從中觀尺度反映網(wǎng)絡(luò)的結(jié)構(gòu)構(gòu)成與交互，便于分析不同社團或節(jié)點在網(wǎng)絡(luò)拓撲中的不同作用。

3）基于多粒度的社團結(jié)構(gòu)探測和不同的節(jié)點壓縮比可以實現(xiàn)多粒度的壓縮展示。本文方法主要通過將網(wǎng)絡(luò)壓縮方法和力導(dǎo)引布局算法結(jié)合，從社團構(gòu)成和社團結(jié)構(gòu)上展示了網(wǎng)絡(luò)的中觀尺度結(jié)構(gòu)，下一步將考慮與其他節(jié)點布局算法和交互方法結(jié)合，進一步優(yōu)化布局結(jié)果。