一種新的復雜網絡節點重要性評估方法

張憲立，唐建新

（蘭州理工大學計算機與通信學院，蘭州 730050）

0 概述

復雜網絡將現實社會中的復雜系統抽象為網絡結構圖以便于描述與理解，并利用節點與節點間的連邊關系來描述系統中各組成部分之間的關系。在網絡信息時代，人們通過社交網絡獲取和傳遞消息，社交網絡的出現極大地便利了人們的生活，并將逐漸取代電視、廣播和報紙等傳統信息傳播方式。在整個社交網絡中通常由多個重要的節點控制信息傳播，因此準確識別網絡中的關鍵節點對于研究網絡信息交互問題具有重要作用［1-2］。

在現實世界中，每個社交網絡都可以被抽象為一張圖，其中節點代表網絡中的用戶，節點間的連邊代表用戶之間的關系［3］。近年來，研究人員對識別復雜網絡中具有影響力的傳播者進行了大量研究并從不同角度分析節點中心性指標，例如，只考慮節點本身拓撲結構性質的度中心性（Degree Centrality，DC）［4］，判定一個給定節點是否位于其他節點最短路徑上的介數中心性（Betweenness Centrality，BC）［5］，代表一個給定節點到網絡中其他節點的距離之和的倒數的緊密中心性（Closeness Centrality，CC）［6］以及通過網絡分解確定節點重要性的K核分解中心性（K-Shell decomposition centrality，KS）［7］和H指數中心性（H-index centrality，H）［8］。

由于現有基于中心性的節點重要性評估方法經常會出現重要程度不同的兩個節點被賦予相同的權值，因此不能保證網絡中所有節點的重要性得到準確度量。此外，網絡拓撲結構、網絡規模以及節點位置都會對評估指標的精確性與適用性產生較大影響，因此，研究人員綜合考慮這些因素后對現有評估方法進行了改進。文獻［9］通過對K核分解中心性進行再次分解提出混合度分解中心性，文獻［10］考慮了節點及其鄰居性質提出局部結構中心性，文獻［11］基于網絡拓撲結構提出混合度中心性，文獻［12］根據節點位置及其鄰居節點性質提出一種新的節點重要性評估方法，上述方法均是通過可調參數來調整評估性能。文獻［13］提出一種兩層架構的節點重要性評估方法，文獻［14］采用多屬性決策技術提高節點重要性的評估準確性，但由于此類方法的評估性能取決于所采取組合方式的性能，因此與節點真實的重要程度存在一定差距。

在現有評估方法的基礎上，本文根據鄰居節點的拓撲結構定義改進的H指數中心性（Improved H-index centrality，IH），通過IH計算節點本身及其鄰居節點的IH值之和（ILH），并將節點自身及其鄰居節點的ILH值分別作為節點質量和鄰居節點的質量，同時利用萬有引力定律公式定義改進的重力中心性（Improved Gravity Centrality，IGC）。

1 相關定義

令G(V，E) 表示一個無向無權的簡單網絡，其中：V={ν1，ν2，…，νn}表示G中節點的集合；E={(νi，νj)|νi，νj∈V}表示G中邊的集合，且|V|=n，|E|=m。A表示G對應的鄰接矩陣，如果節點νi和νj之間存在連邊，則其元素Aij=1，否則Aij=0。在復雜網絡中，評估節點重要性的方法主要分為：僅考慮節點本身及其鄰居節點拓撲結構的局部評估方法，考慮節點在網絡全局中的作用的全局評估方法及考慮節點在網絡中所處位置的位置屬性評估方法3種。

定義1網絡中某個節點νi的度中心性為與該節點相連接的其他節點的數目，即該節點的鄰居節點數。度中心性的計算公式為：

其中，n為網絡中節點的總數。

定義2網絡中某個節點νj的介數中心性為任意兩個節點間的最短路徑通過該節點的數量與節點間總路徑數量的比值，介數中心性的計算公式為：

其中，σst為網絡中任意兩個節點s和t之間的最短路徑數量，σst(νi)為通過節點νi的最短路徑數量。當節點的介數中心性較大時，說明該節點在傳輸信息、物質和能量時負載較小。

定義3網絡中某個節點νi的緊密中心性為該節點到其他節點的距離之和的倒數，緊密中心性的計算公式為：

