周麗娜，常 笑，胡 楓

1.青海師范大學(xué) 計(jì)算機(jī)學(xué)院，西寧 810008

2.青海省藏文信息處理與機(jī)器翻譯重點(diǎn)實(shí)驗(yàn)室，西寧 810008

3.藏語(yǔ)智能信息處理及應(yīng)用國(guó)家重點(diǎn)實(shí)驗(yàn)室，西寧 810008

隨著網(wǎng)絡(luò)科學(xué)的蓬勃發(fā)展，人們對(duì)復(fù)雜系統(tǒng)及復(fù)雜網(wǎng)絡(luò)有了更深入的了解，現(xiàn)實(shí)世界中大多數(shù)系統(tǒng)都可以抽象為復(fù)雜網(wǎng)絡(luò)。而人們對(duì)復(fù)雜網(wǎng)絡(luò)的研究已經(jīng)從宏觀層面轉(zhuǎn)變?yōu)槲⒂^層面（節(jié)點(diǎn)、鏈路）去解釋不同網(wǎng)絡(luò)所具有的不同特征[1]。節(jié)點(diǎn)作為網(wǎng)絡(luò)中最小的單元，在不同的現(xiàn)實(shí)網(wǎng)絡(luò)中起著不同的作用。有效且高效地識(shí)別與大規(guī)模網(wǎng)絡(luò)的特定動(dòng)態(tài)相關(guān)的關(guān)鍵節(jié)點(diǎn)將使人們能夠更好地控制流行病的爆發(fā)、抑制疾病擴(kuò)散[2]、精準(zhǔn)投放商品廣告[3]、預(yù)測(cè)熱門研究成果、發(fā)現(xiàn)重要致病基因[4]、尋找恐怖分子頭目等等。因此，識(shí)別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)至關(guān)重要。

隨著信息化時(shí)代的到來(lái)，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)結(jié)構(gòu)變得復(fù)雜多樣，基于普通圖的復(fù)雜網(wǎng)絡(luò)[1，5-6]已經(jīng)不能很好地描述真實(shí)網(wǎng)絡(luò)以及復(fù)雜系統(tǒng)的各種特性，因此多數(shù)學(xué)者將視角轉(zhuǎn)向了基于超圖的超網(wǎng)絡(luò)[7-9]。目前，超網(wǎng)絡(luò)的研究大都基于超網(wǎng)絡(luò)模型的構(gòu)建及現(xiàn)實(shí)世界的超網(wǎng)絡(luò)特性研究。Wang等[10]構(gòu)建了一種超網(wǎng)絡(luò)動(dòng)態(tài)演化模型，該模型每次增加若干個(gè)新節(jié)點(diǎn)，并與原網(wǎng)絡(luò)中已存在的一個(gè)舊節(jié)點(diǎn)優(yōu)先連接生成新的超邊。胡楓等[11]給出了另一種超網(wǎng)絡(luò)演化模型，該模型的增長(zhǎng)機(jī)理與文獻(xiàn)[10]模型相對(duì)偶，并將BA網(wǎng)絡(luò)視為該模型的特例。Suo等研究了超網(wǎng)絡(luò)中信息動(dòng)態(tài)傳播問題[12]，并且根據(jù)超網(wǎng)絡(luò)的演化模型分析了供應(yīng)鏈網(wǎng)絡(luò)的演化機(jī)制[13]。郭進(jìn)利研究了非均勻超網(wǎng)絡(luò)中標(biāo)度率涌現(xiàn)問題[14]。盧文等[15]構(gòu)建了節(jié)點(diǎn)超度分布具有雙峰特性，層間采用隨機(jī)方式連接，層內(nèi)采用三種不同類型的雙層超網(wǎng)絡(luò)模型。劉勝久等[16]結(jié)合超網(wǎng)絡(luò)維數(shù)與網(wǎng)絡(luò)能量，提出了超網(wǎng)絡(luò)能量，論證了超網(wǎng)絡(luò)的超網(wǎng)絡(luò)能量與圖的網(wǎng)絡(luò)能量之間的內(nèi)在關(guān)聯(lián)，并分析了超網(wǎng)絡(luò)能量的若干性質(zhì)。馬濤等[17]構(gòu)建了基于加權(quán)超圖的產(chǎn)學(xué)研合作申請(qǐng)專利超網(wǎng)絡(luò)模型，并分析其拓?fù)浣Y(jié)構(gòu)。陸睿敏等[18]基于超網(wǎng)絡(luò)理論構(gòu)建了上海公交超網(wǎng)絡(luò)模型，分析了該模型的魯棒性，從而對(duì)城市交通規(guī)劃與設(shè)施管理具有指導(dǎo)意義。而在超網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面的研究則相對(duì)較少，利用超網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)指標(biāo)計(jì)算超網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的研究則更少。Estrada等[8]擴(kuò)展了復(fù)雜網(wǎng)絡(luò)中子圖中心性和聚類系數(shù)的定義到超網(wǎng)絡(luò)上，并用這兩種指標(biāo)識(shí)別出了三類現(xiàn)實(shí)超網(wǎng)絡(luò)中的核心節(jié)點(diǎn)。胡楓等[19]利用復(fù)合參數(shù)的方法識(shí)別出了蛋白復(fù)合物超網(wǎng)絡(luò)中的關(guān)鍵蛋白。王雨等[20]從超網(wǎng)絡(luò)角度出發(fā)研究了科研合作中的作者的重要性問題，并提出了重要度指標(biāo)D′，能夠較好地識(shí)別出科研合作超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。單而芳等[21]討論了超網(wǎng)絡(luò)中心性測(cè)度的一類方法——廣義Position值方法。孫琳等[22]基于超網(wǎng)絡(luò)理論對(duì)上海交通軌道網(wǎng)絡(luò)進(jìn)行識(shí)別關(guān)鍵節(jié)點(diǎn)的實(shí)證研究。

