一種多指標融合的自適應重要節點識別方法*

邵 豪，王倫文，張孟伯

（國防科技大學電子對抗學院，合肥 230037）

0 引言

目前復雜網絡的研究得到了廣泛關注，網絡理論可以詳細分析個體間復雜的相互作用及傳播過程，在戰場態勢感知、網絡對抗等領域中發揮著關鍵作用［1］。網絡中不同節點在結構和功能上有著完全不同的功能與作用，當某些節點失效時，整個網絡會迅速遭受到破壞［2］。因此，識別網絡中的重要節點有助于分析控制網絡。例如在戰場通信網絡中，保護己方通信網中的重要節點，有助于提高網絡抗毀性，保障作戰信息的傳輸；針對敵方通信網絡的重要節點進行干擾，能夠以更少的干擾資源摧毀敵方通信。

至今已有許多評價網絡節點重要性的指標［3］，例如節點度［4］、凝聚度［5］、介數［6］等。其中節點度基于鄰居節點數目，方法簡單但準確性不高。節點的凝聚度通過分析節點間的最短路徑以提高度排序的準確性，但計算復雜度很高。Kitsak 等人提出運用K 核分解尋找網絡核心的節點，但其低分辨率限制了廣泛的應用［7］。最近，余法洪等人［8］利用最小連通支配集來識別網絡重要節點，緊密子序列數量越多節點的越重要。楊云云等人［9］考慮節點之間的接觸頻率和節點之間的接觸時間長度，提出雙向PageRank 算法在復雜網絡中挖掘重要節點。

上述文獻從不同角度出發，針對特定網絡結構定義節點重要性指標，獲得較好的性能。事實上，不同網絡擁有不同結構特征，甚至同一網絡不同部位的結構也是完全不同的，因此，單一的重要性指標在不同網絡中不可能都得到很好的性能。為此，本文提出一種多指標融合的重要節點識別方法，綜合考慮多個指標來確定重要節點。考慮到多個指標間存在關聯信息，且更多的指標會導致計算復雜度高，本文利用主成分分析法［10］篩選合適的指標，以盡可能少量不相關指標，盡可能多地覆蓋網絡信息，通過灰色關聯方法［11］確定各主成分的排序，避免主觀判斷影響算法的合理性。實驗結果表明，在不同網絡中，本文提出的重要節點識別方法普遍具有高識別精度和準確度。

1 相關知識

1.1 網絡性質參數

其中，dij表示節點i、j 間最短路徑的長度。由式（1）可得，網絡規模越小，平均最短路徑越短，其凝聚度越高。

1.2 傳統節點重要性評價指標

以下介紹常見的節點重要性指標，通過比較每個節點間的相似指標值sij，將所有節點的sij值由大至小排序。sij越高，節點在網絡中越重要。一些常見的節點重要性指標如表1 所示［12］：

表1 常見的節點重要性指標

表1 中介紹了常見的9 種節點重要性指標，這些指標包含了盡可能全面的指標信息。前6 種指標考慮節點的顯著性，即比較網絡節點的位置來衡量其重要性；后3 種指標考慮節點的破壞性，即刪除某節點后，比較網絡破壞情況來比較節點重要性。這些指標從不同方面考慮節點的重要性［12］，單個指標不可能適用于所有結構不同的網絡。例如以DC指標為例，在下頁圖1（a）中，利用DC 指標，中間節點度最高，因為在網絡中最重要，顯而易見是準確的。在（b）中，共有5 個節點的度為2，其重要性相同，但很顯然中間節點的重要性要高于邊緣節點，此時DC 指標在（b）網絡中性能很差，此時EC 指標能準確分析（b）網絡的重要節點。因此，本文考慮綜合多指標分析節點重要性，提出了MIF 方法。

圖1 兩種不同的網絡拓撲

2 多指標融合的重要節識別方法

本文提出的MIF 方法由以下步驟組成：①指標數據預處理；②利用主成分分析［10］降維，提出合適指標并降低其相關性；③熵權法［13］計算各主成分權值；④基于灰色關聯分析［11］確定節點重要性。以下詳細介紹各步驟思想與具體實現過程。

2.1 指標數據預處理

2.1.1 指標正向性調整

在上述指標中，DC、CLC、BC、KS 是正向性指標，即指標值越大，節點重要性越高；相反的，CC、EC、SP、MC、SN 指標是負向性指標。以下將負向性指標調整為正向性指標，使指標值與節點重要性的排序相統一，以便于與其他正向性指標進行綜合分析，調整方式如表2 所示。

在表2 中，CC、EC、MC、SN 指標最大值為1，表示網絡直徑，即節點距離的最大值。調整后的指標滿足正向性條件，與節點重要性排序一致。

表2 負向性指標正向調整

2.1.2 指標數據歸一化

不同指標具有不同定義、量綱單位及數量級，這直接影響指標分析的準確度，故而對指標歸一化，使不同維度指標具有可比較性。歸一化處理如下：

最終得到歸一化運算后的指標數據矩陣：

2.2 主成分分析