其中，dij為節點νi到網絡中某個節點νj的最短距離。

定義4 K核分解為重復去除網絡中度值小于k（k=1，2，…）的所有節點及其連邊，使得網絡中剩下的節點的度值均大于等于k。通過對網絡進行K核分解可計算出不同節點的ks值。首先將網絡中所有節點的ks值設置為1，然后找到網絡中所有度為1的節點并將這些節點及其連邊關系刪除，重新計算網絡中節點的度后，再將度為1的節點及其連邊關系刪除，直至網絡中沒有度為1的節點。此時，網絡中剩余節點的ks值設置為2，再重復執行上述操作，直至網絡中沒有度為2的節點。以此類推，直至網絡中沒有節點存在。節點的ks值越大，意味著該節點越接近于網絡中心，最靠近中心的節點被稱為K核分解中心性節點。

定義5 H指數中心性通過考慮鄰居節點的度和節點自身的度來確定節點的重要性。節點中心性由節點自身及其鄰居的性質決定，節點νi的H指數中心性計算公式為：

在上述定義中，度中心性、介數中心性和緊密中心性均只考慮網絡圖中單個節點的拓撲位置及其特征，僅從網絡局部特性對節點重要性進行分析，而K核分解中心性及H指數中心性則從網絡全局的拓撲結構來考慮節點的重要性，但其仍不能準確反映出網絡中節點的重要程度。可見，僅考慮節點的單一影響因素不能準確評估網絡中節點的性能與重要性。

2 節點重要性評估方法

一個節點可以被其鄰居節點影響，然而節點的H指數對節點本身及其鄰居節點信息的微小變化并不敏感，因此不利于評估節點在網絡鏈路信息發生微小變化時的傳播能力。此外，在多數情況下很難確保所收集的數據集完全正確且沒有任何鏈路信息錯誤。對于一個節點，如果某些鄰居節點的信息發生變化，該節點的H指數值不會受到影響，這是因為H指數只考慮具有高質量信息的鄰居數量，少數鄰居的微小變化不會引起節點整體傳播能力的變化。對于基于度中心性和介數中心性等的節點重要性評估方法，少數邊缺失或不正確的連接信息會對節點排序結果產生重要的影響。

然而，H指數對于重要程度不同的節點總是賦予相同的值，這導致了在區分這些節點的實際傳播能力時存在分辨限制問題。針對該問題，本文提出一種改進的H指數中心性（IH），IH綜合考慮了節點νi的所有鄰居的性能，將節點的重要性進行進一步劃分。節點νi的IH指數中心性計算公式為：

其中，α1和α2表示介于［0，1］的隨機變量，A1表示在νi的鄰居節點中度大于節點νi的節點個數，A2表示在νi的鄰居節點中度等于節點νi的節點個數，表示節點νi的鄰居節點集合，|表示節點νi的度。

節點νi及其鄰居節點的ILH值計算公式為：

受萬有引力定律的影響，本文以節點νi和節點νj的ILH值作為節點νi和節點νj的質量，兩節點間的最短距離作為節點間的半徑，提出改進的重力中心性。節點νi的改進重力中心性計算公式為：

圖1為一個簡單網絡的示意圖，其中，節點數量|V|為13，邊數量|E|為17。將本文IGC方法與DC、H、IH、ILH評估方法進行對比，結果如表1所示。在DC和H兩種經典方法中，將所有節點分別賦予5種和3種不同的權值，即節點被劃分為5種和3種等級，因此出現了重要性不一樣的節點被賦予相同權值的情況，對于節點重要性的評估準確性較差。IH、ILH和IGC方法分別將所有節點賦予8種、9種和12種權值，即節點被劃分為8種、9種和12種等級。本文IGC方法綜合考慮了節點自身性質及網絡拓撲結構，相比其他方法在區分節點重要性方面效果更佳，找出的重要節點準確性更高。

圖1 一個簡單網絡的示意圖Fig.1 Schematic diagram of a simple network

表1 簡單網絡中對應DC、H、IH、ILH、IGC方法的權值設置Table 1 Weight setting corresponding to DC,H,IH,ILH,IGC methods in a simple network

3 評價標準及方式

3.1 SIR傳播模型

