基于社團結構節點重要性的網絡可視化壓縮布局

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

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

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

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

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

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

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

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

1 相關工作

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

相比于KK算法和DH算法，FR算法在大多數網絡數據的可視化應用中具有更好的對稱性和聚類布局效果，繪制結果更加符合美學標準，得到廣泛的應用。

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

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

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

2 網絡可視化壓縮布局方法

2.1 多粒度社團結構探測

相比于其他社團結構探測算法，Louvain算法的運算速度更快，可以快速處理具有數以億計節點的網絡，另外基于層次聚類可以輸出不同粒度的社團結構劃分結果。因此，本文采用Louvain算法實現多粒度社團結構探測。

模塊度是刻畫網絡中社團劃分質量的重要指標之一，可通過如下公式計算：

式中：m為網絡中的連邊總數；Aij為節點對（vi，vj）連邊的權值；ki為節點度；cvi為節點vi隸屬的社團；δ（cvi，cvj）為狄拉克函數，如果節點隸屬于同一社團，則為1，否則為0。

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

式中：Cin為社團C中所有內部邊權重的總和；Cout為所有與社團C中節點鄰接的邊權重總和；Ki為所有鄰接節點i的邊權重的總和；Ki，in為所有從節點i與社團C中節點鄰接的邊權重總和；M 為網絡中所有邊的權重之和。

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

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

2.2 基于拓撲勢的社團結構節點重要性評估

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

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

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

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

2.3 壓縮布局算法

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

對于vi∈VCC，用VN（vi）表示節點vi的鄰居節點集合，當節點vi滿足式（2）時，將節點vi和社區結構代表節點vj壓縮為一個節點，并將vj設置為vi的替代節點。

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

算法1 廣度優先遍歷替代節點設置算法。

輸入：原始節點vi、鄰居節點集合VN（vi）、社團結構代表點集合V′CA。

輸出：替代節點replace（vi）。

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

1）如果節點vi的鄰居節點vj屬于社團結構代表點集合V′CA，則把節點vj設置為節點vi的替代節點。

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

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

3 實驗結果與分析

本文選擇網絡社團分析領域3組標準數據集：dolphin、football及karat。其中，dolphin為海豚社會網絡，football為美國大學生足球聯賽社會網絡，karat為美國空手道俱樂部社會網絡。對應網絡的節點數和連邊數如表1所示。

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

實驗中選擇的節點壓縮比為0.2，即方法1和方法2按照全網節點總數的20%篩選網絡代表節點，本文方法按照每個社團中節點總數的20%篩選社團結構代表節點。

表1為不同方法的壓縮結果對比。可知，不同壓縮方法通過合并非重要節點，較大程度地降低了節點和連邊數量，實現了網絡壓縮的目的。

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

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

1）基于社團結構進行壓縮，能夠保留網絡的社團構成，突出中觀尺度結構特征。

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

表1 壓縮結果對比Table 1 Comparison of compression results

圖3 dolphin網絡壓縮前后布局效果Fig.3 Layout effect of dolphin network before and after compression

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

2）采用多粒度社團結構劃分算法，展示社團基本結構，并實現網絡的多粒度壓縮布局。

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

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

圖4 football網絡壓縮前后布局效果Fig.4 Layout effect of football network before and after compression

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

4 結 論

為有效展示網絡的中尺度結構特征，將力導引布局算法與網絡社團結構特征相結合，提出了一種基于社團結構節點重要性的網絡可視化壓縮布局方法。實驗結果和分析表明，該方法的優勢體現在3個方面：

1）有效壓縮節點和連邊數量，降低視覺雜亂現象。

2）比較完整地從中觀尺度反映網絡的結構構成與交互，便于分析不同社團或節點在網絡拓撲中的不同作用。

3）基于多粒度的社團結構探測和不同的節點壓縮比可以實現多粒度的壓縮展示。本文方法主要通過將網絡壓縮方法和力導引布局算法結合，從社團構成和社團結構上展示了網絡的中觀尺度結構，下一步將考慮與其他節點布局算法和交互方法結合，進一步優化布局結果。