考慮到不同指標間存在重復信息，指標數目越多，計算復雜度越高。主成分分析法利用正交變換，將多個相關的向量指標重新組合為少數不相關的主成分指標，且這些指標盡可能包含原始信息［10］。明顯地，主成分分析法是一種基于線性變換，將高維數據投影到低維空間的降維方法，步驟如下：

2.3 灰色關聯分析

關聯度含義是多個對象間關聯程度的度量。若兩個對象的指標變化一致性較低，則關聯度較低；反之則較高。灰色關聯分析法比較不同對象間的相似性，分析其關聯程度。本文方法中，確定最優的節點重要性指標作為參考指標，利用灰色關聯分析法比較所有節點的重要性指標與參考指標，根據與參考指標的相似性綜合確定節點重要性，即節點指標與參考指標越接近，該節點重要性越高。

2.3.1 關聯系數與關聯度

前文已經將所有指標調整為正向性指標，參考指標是最優的節點重要性指標，因此，將H 矩陣中每一列指標的最大值作為參考指標，即：

事實上，節點不同維度的關聯系數對于關聯度的貢獻不同，此時關聯度Ri定義為：

其中，δj表示第j 個指標在計算關聯度時的權重。本文提出熵權法計算關聯系數權重δj。

2.3.2 熵權法確定權重

在信息論中，熵被用來判斷指標的離散程度。若某個指標離散程度越大，則其對綜合的權重也越大。例如，所有節點的某個重要性指標都相等，則該指標對離散程度為0，權重也為0，對綜合分析沒有任何貢獻。計算第j 個指標的熵如下：

其中，pij是第i 個節點的第j 個指標在該列指標中的比重，ej是第j 列指標的熵。權重系數δj為：

3 實驗分析

3.1 實驗數據與流程

為驗證本文算法性能，本文使用Zachary 網絡（http：//www-personal.umich.edu/～mejn/netdata/karate.zip） 和Dolphin 網絡（http：//www-personal.umich.edu/～mejn/netdata/dolphins.zip） 進 行 仿 真 實 驗。Zachary 網絡包含34 個節點和78 條邊；Dolphin 網絡包含62 個節點，159 條邊。網絡拓撲如下頁圖2所示。

在實驗中，首先將Zachary、Dolphin 網絡改為無權向網絡。隨后，利用Matlab 程序分別計算兩個網絡中所有節點DC、CLC、BC、KS、CC、EC、SP、MC、SN指標，得到各節點在所有單指標下的值及排序情況；再以這些指數作為節點的重要性的多維參數，正向化與歸一化后，利用SPSS 軟件對指標進行主成分分析，以消除不同指標間的相關性并降維，之后結合灰色關聯分析法與熵權法確定節點重要性指標排序，排序越前的節點在網絡中處于更加重要的地位。

圖2 網絡節點拓撲圖

3.2 實驗結果

本文采用SPSS 軟件，對節點不同重要性指標進行主成分提取。表3 表示SPSS 軟件輸出的KMO和巴特利特檢驗值，其反映原始指標間的相關性強度；表4 表示所有成分指標的方差矩陣，從中可以表示式（5）中特征值的比例排序，下頁表5 為主成分的系數矩陣。

表3 表示兩個網絡各指標KMO 和Bartlett 檢驗結果，其反映各指標間的相關性水平。KMO 抽樣用于研究不同指標間的偏相關系數，KMO∈［0，1］。已有的文獻研究表明［10］，KMO 值越接近1，說明指標間進行主成分分析的效果越好，KMO 小于0.5，則指標不適合進行主成分分析。Bartlett 球形度指標的顯著性p＜0.001 表明指標高度相關，此時主成分分析有合理的理論基礎。表3 得，KMOZachary=0.749，KMODolphin=0.654，Bartlett 球形檢度顯著性p=0.000，說明初始指標高度相關指標，進行主成分分析合理可靠。

表3 KMO 和巴特利特檢驗結果

表4 總方差解釋表

表4 是主成分分析后，各成分總方差解釋表。各成分以特征值從大到小進行排序，排序在前的成分能包含更多的原始信息，主成分共應包含80%以上信息。在兩種網絡中，前3 個成分一共可以累積87.494%與85.830%的原始信息，說明前4 個成分已經滿足對總體解釋率的需求。因此，分別取前3個成分作為各網絡節點重要性的主成分指標。成分矩陣表如表5 所示。

表5 成分矩陣表

表5 是主成分矩陣表，表示原始指標與主成分的對應系數。通過對應的線性變換，可得兩種網絡對應主成分向量。進行灰色關聯分析后，得到兩個網絡各節點的灰色關聯度值如圖3 所示。此外，研究表明，如果一個網絡中5 %～10 %的關鍵節點失效，則網絡就會陷入癱瘓［14］。因此，以下對不同指標下前10%的重要節點進行排序，結果如表6、表7所示。

圖3 各網絡節點灰色關聯度值

表6 Zachary 網絡指標位于前10%的節點排序

3.3 實驗分析