近年來(lái)，信息熵[23]廣泛應(yīng)用于復(fù)雜系統(tǒng)與復(fù)雜性理論，F(xiàn)ei等[24]將信息熵應(yīng)用到復(fù)雜系統(tǒng)的關(guān)鍵節(jié)點(diǎn)識(shí)別中，并取得了良好的效果。黃麗亞等[25]依據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)在K步內(nèi)可達(dá)的節(jié)點(diǎn)總數(shù)定義了K-階結(jié)構(gòu)熵，并從三個(gè)方面評(píng)價(jià)網(wǎng)絡(luò)的異構(gòu)性。胡鋼等[26]通過計(jì)算網(wǎng)絡(luò)各節(jié)點(diǎn)的鄰接度得到節(jié)點(diǎn)信息熵，利用節(jié)點(diǎn)信息熵的大小表征節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。李懂等[27]融合了度與k核迭代次數(shù)并利用熵權(quán)法計(jì)算度和k核迭代次數(shù)的權(quán)重，從而識(shí)別節(jié)點(diǎn)的重要性。王倩等[28]將軟件動(dòng)態(tài)執(zhí)行過程抽象為有向復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)模型，并結(jié)合結(jié)構(gòu)熵提出了軟件動(dòng)態(tài)執(zhí)行關(guān)鍵節(jié)點(diǎn)挖掘算法。迄今為止，針對(duì)鄰居結(jié)構(gòu)熵的研究都是基于普通圖的復(fù)雜網(wǎng)絡(luò)上的應(yīng)用研究，而缺乏基于超圖的超網(wǎng)絡(luò)上的定義及應(yīng)用研究。網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定網(wǎng)絡(luò)的功能和性質(zhì)，復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)為普通圖，即一條邊連接兩個(gè)節(jié)點(diǎn)，而超網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)為超圖，超圖中的超邊可連接任意多個(gè)節(jié)點(diǎn)，更切合現(xiàn)實(shí)網(wǎng)絡(luò)的復(fù)雜、多元、群聚特性。因此，為刻畫真實(shí)數(shù)據(jù)集的多元群組關(guān)系，以綜合視角研究復(fù)雜的現(xiàn)實(shí)系統(tǒng)，學(xué)者們將研究重點(diǎn)逐漸從復(fù)雜網(wǎng)絡(luò)轉(zhuǎn)向超網(wǎng)絡(luò)。超網(wǎng)絡(luò)分為基于網(wǎng)絡(luò)的網(wǎng)絡(luò)（supernetwork）和基于超圖的網(wǎng)絡(luò)（hypernetwork）。Estrada等最先在文獻(xiàn)[8]提出拓?fù)浣Y(jié)構(gòu)為超圖的網(wǎng)絡(luò)稱為超網(wǎng)絡(luò)（hypernetwork）。超圖是普通圖的擴(kuò)展，普通圖中的“邊”只能連接兩個(gè)節(jié)點(diǎn)，而超圖中的“超邊”可連接任意多個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)連接的超邊數(shù)量稱為節(jié)點(diǎn)的超度?；诔瑘D的超網(wǎng)絡(luò)，由于結(jié)構(gòu)簡(jiǎn)單、表示多元關(guān)系清晰明了，更適合刻畫現(xiàn)實(shí)世界的綜合、群組、多元結(jié)構(gòu)，這種獨(dú)特優(yōu)勢(shì)使其獲得越來(lái)越多的重視。因此，本文在基于超圖的超網(wǎng)絡(luò)上，分析超網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性的識(shí)別方法。網(wǎng)絡(luò)中的節(jié)點(diǎn)相互影響，只考慮度或超度值，會(huì)損失直接或間接鄰居對(duì)節(jié)點(diǎn)的影響；考慮全局節(jié)點(diǎn)會(huì)增加算法的復(fù)雜度，且效果不一定很好，因?yàn)椋?jié)點(diǎn)的重要性不僅與自身的影響力有關(guān)，還與鄰接節(jié)點(diǎn)的重要性密切相關(guān)。如在以作者為節(jié)點(diǎn)，合作發(fā)表的論文為超邊構(gòu)造的科研合作超網(wǎng)絡(luò)中，一個(gè)人的重要性與個(gè)人所發(fā)表的論文數(shù)量（即節(jié)點(diǎn)的超度值）有關(guān)，還與合作者的影響力（即鄰居節(jié)點(diǎn)的超度）有關(guān)，通常情形下，作為合作者的導(dǎo)師的影響力往往會(huì)波及個(gè)人；一個(gè)網(wǎng)頁(yè)的重要性與指向它的權(quán)威網(wǎng)頁(yè)存在重大關(guān)系等。

