基于熵的多屬性決策超網絡重要節點識別方法

吳英晗,李明達,胡 楓

(青海師范大學 a.藏語智能信息處理及應用國家重點實驗室;b.高原科學與可持續發展研究院,西寧 810008)

0 引言

近年科技的高速發展,使人類社會處于信息化數據時代。從現實社會的關系網到虛擬的互聯網,從線上到線下,我們的生活始終與復雜網絡息息相關[1]。比如與生活密切相關的因特網、交通網絡、電力網絡[2];與他人交流的社交網絡、科研合作網絡[3];可以說網絡無處不在。隨著對網絡科學領域的深入研究,人們發現基于超圖的超網絡[4-6]可以更好地表述公交網絡中線路途徑多個站點以及科研合作網絡中多個作者多次合作等真實網絡的情況,于是人們便將研究的焦點轉向更能精準刻畫真實網絡多元復雜關系的超網絡。無論是基于普通圖的復雜網絡[7-9]還是基于超圖的超網絡,都存在部分節點,其失效會對整個網絡的結構及功能產生深層次的影響[10],因此,如何度量超網絡中節點的重要性以及挖掘超網絡中的重要節點仍舊是網絡科學領域值得研究的問題。

目前,諸多學者根據實際需求針對節點重要性問題做了相關研究。Estrada等[5]將復雜網絡中的子圖中心性和聚類系數指標擴展到超網絡,并用這兩種指標識別出了3類現實超網絡中的重要節點;Kapoor等[11]將節點度中心性的概念推廣到社交超網絡,依據節點的強度將節點間的聯系分為強聯系和弱聯系,并以此為附加特征,從而提高了預測的準確性。王雨等[12]從超網絡視角出發,綜合考慮作者自身科研價值以及作者間的重要性貢獻值,提出了一種新的重要度評價指標D′,有效識別出了科研領域的核心作者。Song等[13]基于轉錄組學數據構建超圖,引入新的平均超圖中心性指標對與病毒/病原體感染相關的基因集進行對比分析,結果表明平均調和s-介數中心性能夠有效識別關鍵基因。周麗娜等[14]將復雜網絡中的K-shell分解法擴展到超網絡,基于復合參數的思想,結合超度及K-shell值利用歐氏距離公式提出了一種超網絡關鍵節點識別指標。

1 相關工作

1.1 超網絡相關概念

1.2 超網絡中節點重要性評價相關指標

定義1超網絡介數中心性 介數中心性[18]用于刻畫節點對網絡中沿著最短超路徑傳輸網絡流的控制力,可表征網絡中處在“橋”位置節點的重要性。節點vi的介數中心性定義為

(1)

其中,gk為節點vj和節點vk之間的最短超路徑數目,gk(i)為節點vj和節點vk之間的最短超路徑中經過節點vi的數目。

定義2信息熵 信息熵[19]于1948年由Shannon提出,利用概率與統計方法來表征樣本空間所體現的系統無序化程度,進而反映節點在網絡中的重要性。信息熵被定義為

(2)

定義3核度中心度 核度中心度指標是結合節點超度和K-shell值,利用歐氏距離公式計算的超網絡中節點的核度值,該指標有效改善了超網絡K-shell分解方法的區分度。節點vi的核度中心度定義為

(3)

其中,dH(i)為節點vi的超度,Ks(i)為節點vi的Ks值。

定義4超網絡最大連通子圖的相對大小為網絡受到攻擊后的最大連通子圖的節點數與原始網絡總節點數之比,即:

(4)

其中,S為遭受攻擊后網絡的最大連通子圖的大小,N為原始網絡的節點數。該方法著重考察移除部分節點后網絡結構和功能的變化,通過網絡的魯棒性和脆弱性對排序算法進行客觀評價。

定義5超網絡自然連通度[20-21]超網絡的鄰接矩陣A(H)=(aij)N×N為對稱矩陣,令λ1≥λ2≥…≥λN為A(H)的特征根,表示網絡中所有閉途徑數目,則超網絡的自然連通度[22]定義為

(5)

其中,λi為超網絡鄰接矩陣的特征根。該方法基于網絡特征譜,通過計算網絡中不同長度閉環數目的加權和來刻畫網絡中替代途徑的冗余性,用于反映網絡的抗毀性,進而對排序算法進行精確性評價。

2 構造中心性度量指標

超網絡由節點及超邊組成,通過超邊連通的節點之間存在一定的重要度依賴關系。由于鄰居節點間的影響是相對重要且直接的,在對節點重要性進行度量時,考慮節點自身屬性及鄰居節點間的相互影響,提出了局部影響力和全局影響力兩種指標。

2.1 局部影響力指標

超網絡中節點超度反映節點自身的直接影響力,而節點的重要性不僅與自身屬性有關,還依賴于網絡中其他節點對其重要度的影響,尤其是鄰居節點的貢獻。為此,本文基于節點超度引入影響度的概念,來表征鄰居節點間的相互影響。

定義6節點vi對節點vj的影響度定義為

(6)

其中,dH(vi)為節點vi的超度,Γ(vj)為節點vj鄰居節點的集合。

定義7節點vi和節點vj之間的相互影響度Rw(vi,vj)定義為

Rw(vi,vj)=w(vi,vj)+w(vj,vi)