針對各重要性指標的結果，以及表6，表7 表示的節點排序，本節從算法有效性與準確性兩方面分析本文提出的MIF 方法的性能。

3.3.1 指標精度分析

指標精度分析主要考慮各方法是否能產生盡可能分散的指標值，如果多個節點的指標值相同，此時將無法區分其重要性。因此，將兩個方法得到的指標值中重復部分刪除，計算剩余不同值所占的比例，以此分析各指標結果的分散情況。

從表8 中可得，KS，EC，MC 作為粗粒度的重要性排序方法［15］，精度很低，說明大部分節點的重要性值不唯一，造成分辨困難。本文提出的MIF 方法，當某指標值相同無法分辨時，可利用其他指標進行分析，排序精度很高，在Zachary 和Dolphin 網絡中，MIF 的分散指標值比例為82.35%和96.77%，相較于其余單指標有最高的排序精度。之所以未到100%，是因為網絡中確實存在極少數節點，它們的鄰居節點及功能完全相同。由此，MIF 方法在指標精度方面有很好的表現。

表8 各指標不同值所占比例（%）

3.3.2 指標排序準確度分析

現分析表6 與表7 的指標排序結果是否和實際網絡節點的重要性相一致。在Zachary 網絡中，本文MIF 方法的前5 個節點與BC、SP、SN 相同，與DC、CLC 有4 個相同節點，與CC 有2 個相同節點；在Dolphin 網絡中，MIF 方法與SN 有6 個節點相同，與DC 與4 個節點相同，與CLC、BC 各有5 個節點相同，與EC、SP 有3 個節點相同。可以看到，MIF算法與各指標都有不同程度的關聯，說明其綜合考慮了各指標的性能，與單指標方法相比更具合理性。

為更進一步分析本文MIF 方法的準確性，以下篩選MIF 與其他單指標前10%排序結果不同的節點，分析其信息傳播能力。篩選節點的編號如圖9所示。

以下解釋選取這些節點的理由：在Zachary 網絡中，（1）2、9、10 號節點分別在DC、CLC、CC 指標的前10%排序中，但不存在于MIF 中；32 號節點存在MIF 前10 %排序中，但不存在DC、CC 排序中。（2）1、10、34 號節點是不同指標下的排序首位的節點。在Dolphin 網絡中，（1）21、52、58 號節點分別存在于其他單指標前10%排序中，但不存在于MIF 排序中；34 號節點是MIF 前10%排序中最末的節點；（2）15，37，52 是不同指標中排序首位的節點。

表9 分析傳播能力的節點編號

SIR 感染模型［16］模擬信息在網絡中的傳播，將某一節點作為初始感染節點，以α 的概率感染其鄰居節點，并以β=1 的概率作為免疫狀態，直到網絡中所有節點無法被感染時，過程終止。以下計算已感染過的節點占所有節點的比例，以此衡量節點的傳播能力。圖4 表示各網絡感染節點所占比例，其值是100 次獨立實驗的平均值。

圖4 各網絡傳染節點比例

收斂狀態時感染節點所占比例越高，說明此節點的傳播力越大［17］。對比4 組感染節點可得，在圖4（a）中，Zachary 網絡32 號節點相較于2、9、10 號節點有更優的傳播能力，因此，MIF 方法得到的10%節點排序中，32 號節點的位置是準確的。在（b）中，Zachary 網絡1 號節點的感染節點比例僅比34 號節點略高0.5%，基本持平，但遠高于10 號節點，說明Zachary 網絡中，1 號節點的傳播能力與34 號節點基本相等，這與MIF 得到的結果一致。在（c）、（d）中，Dolphin 網絡34 號節點傳播能力高于21、52、58節點，且37 號節點傳播能力高于15、52 號節點，說明相較于其他單指標方法，34 號節點在MIF 方法的前10%節點是合理的；且37 號節點作為MIF 最首的節點，比其他單指標將15 或52 號指標作為最首節點更具說服力。可見，本文MIF 方法相較于其他指標，在尋找傳播力大節點方面性能出色，重要性排序準確。

綜上可得：通過上述對Zachary 與Dolphin 網絡仿真實驗表明，本文提出的多指標融合判斷節點重要性的方法，利用不同指標的互補性，與單指標判斷相比具有很高的排序精度；且對位于前10%的節點分析表明，本文提出的MIF 方法能夠更好地找到網絡中傳播能力更大的節點，對網絡節點重要性排序更加準確。

4 結論

隨著信息技術的迅速發展，網絡在各領域都發揮著至關重要的作用，識別網絡中的重要節點在實際中有十分重要的意義，本文在已有眾多重要性指標的基礎上，提出一種基于多指標融合的重要節點識別方法。該方法主要考慮各指標間的互補性與交差關系，在進行主成分分析降低其相關性的基礎上，利用客觀賦權的方法確定每個指標的權重，并通過灰度關聯分析對網絡中所有節點進行重要性排序。實驗表明本文提出的方法是合理的，與單指標分析相比，本文方法的排序精度與準確度都有明顯的提高。下一步將深入研究在有權向網絡及動態網絡中多指標融合的重要節點識別方法。