基于熵的多屬性決策超網(wǎng)絡重要節(jié)點識別方法

吳英晗,李明達,胡 楓

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

0 引言

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

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

1 相關工作

1.1 超網(wǎng)絡相關概念

1.2 超網(wǎng)絡中節(jié)點重要性評價相關指標

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

(1)

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

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

(2)

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

(3)

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

定義4超網(wǎng)絡最大連通子圖的相對大小為網(wǎng)絡受到攻擊后的最大連通子圖的節(jié)點數(shù)與原始網(wǎng)絡總節(jié)點數(shù)之比,即:

(4)

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

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

(5)

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

2 構造中心性度量指標

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

2.1 局部影響力指標

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

定義6節(jié)點vi對節(jié)點vj的影響度定義為

(6)

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

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

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

(7)

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

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

(8)

2.2 全局影響力指標

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

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

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

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

(9)

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

3 多屬性決策的重要節(jié)點識別算法

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

步驟1構造屬性矩陣

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

(10)

其中,n為超網(wǎng)絡中的節(jié)點數(shù),{ai1,ai2,ai3}表示節(jié)點的屬性。

步驟2計算各屬性熵值

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

(11)

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

(12)

步驟4根據(jù)熵權法的結果,計算節(jié)點vi的權重因子si:

(13)

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

(14)

4 實證分析

4.1 示例超網(wǎng)絡分析

表1 不同指標對示例超網(wǎng)絡的排序結果

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

圖2 移除節(jié)點后的網(wǎng)絡最大連通子圖相對大小及自然連通度變化圖

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

4.2 實證超網(wǎng)絡分析

4.2.1 數(shù)據(jù)來源

為了進一步驗證EBMCH算法的可行性,本文以西寧市公交數(shù)據(jù)為例,收集了截至2022年2月13日西寧市公交線路及站點的數(shù)據(jù),得到577個公交站點以及92條公交線路?；诖藬?shù)據(jù)集構建西寧市公交超網(wǎng)絡模型,站點表示超網(wǎng)絡中的節(jié)點,線路表示超網(wǎng)絡中的超邊。

4.2.2 實驗結果分析

圖3 所有節(jié)點的基于熵的多屬性中心性值、超度值、介數(shù)中心性值及核度中心度值

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

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

圖4 移除節(jié)點后的公交網(wǎng)絡最大連通子圖相對大小及自然連通度變化圖

5 結論