SIR傳播模型［16］可用于評估網絡中不同節點的傳播能力。在標準隨機SIR傳播模型中，每個節點可以被分為易感（S）、感染（I）和恢復（R）3種不同狀態［17-19］。在傳播過程開始時，只有一個節點被設置為I狀態，而其他節點均被設置為S狀態。然后，受感染的節點將以概率α擴散至與之相連的所有易感節點，而受感染的節點將有可能以概率β進行恢復并被設置為R狀態。在傳播過程結束后，整個網絡中只有I與R兩種狀態，而統計出的網絡中易感節點的數量即為節點的傳播能力。

在評估完節點的傳播能力后，使用Kendall相關系數表示各中心性指標與真實數據之間的關系［20-21］。假設序列Χ=(x1，x2，…，xn)和序列Y=(y1，y2，…，yn)是兩個與節點相關的序列，兩個序列中的元素個數一致，且每個序列中的第i個元素都表示節點νi的某個屬性值。將兩個節點一一對應組成一個新的序列ΧY=((x1，y1)，(x2，y2)，…，(xn，yn))，取ΧY中的兩個元素(xi，yi)和(xj，yj)(其中i≠j)，若xi＞xj且yi＞yj或者xi＜xj且yi＜yj，則認為這兩個元素一致；若xi＞xj且yi＜yj或者xi＜xj且yi＞yj，則認為這兩個元素不一致。Kendall相關系數τ的計算公式為：

其中，C表示XY中任意兩個元素所組成有序對中具有一致性元素對的數量，D表示XY中任意兩個元素所組成有序對中具有不一致性元素對的數量。τ的取值范圍為［-1，1］，當τ＞0時認為兩個有序對正相關，當τ＜0時認為兩個有序對負相關。通過在SIR傳播模型中得到的節點傳播能力和中心性指標所計算出的Kendall相關系數可以較好地反映節點重要性評估方法的優劣，更優的中心性指標有助于更好地評估節點的重要性。

3.2 單調性

區分具有不同傳播能力及等級的節點的能力是度量復雜網絡中節點重要性評估方法的重要指標之一，而利用單調性（M）可以檢驗不同中心性序列對于節點重要性的區分能力［13，22］。序列R的M值計算公式為：

其中：n表示序列R中的節點數量；nr表示在等級r上的節點數量；M的取值范圍為［0，1］，其數值較大表示該方法具有較高的評估準確率。

4 實驗數據集與結果分析

4.1 實驗數據集

本文共使用6個真實網絡數據集和2個人工網絡數據集。真實網絡包括Zachary空手道俱樂部工作成員關系網絡（Karate）［23］、Krebs美國政治圖書網絡（Polbooks）［24］、爵士音樂家網絡（Jazz）［25］、美國航空公司飛行路線網絡（USair）［26］、Rovira Virgili大學電子郵件信息網絡（Email）［27］和蛋白質相互關系網絡（Yeast）［28］。人工網絡包含小世界網絡（WS）［29］和Lancichinetti-Fortunato-Radicchi隨機網絡（LFR）［30］，人工網絡都是通過Gephi軟件自動生成。網絡數據集的具體設置如表2所示，其中βth表示各個網絡在SIR傳播模型中的感染率閾值。

表2 網絡數據集設置Table 2 Setting of network datasets

4.2 實驗結果

為評價本文IGC方法的評估性能進行以下實驗：1）確定評估方法和SIR傳播模型之間的排序相關性，并計算出IGC方法相較于現有方法的評估準確率提升比例；2）將IGC方法與DC、BC、CC、KS和H方法進行單調性分析與比較。

4.2.1 準確性分析

為驗證評估方法與SIR傳播模型之間的排序相關性，通過計算節點傳播效率得到網絡中的最優傳播者。在實驗過程中：1）使用基于網絡屬性特征和拓撲結構的靜態評估方法計算網絡節點傳播效率序列；2）基于網絡數據集，采用SIR傳播模型及Kendall相關系數τ開展動態傳播模擬仿真，近似計算網絡節點傳播效率序列。在6個真實網絡和2個人工網絡數據集上，將本文IGC方法與5種評估方法進行比較，實驗結果如圖2所示，其中，β表示各個網絡在SIR傳播模型中的感染率，τ表示SIR傳播模型與評估方法之間的Kendall相關系數，平行于縱坐標軸的虛線表示各個網絡的感染率閾值βth。在LFR網絡中，由于KS算法在感染率過低時效果不佳，為突出顯示其他算法間的性能差異，因此本文在圖2（h）中只呈現了τ≥0.4時的Kendall相關系數變化趨勢。實驗結果表明，本文IGC方法與現有方法相比在多數網絡數據集中均具有更好的評估性能。由圖2可以看出，在β值較小時，本文IGC方法的Kendall相關系數τ與現有方法相比有一定差距，但隨著β的不斷增大且接近βth時，IGC方法的評估性能要優于現有方法。在β＞βth的情況下，δ=0.01時不同評估方法的Kendall相關系數τ的平均值σ(τI)計算公式為：