基于以上考慮，本文提出用鄰接結(jié)構(gòu)熵識(shí)別超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，通過研究節(jié)點(diǎn)及其直接與間接節(jié)點(diǎn)間的關(guān)系，利用節(jié)點(diǎn)信息熵刻畫不同節(jié)點(diǎn)在超網(wǎng)絡(luò)中的重要性。其優(yōu)勢(shì)在于不僅考慮了節(jié)點(diǎn)自身的性質(zhì)，也融合了鄰居節(jié)點(diǎn)的影響力，且由于該算法只利用節(jié)點(diǎn)的局部屬性，故其復(fù)雜度較低。為了驗(yàn)證此算法的適用性及正確性，本文收集了《物理學(xué)報(bào)》2012—2020年間發(fā)表的論文及作者信息，構(gòu)建了一個(gè)作者為節(jié)點(diǎn)，合作發(fā)表的論文為超邊的科研合作超網(wǎng)絡(luò)。實(shí)證分析結(jié)果表明，本文提出的基于鄰居結(jié)構(gòu)熵識(shí)別關(guān)鍵節(jié)點(diǎn)的算法可以精準(zhǔn)地識(shí)別超網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。

1 相關(guān)知識(shí)

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

超圖概念最早是Berge[29]提出的，設(shè)V={v1,v2,…,vn}是一個(gè)有限集。若ei≠φ(i=1,2,…,m)，且則稱二元關(guān)系H=(V,E)為超圖。其中V的元素稱為超圖的節(jié)點(diǎn)或頂點(diǎn)，E={e1,e2,…,em}是超圖的邊集合，集合E的元素ei稱為超圖的超邊。超圖H=(V,E)的鄰接矩陣A(H)是一個(gè)N×N的對(duì)稱方陣，其元素aij為同時(shí)包含頂點(diǎn)vi和vj的超邊數(shù)量，對(duì)角線元素為0。關(guān)聯(lián)矩陣B(H)是一個(gè)N×M的矩陣，如果頂點(diǎn)vi包含在超邊ej中，則bij=1，否則為0。超網(wǎng)絡(luò)中節(jié)點(diǎn)度等同于普通圖中度的定義，即節(jié)點(diǎn)的連邊數(shù)，即，簡(jiǎn)記為ki。節(jié)點(diǎn)超度是包含該節(jié)點(diǎn)vi的超邊數(shù)屬于同一條超邊中的節(jié)點(diǎn)為超圖量，即中的鄰接節(jié)點(diǎn)。Estrada等[8]提出了超網(wǎng)絡(luò)中子圖中心性的計(jì)算公式，即其中，λj是超網(wǎng)絡(luò)H中鄰接矩陣A的特征值，U=(uij)N×N是一個(gè)正交矩陣，且每一列都是特征值λj對(duì)應(yīng)的特征向量。

