利用鄰接結構熵確定超網絡關鍵節點

周麗娜，常 笑，胡 楓

1.青海師范大學 計算機學院，西寧 810008

2.青海省藏文信息處理與機器翻譯重點實驗室，西寧 810008

3.藏語智能信息處理及應用國家重點實驗室，西寧 810008

隨著網絡科學的蓬勃發展，人們對復雜系統及復雜網絡有了更深入的了解，現實世界中大多數系統都可以抽象為復雜網絡。而人們對復雜網絡的研究已經從宏觀層面轉變為微觀層面（節點、鏈路）去解釋不同網絡所具有的不同特征[1]。節點作為網絡中最小的單元，在不同的現實網絡中起著不同的作用。有效且高效地識別與大規模網絡的特定動態相關的關鍵節點將使人們能夠更好地控制流行病的爆發、抑制疾病擴散[2]、精準投放商品廣告[3]、預測熱門研究成果、發現重要致病基因[4]、尋找恐怖分子頭目等等。因此，識別網絡中的重要節點至關重要。

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

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

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

1 相關知識

1.1 超網絡相關概念

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

1.2 信息熵

信息熵于1948年由Shannon提出，信息熵的優點是能夠從系統樣本點的不確定性出發，利用概率與統計方法，表征樣本空間所體現的系統無序化程度，該方法能夠很好地衡量網絡節點的重要性。

1.3 網絡結構熵

熵是系統的一種無序度量，用來描述一個系統內所有元素的狀態總和。網絡熵主要從網絡結構和網絡信息收容能力（即網絡能夠收取容納信息規模的能力）來定義。吳俊等[30]利用網絡節點的度與所有節點度值總和的比值來度量節點的差異性，提出了基于網絡節點度來定義網絡節點的重要性程度，最后通過網絡節點的重要性程度定義網絡結構熵。

定義1假設網絡中節點vi的度為ki，則其重要度可以定義為[30]：

對于ki=0的節點不作考慮。定義網絡結構熵[30]：

1.4 鄰接信息熵

定義2（節點鄰居概率函數）為了描述不同節點的鄰居節點對節點的影響力大小，節點鄰居概率函數定義如下：

其中，ki為節點vi的度值，Qi為節點vi的鄰接度，通過以上改進，在復雜網絡中，重要節點的識別計算公式如下：

其中，pi為節點vi的概率函數，pj為節點vj的概率函數，Γi為節點vi鄰居節點的集合，Γj為節點vj鄰居節點的集合。

2 鄰接結構熵

超網絡中節點超度只能反映節點被包含的超邊的數量，不能很好地反映節點與其他間接鄰居節點的連接情況，為此，本文引入節點鄰接超度的定義，在此基礎上給出超網絡中的鄰接結構熵概念，通過鄰接結構熵值識別超網絡中的關鍵節點。

定義3（鄰接超度）為了更準確地反映超網絡中鄰居節點對該節點的影響，通過鄰接節點的重要性確定目標節點的地位。目標節點的鄰接超度定義如下：

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

定義4（重要度函數）為了描述超網絡中不同節點在其鄰居節點中被選中的可能性大小，定義超網絡中節點的重要度函數：

其中，DH(i)為超網絡中節點i的鄰接超度。

定義5（鄰接結構熵）結合鄰接超度與網絡結構熵定義，將超網絡中計算單個節點vi的鄰接結構熵定義如下：

其中，PH(i)表示超網絡中節點的重要度函數。

根據以上定義可知，超網絡中的鄰接結構熵不僅與節點的超度有關，還與鄰接節點的超度有關。若節點包含在多條超邊（即多個團隊或族內）中，其重要性不僅跟自身有關，也與其鄰接節點（即團隊成員）的重要性有關。利用鄰接結構熵值的大小，表示節點在超網絡中的重要性。鄰接結構熵值越大，節點越重要，表明該節點隱含的信息的價值越高。

本文實例為Estrada等在文獻[8]中的競爭復雜網絡與超網絡對比圖驗證本文算法的正確性。在競爭網中，節點表示物種而鏈表示物種之間的營養關系。如圖1所示的競爭網絡及對應的競爭超網絡圖[8]。在競爭網中，當且僅當聯系的物種在食物網中有共同的獵物時，兩點直接連邊。在競爭圖中，僅僅知道兩個聯系的物種之間有共同的獵物，但并不知道為共同獵物競爭的整個物種群的構成情況。在競爭超網絡中，節點為物種，競爭同一獵物的物種在同一條超邊中，節點所競爭的獵物與鄰居節點競爭的獵物一目了然。該競爭超網絡由8個節點和3條超邊組成，即8個物種競爭3種獵物，競爭關系明確清晰。節點的重要性也易識別。表1為此超網絡超度、子圖中心性及本文算法提出的鄰接結構熵的排序結果。

圖1 競爭網絡與競爭超網絡Fig.1 Competitive network and competitive hypernetwork

表1 競爭超網絡各指標Table 1 Index of competitive hypernetwork

由表1知，超度不能很好地區分各節點的重要性，根據鄰接信息熵、子圖中心性及鄰接結構熵知，節點10是此競爭超網絡的重要節點。其子圖中心性和鄰接結構熵的值均遠遠大于節點2。節點10代表的物種發生在競爭數量最多的群體E1和E3中，分別有5個和4個競爭者，又因為它在子結構中參與同時涉及競爭群和外部群的物種，這使得此物種難以生存。排名第二的關鍵節點是節點2，它參與E1和E2組；接下來是節點4和5，它們參加E2和E3群體的競爭。

基于鄰接結構熵計算節點重要度的算法如下：

步驟1對于超網絡H=(V,E)，根據其鄰接矩陣A(H)計算給定超網絡H中節點i的超度d H(i)及鄰接超度

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

