基于社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)重要性的網(wǎng)絡(luò)可視化壓縮布局

吳玲達(dá)，張喜濤，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é)點(diǎn)和連邊的細(xì)節(jié)信息完全展示在有限尺寸的屏幕中，會導(dǎo)致以下問題：①受屏幕尺寸限制，對于具有大量節(jié)點(diǎn)和高密度連邊的大規(guī)模網(wǎng)絡(luò)可視化來說，用戶會陷入混亂重疊的節(jié)點(diǎn)-連接圖中，難以識別和感知網(wǎng)絡(luò)的整體結(jié)構(gòu)，更不能引導(dǎo)用戶發(fā)現(xiàn)感興趣的元素；②大規(guī)模的數(shù)據(jù)量必然帶來更大的計算壓力，對算法和硬件都會有更高的要求。低效、耗時的網(wǎng)絡(luò)可視化就失去了應(yīng)有的意義。

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

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

抽樣是根據(jù)一定的抽樣策略篩選有代表性的節(jié)點(diǎn)和連邊，用盡可能少的節(jié)點(diǎn)和連邊最大限度地反映原始網(wǎng)絡(luò)的結(jié)構(gòu)特征。常用的抽樣策略包括隨機(jī)選點(diǎn)、隨機(jī)選邊、隨機(jī)游走和基于拓?fù)浞謱幽Ｐ偷某闃硬呗缘龋?-4］。

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 基于拓?fù)鋭莸纳鐖F(tuán)結(jié)構(gòu)節(jié)點(diǎn)重要性評估

節(jié)點(diǎn)拓?fù)鋭莸拇笮∶枋隽司W(wǎng)絡(luò)拓?fù)渲械哪硞€節(jié)點(diǎn)受自身和近鄰節(jié)點(diǎn)共同影響所具有的勢值。類似地，對于一個給定的社團(tuán)C=（VC，EC）（VC為社團(tuán)C中的所有節(jié)點(diǎn)集合，EC為社團(tuán)C中的所有連邊集合），社團(tuán)中任意一個節(jié)點(diǎn)的拓?fù)鋭莸挠嬎愎綖?/p>

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

根據(jù)節(jié)點(diǎn)的度和節(jié)點(diǎn)到社團(tuán)中心節(jié)點(diǎn)的最短路徑長度確定的社團(tuán)結(jié)構(gòu)中節(jié)點(diǎn)的拓?fù)湮恢梅从沉斯?jié)點(diǎn)對社團(tuán)結(jié)構(gòu)構(gòu)成的貢獻(xiàn)度大小。如圖2中左圖所示，通過計算節(jié)點(diǎn)在社團(tuán)結(jié)構(gòu)中的勢來評估節(jié)點(diǎn)的重要性，根據(jù)重要性排序?qū)⑸鐖F(tuán)內(nèi)部節(jié)點(diǎn)分為3類：①節(jié)點(diǎn)9最重要，是拓?fù)鋭輼O值點(diǎn)，也是社團(tuán)中心點(diǎn)，圖2中左圖用紅色標(biāo)注，用VCA表示；②節(jié)點(diǎn)7，19，21，22，25，26，10，16對拓?fù)鋭輼O值點(diǎn)影響較大，圖2中左圖用黃色標(biāo)注，用VCB表示；③其余節(jié)點(diǎn)為邊緣節(jié)點(diǎn)，圖2中左圖采用灰色標(biāo)注，用VCC表示。選擇社團(tuán)中拓?fù)鋭莸臉O值點(diǎn)作為社團(tuán)代表點(diǎn)，選擇對代表點(diǎn)拓?fù)鋭葚暙I(xiàn)大的節(jié)點(diǎn)作為相對重要節(jié)點(diǎn)。

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

2.3 壓縮布局算法

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

本文選擇網(wǎng)絡(luò)社團(tuán)分析領(lǐng)域3組標(biāo)準(zhǔn)數(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é)點(diǎn)數(shù)和連邊數(shù)如表1所示。

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

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

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

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

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

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

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

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

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

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

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

圖5 采用本文方法對karat網(wǎng)絡(luò)進(jìn)行多粒度壓縮前后布局效果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ò)社團(tuán)結(jié)構(gòu)特征相結(jié)合，提出了一種基于社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)重要性的網(wǎng)絡(luò)可視化壓縮布局方法。實(shí)驗(yàn)結(jié)果和分析表明，該方法的優(yōu)勢體現(xiàn)在3個方面：

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

2）比較完整地從中觀尺度反映網(wǎng)絡(luò)的結(jié)構(gòu)構(gòu)成與交互，便于分析不同社團(tuán)或節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械牟煌饔谩?/p>

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