1.2 信息熵

信息熵于1948年由Shannon提出，信息熵的優(yōu)點(diǎn)是能夠從系統(tǒng)樣本點(diǎn)的不確定性出發(fā)，利用概率與統(tǒng)計(jì)方法，表征樣本空間所體現(xiàn)的系統(tǒng)無(wú)序化程度，該方法能夠很好地衡量網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。

1.3 網(wǎng)絡(luò)結(jié)構(gòu)熵

熵是系統(tǒng)的一種無(wú)序度量，用來(lái)描述一個(gè)系統(tǒng)內(nèi)所有元素的狀態(tài)總和。網(wǎng)絡(luò)熵主要從網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)信息收容能力（即網(wǎng)絡(luò)能夠收取容納信息規(guī)模的能力）來(lái)定義。吳俊等[30]利用網(wǎng)絡(luò)節(jié)點(diǎn)的度與所有節(jié)點(diǎn)度值總和的比值來(lái)度量節(jié)點(diǎn)的差異性，提出了基于網(wǎng)絡(luò)節(jié)點(diǎn)度來(lái)定義網(wǎng)絡(luò)節(jié)點(diǎn)的重要性程度，最后通過網(wǎng)絡(luò)節(jié)點(diǎn)的重要性程度定義網(wǎng)絡(luò)結(jié)構(gòu)熵。

定義1假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)vi的度為ki，則其重要度可以定義為[30]：

對(duì)于ki=0的節(jié)點(diǎn)不作考慮。定義網(wǎng)絡(luò)結(jié)構(gòu)熵[30]：

1.4 鄰接信息熵

定義2（節(jié)點(diǎn)鄰居概率函數(shù)）為了描述不同節(jié)點(diǎn)的鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的影響力大小，節(jié)點(diǎn)鄰居概率函數(shù)定義如下：

其中，ki為節(jié)點(diǎn)vi的度值，Qi為節(jié)點(diǎn)vi的鄰接度，通過以上改進(jìn)，在復(fù)雜網(wǎng)絡(luò)中，重要節(jié)點(diǎn)的識(shí)別計(jì)算公式如下：

其中，pi為節(jié)點(diǎn)vi的概率函數(shù)，pj為節(jié)點(diǎn)vj的概率函數(shù)，Γi為節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)的集合，Γj為節(jié)點(diǎn)vj鄰居節(jié)點(diǎn)的集合。

2 鄰接結(jié)構(gòu)熵

超網(wǎng)絡(luò)中節(jié)點(diǎn)超度只能反映節(jié)點(diǎn)被包含的超邊的數(shù)量，不能很好地反映節(jié)點(diǎn)與其他間接鄰居節(jié)點(diǎn)的連接情況，為此，本文引入節(jié)點(diǎn)鄰接超度的定義，在此基礎(chǔ)上給出超網(wǎng)絡(luò)中的鄰接結(jié)構(gòu)熵概念，通過鄰接結(jié)構(gòu)熵值識(shí)別超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

定義3（鄰接超度）為了更準(zhǔn)確地反映超網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的影響，通過鄰接節(jié)點(diǎn)的重要性確定目標(biāo)節(jié)點(diǎn)的地位。目標(biāo)節(jié)點(diǎn)的鄰接超度定義如下：

其中，d H(j)為節(jié)點(diǎn)i的超度值，R(i)為節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)集合。

定義4（重要度函數(shù)）為了描述超網(wǎng)絡(luò)中不同節(jié)點(diǎn)在其鄰居節(jié)點(diǎn)中被選中的可能性大小，定義超網(wǎng)絡(luò)中節(jié)點(diǎn)的重要度函數(shù)：

其中，DH(i)為超網(wǎng)絡(luò)中節(jié)點(diǎn)i的鄰接超度。

定義5（鄰接結(jié)構(gòu)熵）結(jié)合鄰接超度與網(wǎng)絡(luò)結(jié)構(gòu)熵定義，將超網(wǎng)絡(luò)中計(jì)算單個(gè)節(jié)點(diǎn)vi的鄰接結(jié)構(gòu)熵定義如下：