步驟3根據式，計算節點i的鄰接結構熵；重復步驟2至3，直到計算出所有節點的鄰接結構熵。

步驟4根據各節點的鄰接結構熵大小對節點進行排序。

超網絡H中，節點個數為V，超邊數量為E，文獻[8]提出的超網絡中子圖中心性的時間復雜度為O(V2)。復雜網絡中，文獻[30]利用節點的度計算網絡結構熵的時間復雜度為O(V)，文獻[28]利用節點及節點的鄰居節點的度計算鄰接信息熵的時間復雜度為O(V2)。本文算法利用公式（4）、公式（5）計算超網絡中每個節點的鄰接結構熵，算法時間復雜度為O(V)。本文算法相比其他算法，時間復雜度更優。

3 實驗結果與分析

3.1 復雜網絡與超網絡比較

為了比較鄰接結構熵在復雜網絡和超網絡中的異同性，本文在Estrada文獻[8]的競爭網絡和競爭超網絡中進行鄰接結構熵的重要度比對，并與網絡結構熵和鄰接信息熵進行比較。結果如圖2所示。

圖2 復雜網絡和超網絡的熵值Fig.2 Entropy of complex networks and hypernetwork

從圖2可知，由復雜網絡的網絡結構熵識別出節點10為重要節點，與超網絡的鄰接結構熵識別出的關鍵節點相同。但是，由于復雜網絡中各節點的度值大致相同，導致根據網絡結構熵與鄰接信息熵得到的節點的粗粒化程度較高，難以區分度值相同的節點的重要性。而超網絡中也存在某些節點超度值相同的情況，但超網絡的鄰接結構熵則能夠較好地區分出各節點的重要性。

3.2 數據來源

為了進一步驗證該算法的正確性，本文以《物理學報》為例，選取發表時間為2012年1月1日—2020年9月10日的文獻記錄。其中涵蓋了16 158位不同的作者撰寫的5 338篇論文，基于此數據集構建科研合作超網絡模型，該模型包含16 158個作者節點和5 338篇論文超邊。其中獨立發文的作者有138人，僅占2.5%，故大部分論文由多位作者共同合作完成，且絕大多數論文由3～6個作者合作完成。

3.3 實驗結果分析

將本文算法應用到上述超網絡中，得到各個作者的鄰接結構熵如圖3（a）所示，圖3（b）為各作者的超度值，即作者發表論文的數量。橫軸表示節點編號；縱軸分別表示節點的鄰接結構熵和節點超度值。由圖3可以看出，大部分節點的鄰接結構熵和超度值均處于區間[1，5]。由此可知，大部分作者在其領域內的影響力較低，并且大部分作者僅發表了1～5篇論文。

圖3 所有節點的鄰接結構熵及超度值Fig.3 Adjacent structure entropy and hyper-degree value of all nodes

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

表2 鄰接結構熵排名前20的作者及相應指標Table 2 Top 20 authors of adjacency structure entropy and their corresponding indicators

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

圖4 作者各指標的排名Fig.4 Ranking of each index

圖4橫軸表示作者，縱軸為三個指標的名次排名。方塊表示鄰接結構熵，圓圈表示超度，三角表示節點度。在此超網絡中，超度反映作者的發文量，鄰接結構熵反映該作者再次發表論文的可能性，也就是作者在其領域內的影響力，作者合作發表論文的發展潛力，而節點度反映作者的合作人數。根據節點度排名，排名第一的節點5169，其節點度為118，但其超度值僅僅為9，其鄰接結構熵值排在第5位。該作者發表的論文中有一篇論文《中國散裂中子源反角白光中子束流參數的初步測量》與86位作者共同合作完成，導致該作者的節點度最大，因此，僅利用節點度衡量網絡節點的重要性并不準確。

此數據集收集了2012—2020年間各個領域、各個方向的論文及作者，故識別的關鍵作者共同發表論文、形成良好的交流環境并形成對應領域內團體的可能性很小，但識別出的重要作者均為各領域內具有較大影響力的關鍵人物。例如，鄰接結構熵排名前三位作者的研究領域如下，節點9941的H指數為46，研究領域是攝影測量與遙感；節點10350的H指數為48，研究領域是環境工程；節點4075的H指數為43，研究領域是光學。

最后，利用準確性評價指標AUC指標，從整體上衡量算法的準確度。對網絡中各節點的重要性排序，當節點分配到不同的排序值越多，算法劃分節點重要性更清晰。即AUC值越大，算法準確性越高。

表3為超度和鄰接結構熵的AUC指標。由表3可知，鄰接結構熵的AUC指標略高于超度的AUC指標，故進一步驗證了鄰接結構熵可以高效、準確地識別超網絡中的關鍵節點。

表3 AUC指標Table 3 AUC index

4 結語

識別網絡中的關鍵節點不僅能夠分析網絡的拓撲結構，還能預測節點的實際影響力。而網絡中節點的重要性不僅與節點自身性質有關，也與其鄰居節點的重要性有關。本文結合鄰接超度與網絡結構熵，提出了基于超網絡的鄰接結構熵，用于識別超網絡中的關鍵節點。并將此指標應用于競爭超網絡，準確地得到了該超網絡的關鍵節點。其次，分析比較復雜網絡與超網絡，得到的關鍵節點均為節點10。最后，本文從知網收集了《物理學報》2012—2020年間的作者及其發表的論文，構建了科研合作超網絡，并將超網絡中的鄰接結構熵應用于該數據集中，實驗分析證明，該算法能夠準確高效地識別出超網絡中的關鍵節點。本文為今后預測超網絡中的關鍵節點、識別有影響力的學者，以及研究超網絡拓撲結構提供了一種行之有效的方法。