圖2 在網絡數據集上不同評估方法與SIR傳播模型的Kendall相關系數變化趨勢1Fig.2 The change trend 1 of Kendall correlation coefficient between different evaluation methods and SIR propagation model on the network datasets

網絡數據集中不同評估方法的Kendall相關系數τ的平均值σ（τI）比較如表3所示。由此可以看出，本文IGC方法的σ(τI)在多數網絡中要優于現有方法。

表3 網絡數據集中不同評估方法的Kendall相關系數平均值比較Table 3 Comparison of average value of Kendall correlation coefficient of different evaluation methods in the network datasets

為衡量本文IGC方法相比現有方法的評估準確率提升比例，對Kendall相關系數τ的定義進行改進，計算公式修改為：

其中，τC(I)表示IGC方法和SIR模型之間的Kendall相關系數，τI表示現有方法和SIR模型之間的Kendall相關系數。當ηI＞0時，意味著IGC方法優于現有方法；當ηI＜0時，意味著IGC方法劣于現有方法；當ηI=0時，意味著IGC方法與現有方法相比無明顯優劣區別。

圖3表明在不同網絡數據集中IGC方法與現有方法相比的評估準確率提升比例，其中，β表示在SIR傳播模型中的不同感染率，η表示IGC方法與現有方法相比評估準確率的提升比例，平行于橫坐標軸的虛線表示τC(IGC)曲線，平行于縱坐標軸的虛線表示各個網絡的βth。在WS和LFR網絡中，由于KS方法效果明顯劣于對比方法，性能接近兩個量級，因此為更直觀呈現本文IGC方法和其他方法間的性能差異，本文在圖3（g）和圖3（h）中未呈現KS方法的Kendall相關系數變化趨勢。

圖3 在網絡數據集上不同評估方法與SIR傳播模型的Kendall相關系數變化趨勢2Fig.3 The change trend 2 of Kendall correlation coefficient between different evaluation methods and SIR propagation model on the network datasets

由圖3可看出，在β＞βth時τC(IGC)相比τBC、τKS有較大的評估準確率性能提升，盡管在Polbooks和Email網絡數據集中相比τKS優勢不明顯，但在網絡數據集中的總體評估效果仍為最優。對于τDC、τCC和τH而言，在大部分網絡數據集中τC(IGC)與其之間的η均大于0，即在這些網絡數據集中IGC方法的評估準確性優于現有方法。

4.2.2 單調性分析

單調性用于評估排序節點的唯一性，當網絡中的節點都被賦予不同的權值時所用評估方法的單調性最強，而當網絡中的節點都被賦予相同的權值時，所用評估方法的單調性最弱。本文計算DC、BC、CC、KS、H和IGH方法的M值，如表4所示。可以看出，IGC方法在所有真實網絡數據集中的M值均優于DC、CC、KS和H方法。然而在人工網絡數據集中，IGC和BC方法均表現出較好的單調性，但從整體上看，IGC方法單調性更優，主要原因為IGC方法相比現有方法能將網絡中的節點劃分為更多不同的等級。

表4 網絡數據集中不同評估方法的M 值比較Table 4 Comparison of M value of different evaluation methods in the network datasets

5 結束語

本文根據鄰居節點的拓撲結構并結合萬有引力定律，提出一種基于改進重力中心性的節點重要性評估方法。由于SIR傳播模型的Kendall相關系數和單調性與節點真實傳播能力之間有較強關聯性，且對于具有不同傳播能力的節點有較強的區分能力，因此通過實驗驗證了該方法的正確性與有效性，并表明其能準確地評估節點的重要性。下一步可將多種節點重要性靜態評估方法與動態網絡相結合，利用節點屬性關聯特性實現節點重要性排序。