其中，PH(i)表示超網(wǎng)絡(luò)中節(jié)點(diǎn)的重要度函數(shù)。

根據(jù)以上定義可知，超網(wǎng)絡(luò)中的鄰接結(jié)構(gòu)熵不僅與節(jié)點(diǎn)的超度有關(guān)，還與鄰接節(jié)點(diǎn)的超度有關(guān)。若節(jié)點(diǎn)包含在多條超邊（即多個(gè)團(tuán)隊(duì)或族內(nèi)）中，其重要性不僅跟自身有關(guān)，也與其鄰接節(jié)點(diǎn)（即團(tuán)隊(duì)成員）的重要性有關(guān)。利用鄰接結(jié)構(gòu)熵值的大小，表示節(jié)點(diǎn)在超網(wǎng)絡(luò)中的重要性。鄰接結(jié)構(gòu)熵值越大，節(jié)點(diǎn)越重要，表明該節(jié)點(diǎn)隱含的信息的價(jià)值越高。

本文實(shí)例為Estrada等在文獻(xiàn)[8]中的競(jìng)爭(zhēng)復(fù)雜網(wǎng)絡(luò)與超網(wǎng)絡(luò)對(duì)比圖驗(yàn)證本文算法的正確性。在競(jìng)爭(zhēng)網(wǎng)中，節(jié)點(diǎn)表示物種而鏈表示物種之間的營(yíng)養(yǎng)關(guān)系。如圖1所示的競(jìng)爭(zhēng)網(wǎng)絡(luò)及對(duì)應(yīng)的競(jìng)爭(zhēng)超網(wǎng)絡(luò)圖[8]。在競(jìng)爭(zhēng)網(wǎng)中，當(dāng)且僅當(dāng)聯(lián)系的物種在食物網(wǎng)中有共同的獵物時(shí)，兩點(diǎn)直接連邊。在競(jìng)爭(zhēng)圖中，僅僅知道兩個(gè)聯(lián)系的物種之間有共同的獵物，但并不知道為共同獵物競(jìng)爭(zhēng)的整個(gè)物種群的構(gòu)成情況。在競(jìng)爭(zhēng)超網(wǎng)絡(luò)中，節(jié)點(diǎn)為物種，競(jìng)爭(zhēng)同一獵物的物種在同一條超邊中，節(jié)點(diǎn)所競(jìng)爭(zhēng)的獵物與鄰居節(jié)點(diǎn)競(jìng)爭(zhēng)的獵物一目了然。該競(jìng)爭(zhēng)超網(wǎng)絡(luò)由8個(gè)節(jié)點(diǎn)和3條超邊組成，即8個(gè)物種競(jìng)爭(zhēng)3種獵物，競(jìng)爭(zhēng)關(guān)系明確清晰。節(jié)點(diǎn)的重要性也易識(shí)別。表1為此超網(wǎng)絡(luò)超度、子圖中心性及本文算法提出的鄰接結(jié)構(gòu)熵的排序結(jié)果。

圖1 競(jìng)爭(zhēng)網(wǎng)絡(luò)與競(jìng)爭(zhēng)超網(wǎng)絡(luò)Fig.1 Competitive network and competitive hypernetwork

表1 競(jìng)爭(zhēng)超網(wǎng)絡(luò)各指標(biāo)Table 1 Index of competitive hypernetwork

由表1知，超度不能很好地區(qū)分各節(jié)點(diǎn)的重要性，根據(jù)鄰接信息熵、子圖中心性及鄰接結(jié)構(gòu)熵知，節(jié)點(diǎn)10是此競(jìng)爭(zhēng)超網(wǎng)絡(luò)的重要節(jié)點(diǎn)。其子圖中心性和鄰接結(jié)構(gòu)熵的值均遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)2。節(jié)點(diǎn)10代表的物種發(fā)生在競(jìng)爭(zhēng)數(shù)量最多的群體E1和E3中，分別有5個(gè)和4個(gè)競(jìng)爭(zhēng)者，又因?yàn)樗谧咏Y(jié)構(gòu)中參與同時(shí)涉及競(jìng)爭(zhēng)群和外部群的物種，這使得此物種難以生存。排名第二的關(guān)鍵節(jié)點(diǎn)是節(jié)點(diǎn)2，它參與E1和E2組；接下來(lái)是節(jié)點(diǎn)4和5，它們參加E2和E3群體的競(jìng)爭(zhēng)。