(7)

顯然節點vi和節點vj的鄰居節點不同,w(vi,vj)和w(vj,vi)不一定相等。

定義8(局部影響力LI)節點vi的局部影響力LI(vi)定義為

(8)

2.2 全局影響力指標

超網絡中節點的影響不僅取決于節點的局部影響,還依賴于節點的全局影響。K-shell分解法[14]是一種從網絡整體結構評價節點重要性的全局性指標。該方法的基本思想是通過迭代的方式將網絡劃分為從核心到邊緣的不同層次,越靠近核心的節點越具有影響力。圖1b～d分別為1-shell、2-shell和3-shell分解圖。

圖1 3-shell分解過程示例圖[14]

由圖1可知,節點1,4均位于超網絡的核心位置,具有相同的ks=3,顯然這兩個節點的影響力是不同的。K-shell分解法無法區分ks值相同的節點的影響,這會導致節點排序結果過于粗粒化,因此,為了更準確地識別影響節點,本文給出衡量節點全局影響力的定義。

定義9(全局影響力GI)考慮到節點鄰居數目及所處位置的影響,將節點vi的全局影響力GI(vi)定義為

(9)

圖1所示的網絡中,ks=3的節點可以通過全局影響力進行區分:GI(1)=12,GI(4)=14。節點5,6,7,12,15的ks值均為1,其GI值分別為8,9,5,3,2。綜上可以看出,GI指標相比ks指標能更進一步區分節點的影響力。

3 多屬性決策的重要節點識別算法

節點的局部影響及全局影響對節點重要性識別起著重要作用,但每個屬性各有側重且存在一定差異。本文在考慮網絡拓撲結構信息的基礎上,選用介數中心性來度量節點在網絡連通性方面的重要性,綜合考慮節點的局部影響力LI和全局影響力GI,通過熵理論對每個指標賦予不同的權重,提出一種基于熵的多屬性決策超網絡重要節點識別算法(Entropy Theory-Based Multi-Attribute Centrality of Hypernetworks,簡稱EBMCH)。算法步驟為

步驟1構造屬性矩陣

在評估節點重要性時,對局部影響力、介數中心性以及全局影響力進行歸一化處理,根據歸一化后的值構造屬性矩陣P:

(10)

其中,n為超網絡中的節點數,{ai1,ai2,ai3}表示節點的屬性。

步驟2計算各屬性熵值

在多屬性決策問題中,為保證各屬性權重分配的合理性,基于熵理論來客觀確定各屬性權重。如果一個屬性的信息熵越小,說明該屬性提供的信息量就越大,在綜合評價中所起的作用就越大,其權重相應就越高。基于香農熵理論,計算第j項指標的熵值ej:

(11)

步驟3根據熵值ej計算各指標的權重wj:

(12)

步驟4根據熵權法的結果,計算節點vi的權重因子si:

(13)

步驟5結合節點本身及其鄰居節點的權重因子,最終得到節點vi的基于熵的多屬性中心性EBMCH(i)為

(14)

4 實證分析

4.1 示例超網絡分析

表1 不同指標對示例超網絡的排序結果

為了進一步驗證本文算法的合理性,從網絡拓撲結構和特征譜兩個方面來驗證本文所提方法的準確性。對比按照不同方法依次移除節點后剩余網絡的最大連通子圖的相對大小及自然連通度變化情況,結果如圖2所示。

圖2 移除節點后的網絡最大連通子圖相對大小及自然連通度變化圖

由圖2a可知,EBMCH指標在移除第1,4節點后得到的網絡最大連通子圖的相對大小值略高于其他指標,而其他節點刪除后得到的最大連通子圖的相對大小值均小于或等同于其他指標,如圖2b,EBMCH指標在移除第2,7節點時的網絡自然連通度值略高于其他指標,在刪除其他節點時的網絡自然連通度值一直處于最低位置。

4.2 實證超網絡分析

4.2.1 數據來源

為了進一步驗證EBMCH算法的可行性,本文以西寧市公交數據為例,收集了截至2022年2月13日西寧市公交線路及站點的數據,得到577個公交站點以及92條公交線路。基于此數據集構建西寧市公交超網絡模型,站點表示超網絡中的節點,線路表示超網絡中的超邊。

4.2.2 實驗結果分析

圖3 所有節點的基于熵的多屬性中心性值、超度值、介數中心性值及核度中心度值

表2 EBMCH排名前20的站點及相應指標

由表2知,節點46和節點78的EBMCH值最大,即識別出的西寧市公交超網絡的重要節點分別是中心廣場北站和昆侖橋站。這與其他單一指標的識別結果一致。EBMCH值排名第3的是火車站,而其他指標識別排名靠后,相同值較多,火車站作為城市的重要樞紐,其重要性顯而易見。由EBMCH識別的4、5名站點位于西寧市城西區域,據智能CT實時數據顯示,西寧市四區中最擁堵區域為城西區,由EBMCH指標識別出的站點位于城西區的占45%以上,表明EBMCH指標能更準確、有效地識別公交超網絡重要節點。為了進一步驗證識別結果的合理性,對比網絡最大連通子圖相對大小及自然連通度值如圖4所示。

圖4 移除節點后的公交網絡最大連通子圖相對大小及自然連通度變化圖

5 結論