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

吳英晗,李明達(dá),胡 楓

(青海師范大學(xué) a.藏語(yǔ)智能信息處理及應(yīng)用國(guó)家重點(diǎn)實(shí)驗(yàn)室;b.高原科學(xué)與可持續(xù)發(fā)展研究院,西寧 810008)

0 引言

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

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

1 相關(guān)工作

1.1 超網(wǎng)絡(luò)相關(guān)概念

1.2 超網(wǎng)絡(luò)中節(jié)點(diǎn)重要性評(píng)價(jià)相關(guān)指標(biāo)

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

(1)

其中,gk為節(jié)點(diǎn)vj和節(jié)點(diǎn)vk之間的最短超路徑數(shù)目,gk(i)為節(jié)點(diǎn)vj和節(jié)點(diǎn)vk之間的最短超路徑中經(jīng)過(guò)節(jié)點(diǎn)vi的數(shù)目。

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

(2)

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

(3)

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

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

(4)

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

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

(5)

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

2 構(gòu)造中心性度量指標(biāo)

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

2.1 局部影響力指標(biāo)

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

定義6節(jié)點(diǎn)vi對(duì)節(jié)點(diǎn)vj的影響度定義為

(6)

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

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

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

(7)

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

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

(8)

2.2 全局影響力指標(biāo)

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

圖1 3-shell分解過(guò)程示例圖[14]

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

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

(9)

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

3 多屬性決策的重要節(jié)點(diǎn)識(shí)別算法

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

步驟1構(gòu)造屬性矩陣

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

(10)

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

步驟2計(jì)算各屬性熵值

在多屬性決策問(wèn)題中,為保證各屬性權(quán)重分配的合理性,基于熵理論來(lái)客觀確定各屬性權(quán)重。如果一個(gè)屬性的信息熵越小,說(shuō)明該屬性提供的信息量就越大,在綜合評(píng)價(jià)中所起的作用就越大,其權(quán)重相應(yīng)就越高。基于香農(nóng)熵理論,計(jì)算第j項(xiàng)指標(biāo)的熵值ej:

(11)

步驟3根據(jù)熵值ej計(jì)算各指標(biāo)的權(quán)重wj:

(12)

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

(13)

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

(14)

4 實(shí)證分析

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

表1 不同指標(biāo)對(duì)示例超網(wǎng)絡(luò)的排序結(jié)果

為了進(jìn)一步驗(yàn)證本文算法的合理性,從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和特征譜兩個(gè)方面來(lái)驗(yàn)證本文所提方法的準(zhǔn)確性。對(duì)比按照不同方法依次移除節(jié)點(diǎn)后剩余網(wǎng)絡(luò)的最大連通子圖的相對(duì)大小及自然連通度變化情況,結(jié)果如圖2所示。

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

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

4.2 實(shí)證超網(wǎng)絡(luò)分析

4.2.1 數(shù)據(jù)來(lái)源

為了進(jìn)一步驗(yàn)證EBMCH算法的可行性,本文以西寧市公交數(shù)據(jù)為例,收集了截至2022年2月13日西寧市公交線路及站點(diǎn)的數(shù)據(jù),得到577個(gè)公交站點(diǎn)以及92條公交線路。基于此數(shù)據(jù)集構(gòu)建西寧市公交超網(wǎng)絡(luò)模型,站點(diǎn)表示超網(wǎng)絡(luò)中的節(jié)點(diǎn),線路表示超網(wǎng)絡(luò)中的超邊。

4.2.2 實(shí)驗(yàn)結(jié)果分析

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

表2 EBMCH排名前20的站點(diǎn)及相應(yīng)指標(biāo)

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

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

5 結(jié)論