基于鄰接結(jié)構(gòu)熵計(jì)算節(jié)點(diǎn)重要度的算法如下：

步驟1對(duì)于超網(wǎng)絡(luò)H=(V,E)，根據(jù)其鄰接矩陣A(H)計(jì)算給定超網(wǎng)絡(luò)H中節(jié)點(diǎn)i的超度d H(i)及鄰接超度

步驟2按照重要度函數(shù)式計(jì)算概率函數(shù)PH(i)。

步驟3根據(jù)式，計(jì)算節(jié)點(diǎn)i的鄰接結(jié)構(gòu)熵；重復(fù)步驟2至3，直到計(jì)算出所有節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵。

步驟4根據(jù)各節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵大小對(duì)節(jié)點(diǎn)進(jìn)行排序。

超網(wǎng)絡(luò)H中，節(jié)點(diǎn)個(gè)數(shù)為V，超邊數(shù)量為E，文獻(xiàn)[8]提出的超網(wǎng)絡(luò)中子圖中心性的時(shí)間復(fù)雜度為O(V2)。復(fù)雜網(wǎng)絡(luò)中，文獻(xiàn)[30]利用節(jié)點(diǎn)的度計(jì)算網(wǎng)絡(luò)結(jié)構(gòu)熵的時(shí)間復(fù)雜度為O(V)，文獻(xiàn)[28]利用節(jié)點(diǎn)及節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度計(jì)算鄰接信息熵的時(shí)間復(fù)雜度為O(V2)。本文算法利用公式（4）、公式（5）計(jì)算超網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵，算法時(shí)間復(fù)雜度為O(V)。本文算法相比其他算法，時(shí)間復(fù)雜度更優(yōu)。

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

3.1 復(fù)雜網(wǎng)絡(luò)與超網(wǎng)絡(luò)比較

為了比較鄰接結(jié)構(gòu)熵在復(fù)雜網(wǎng)絡(luò)和超網(wǎng)絡(luò)中的異同性，本文在Estrada文獻(xiàn)[8]的競(jìng)爭(zhēng)網(wǎng)絡(luò)和競(jìng)爭(zhēng)超網(wǎng)絡(luò)中進(jìn)行鄰接結(jié)構(gòu)熵的重要度比對(duì)，并與網(wǎng)絡(luò)結(jié)構(gòu)熵和鄰接信息熵進(jìn)行比較。結(jié)果如圖2所示。

圖2 復(fù)雜網(wǎng)絡(luò)和超網(wǎng)絡(luò)的熵值Fig.2 Entropy of complex networks and hypernetwork

從圖2可知，由復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)熵識(shí)別出節(jié)點(diǎn)10為重要節(jié)點(diǎn)，與超網(wǎng)絡(luò)的鄰接結(jié)構(gòu)熵識(shí)別出的關(guān)鍵節(jié)點(diǎn)相同。但是，由于復(fù)雜網(wǎng)絡(luò)中各節(jié)點(diǎn)的度值大致相同，導(dǎo)致根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)熵與鄰接信息熵得到的節(jié)點(diǎn)的粗?；潭容^高，難以區(qū)分度值相同的節(jié)點(diǎn)的重要性。而超網(wǎng)絡(luò)中也存在某些節(jié)點(diǎn)超度值相同的情況，但超網(wǎng)絡(luò)的鄰接結(jié)構(gòu)熵則能夠較好地區(qū)分出各節(jié)點(diǎn)的重要性。

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

為了進(jìn)一步驗(yàn)證該算法的正確性，本文以《物理學(xué)報(bào)》為例，選取發(fā)表時(shí)間為2012年1月1日—2020年9月10日的文獻(xiàn)記錄。其中涵蓋了16 158位不同的作者撰寫的5 338篇論文，基于此數(shù)據(jù)集構(gòu)建科研合作超網(wǎng)絡(luò)模型，該模型包含16 158個(gè)作者節(jié)點(diǎn)和5 338篇論文超邊。其中獨(dú)立發(fā)文的作者有138人，僅占2.5%，故大部分論文由多位作者共同合作完成，且絕大多數(shù)論文由3～6個(gè)作者合作完成。

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

將本文算法應(yīng)用到上述超網(wǎng)絡(luò)中，得到各個(gè)作者的鄰接結(jié)構(gòu)熵如圖3（a）所示，圖3（b）為各作者的超度值，即作者發(fā)表論文的數(shù)量。橫軸表示節(jié)點(diǎn)編號(hào)；縱軸分別表示節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵和節(jié)點(diǎn)超度值。由圖3可以看出，大部分節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵和超度值均處于區(qū)間[1，5]。由此可知，大部分作者在其領(lǐng)域內(nèi)的影響力較低，并且大部分作者僅發(fā)表了1～5篇論文。

圖3 所有節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵及超度值Fig.3 Adjacent structure entropy and hyper-degree value of all nodes

由圖3知，各節(jié)點(diǎn)所處的位置相對(duì)分散，層次分明，顏色越深的地方，節(jié)點(diǎn)分布越密集。從圖3（a）可知，節(jié)點(diǎn)9941的鄰接結(jié)構(gòu)熵值遠(yuǎn)遠(yuǎn)高于其他節(jié)點(diǎn)，此節(jié)點(diǎn)為超網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。從圖3（b）可以看出，節(jié)點(diǎn)所處位置分布規(guī)律，且均勻地分布在超度值為1～5的位置，然而超度值相同的節(jié)點(diǎn)較多，這類節(jié)點(diǎn)重要性相同，故超度的粗粒度高于鄰接結(jié)構(gòu)熵。因此，鄰接結(jié)構(gòu)熵能夠有效地識(shí)別出超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。通過對(duì)這16 158位作者的鄰接結(jié)構(gòu)熵進(jìn)行排序，得到排名結(jié)果前20的作者及其相應(yīng)指標(biāo)，結(jié)果見表2。由表2知，節(jié)點(diǎn)9941的鄰接結(jié)構(gòu)熵最為突出，為31.83，屬于重要作者，是該科研合作超網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。通過對(duì)節(jié)點(diǎn)的超度進(jìn)行排序，得到超度值最大的節(jié)點(diǎn)為節(jié)點(diǎn)4057，其超度值為22；但其節(jié)點(diǎn)度為77，表明與節(jié)點(diǎn)4057合作的作者的超度值均較大，因此，他的鄰接超度值較大。通過分析作者自身發(fā)文量占與他合作的作者的發(fā)文量的比例，得出此比例小于節(jié)點(diǎn)9941，故其鄰接結(jié)構(gòu)熵小于節(jié)點(diǎn)9941的鄰接結(jié)構(gòu)熵。因此，節(jié)點(diǎn)4057再次參與合作論文的可能性相對(duì)較小。而節(jié)點(diǎn)9941的合作作者人數(shù)為102，相比較于節(jié)點(diǎn)4057較多，但其鄰接超度較小，故再次邀請(qǐng)節(jié)點(diǎn)9941參與合作論文的可能性較大。節(jié)點(diǎn)9941發(fā)表的論文中署名為第一作者的論文偏多，而節(jié)點(diǎn)4057的署名均位于末尾，因此，節(jié)點(diǎn)9941共同合作發(fā)表論文的次數(shù)比節(jié)點(diǎn)4057的可能性大，節(jié)點(diǎn)9941更有合作潛力。

表2 鄰接結(jié)構(gòu)熵排名前20的作者及相應(yīng)指標(biāo)Table 2 Top 20 authors of adjacency structure entropy and their corresponding indicators

排名第二的關(guān)鍵節(jié)點(diǎn)是節(jié)點(diǎn)10350，其鄰接結(jié)構(gòu)熵為26.48，超度值排名第8，該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)為81，位于第14位。其中，該作者節(jié)點(diǎn)的大多數(shù)論文由3～5名作者共同合作完成，此節(jié)點(diǎn)與鄰接結(jié)構(gòu)熵排名第一的節(jié)點(diǎn)9941生成一條超邊。此節(jié)點(diǎn)的鄰居節(jié)點(diǎn)超度值較小，選擇該作者共同合作論文的機(jī)率較大，故此節(jié)點(diǎn)的鄰接結(jié)構(gòu)熵排在第二位。進(jìn)一步，比對(duì)超度、鄰接結(jié)構(gòu)熵、節(jié)點(diǎn)度的排名情況，如圖4所示鄰接結(jié)構(gòu)熵排名前20名作者的度、超度。

圖4 作者各指標(biāo)的排名Fig.4 Ranking of each index

圖4橫軸表示作者，縱軸為三個(gè)指標(biāo)的名次排名。方塊表示鄰接結(jié)構(gòu)熵，圓圈表示超度，三角表示節(jié)點(diǎn)度。在此超網(wǎng)絡(luò)中，超度反映作者的發(fā)文量，鄰接結(jié)構(gòu)熵反映該作者再次發(fā)表論文的可能性，也就是作者在其領(lǐng)域內(nèi)的影響力，作者合作發(fā)表論文的發(fā)展?jié)摿?，而?jié)點(diǎn)度反映作者的合作人數(shù)。根據(jù)節(jié)點(diǎn)度排名，排名第一的節(jié)點(diǎn)5169，其節(jié)點(diǎn)度為118，但其超度值僅僅為9，其鄰接結(jié)構(gòu)熵值排在第5位。該作者發(fā)表的論文中有一篇論文《中國(guó)散裂中子源反角白光中子束流參數(shù)的初步測(cè)量》與86位作者共同合作完成，導(dǎo)致該作者的節(jié)點(diǎn)度最大，因此，僅利用節(jié)點(diǎn)度衡量網(wǎng)絡(luò)節(jié)點(diǎn)的重要性并不準(zhǔn)確。

此數(shù)據(jù)集收集了2012—2020年間各個(gè)領(lǐng)域、各個(gè)方向的論文及作者，故識(shí)別的關(guān)鍵作者共同發(fā)表論文、形成良好的交流環(huán)境并形成對(duì)應(yīng)領(lǐng)域內(nèi)團(tuán)體的可能性很小，但識(shí)別出的重要作者均為各領(lǐng)域內(nèi)具有較大影響力的關(guān)鍵人物。例如，鄰接結(jié)構(gòu)熵排名前三位作者的研究領(lǐng)域如下，節(jié)點(diǎn)9941的H指數(shù)為46，研究領(lǐng)域是攝影測(cè)量與遙感；節(jié)點(diǎn)10350的H指數(shù)為48，研究領(lǐng)域是環(huán)境工程；節(jié)點(diǎn)4075的H指數(shù)為43，研究領(lǐng)域是光學(xué)。

最后，利用準(zhǔn)確性評(píng)價(jià)指標(biāo)AUC指標(biāo)，從整體上衡量算法的準(zhǔn)確度。對(duì)網(wǎng)絡(luò)中各節(jié)點(diǎn)的重要性排序，當(dāng)節(jié)點(diǎn)分配到不同的排序值越多，算法劃分節(jié)點(diǎn)重要性更清晰。即AUC值越大，算法準(zhǔn)確性越高。

表3為超度和鄰接結(jié)構(gòu)熵的AUC指標(biāo)。由表3可知，鄰接結(jié)構(gòu)熵的AUC指標(biāo)略高于超度的AUC指標(biāo)，故進(jìn)一步驗(yàn)證了鄰接結(jié)構(gòu)熵可以高效、準(zhǔn)確地識(shí)別超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

表3 AUC指標(biāo)Table 3 AUC index

4 結(jié)語(yǔ)

識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)不僅能夠分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，還能預(yù)測(cè)節(jié)點(diǎn)的實(shí)際影響力。而網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性不僅與節(jié)點(diǎn)自身性質(zhì)有關(guān)，也與其鄰居節(jié)點(diǎn)的重要性有關(guān)。本文結(jié)合鄰接超度與網(wǎng)絡(luò)結(jié)構(gòu)熵，提出了基于超網(wǎng)絡(luò)的鄰接結(jié)構(gòu)熵，用于識(shí)別超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。并將此指標(biāo)應(yīng)用于競(jìng)爭(zhēng)超網(wǎng)絡(luò)，準(zhǔn)確地得到了該超網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。其次，分析比較復(fù)雜網(wǎng)絡(luò)與超網(wǎng)絡(luò)，得到的關(guān)鍵節(jié)點(diǎn)均為節(jié)點(diǎn)10。最后，本文從知網(wǎng)收集了《物理學(xué)報(bào)》2012—2020年間的作者及其發(fā)表的論文，構(gòu)建了科研合作超網(wǎng)絡(luò)，并將超網(wǎng)絡(luò)中的鄰接結(jié)構(gòu)熵應(yīng)用于該數(shù)據(jù)集中，實(shí)驗(yàn)分析證明，該算法能夠準(zhǔn)確高效地識(shí)別出超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。本文為今后預(yù)測(cè)超網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)、識(shí)別有影響力的學(xué)者，以及研究超網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)提供了一種行之有效的方法。