基于圖注意力機制的復雜網絡關鍵節點識別

中圖分類號：0157.5 文獻標識碼：A

Abstract：This study aims to address the problem of vital nodes identification in complex networks using graph attention mechanism. This paper integrates both node's virus transmissibility and structural impact，constructing training labels on the generated network to learn node importance through a graph attention network model. Experimental results demonstrate the excellence of this algorithm in two critical tasks： influence maximization and immune isolation.

Keywords： vital nodes identification; complex networks;influence maximization; virus transmission

0 引言

復雜網絡是一種由大量節點和連邊構成的復雜系統，具有自組織、自相似、小世界等特征，能夠描述許多自然界和人工系統中的現象和規律[1]。復雜網絡中的節點并不是等同或等價的，有些節點由于其位置、功能或連接方式的不同，對網絡的結構和動力學行為具有更大的影響力，這些節點被稱為關鍵節點[2]。

關鍵節點識別是復雜網絡研究的重要內容之一，對于理解和控制復雜網絡具有重要的理論意義和實際應用價值。例如在社交網絡中，識別關鍵節點可以幫助進行有效的信息傳播[3]、輿情監控和社會影響力分析[4];在生物網絡中，識別關鍵節點可以幫助發現重要的基因、蛋白質或代謝物，從而揭示生命系統的功能和機制[5];在交通網絡中，識別關鍵節點可以幫助優化路線設計、提高運輸效率和保障網絡安全[6]。

復雜網絡關鍵節點識別方法主要涵蓋了網絡結構特征，可以劃分為兩大類：1）基于鄰域結構的方法：這類方法依賴于節點的局部信息來評估其重要性，包括度中心性（DC）[]和 PageRank 算法[8]等。然而這些方法往往忽略了周圍節點和節點所處網絡位置對其重要性的影響，可能導致識別效果不盡如人意。為了克服這一限制，Zhu等[9]提出了改進的PageRank算法，該算法融合了全局信息，用以識別電網中的關鍵節點;2）基于全局結構的方法：這類方法從整個網絡的角度來評估節點重要性，包括緊密中心性（CC）[10]和介數中心性（BC）[11]等。然而，這些方法的計算復雜度相對較高，不適用于大規模的網絡。

此外，隨著人工智能等領域的不斷發展，機器學習逐漸成為關鍵節點識別新的方向。其能以更高的精度分析復雜網絡特征并適應不同的網絡結構。例如 Zhang 等[12]構建了NIRM模型，改模型利用圖注意力網絡（GraphAttention Networks，GAT）[13]來評估節點鄰域內節點特征對網絡穩定性的影響，以識別某一實際網絡中的關鍵節點集合;Grassia等[14]采用窮舉法來尋找最優的網絡節點集，同時利用GAT和節點特征，挖掘盡可能少的節點在最大程度上瓦解整個網絡。上述方法分別基于不同算法來衡量節點的重要性，但仍然存在一些不足之處：1）真實網絡結構復雜多樣，部分方法僅考慮網絡局部結構，忽略了全局結構的影響;2）使用窮舉法來尋找對網絡影響最大的節點集以用于機器學習，其計算復雜度較高;3）方法泛用性較低，例如在傳染病網絡中，受病毒傳播能力影響較大的節點單靠網絡結構的方法可能會導致識別的不準確。

針對上述問題，本文提出了一種基于圖注意力機制的關鍵節點識別模型（Vital Nodes Identification Modelbased on Attntion mechanism，VNIA）。該模型具有以下特點：1）以全局角度綜合節點傳播能力和結構影響力；2）利用增強 K-Shell算法來平衡鄰居節點和遠距離節點的影響，避免過度依賴局部信息;3）在人工生成網絡中模擬病毒傳播過程，并利用“消息傳遞”[15]思想以降低標簽獲取的時間復雜度;4）通過機器學習方法，將注意力機制和節點拓撲特征相結合，構建關鍵節點識別模型，并在多種網絡上進行訓練。

1模型介紹

為了改進傳統關鍵節點識別算法的不足并實現在網絡中最大化影響范圍的目標。本文構建了一種新的訓練標簽度量方法，采用機器學習的方式高效地識別網絡中的關鍵節點，總體框架如圖1所示。該模型由3個模塊構成：1）構建訓練標簽：該模塊包括兩部分：（1）a傳播能力分數：通過模擬SIR傳染病過程，結合“消息傳遞\"思想來表示節點傳播能力；（2）b結構影響力分數：利用增強K-Shell算法，充分考慮節點局部和全局結構信息綜合衡量節點重要性程度；2）特征學習：該模塊利用圖注意力網絡（GAT），動態地聚合不同鄰居節點中對病毒傳播有貢獻的向量化拓撲特征。同時，也考慮了全局影響，以獲得將鄰居節點和次鄰節點，節點和全局節點融合在一起的節點信息;3）挑選關鍵節點集：該模塊涉及比較不同節點選擇算法，以應對各種實際應用場景的需求，如最大化網絡影響能力等。

1.1 構建訓練標簽

1.1.1節點傳播能力度量

節點的重要性與其傳播能力密切相關，為描述節點的傳播能力，本文采用了經典SIR傳染病模型來模擬病毒傳播[16]。該模型假設將人群分為三個類別：S（Susceptible）-易感者，I（Infected）-感染者和R（Recovered）-恢復者。在SIR模擬中，節點狀態變化過程如圖2所示，其中感染率設為 β ，恢復率為γ。

為了評估每個節點的傳播能力，在模擬傳播階段，采用遍歷的方式逐個將節點狀態設為感染狀態I，并將其他所有節點的狀態設為易感狀態 Ω_S 。在小型生成網絡上進行多次模擬以減少隨機性。在每次SIR模擬中，統計網絡中節點狀態為I和R的占比，得到節點 i 的初始傳播分數（InitialPropagationScore，IPS），即：

其中， I（j） 和 R（j） 分別表示第 j 次模擬結束時，以節點 i 為初始感染源的網絡中感染者和恢復者的數量，times為模擬次數， N 為網絡節點數。

在生成網絡中，某些節點可能具有相同的傳播分數。為了更準確地反映節點的實際重要性，本文引入了消息傳遞機制，使每個節點能夠融合來自鄰居節點的一部分初始傳播分數，以考慮到鄰居節點對其傳播能力的影響。節點 i 通過公式（2）得到更新后的傳播分數（PropagationScore，PS）：

其中， d_j 為節點 j 的度， N_i ， IPS_i 分別為節點 i 的鄰居節點集和初始傳播分數。

1.1. 2 節點結構影響力度量

在許多研究中，選擇關鍵節點時通常充分考慮節點的局部特征。然而，在實際網絡中，存在一些具有相似結構的節點，但由于其所處網絡位置等因素不同，將導致其影響范圍可能有所不同[1]。因此本文選擇增強 K-Shell算法[18]來細化訓練標簽，從局部和全局兩個角度獲得結構影響力度量，以解決節點間的級聯影響。基于香農信息熵的增強 K-Shell算法（Improved K-Shell，IKS）定義了節點 i 的重要性 I_i 和信息熵：

IKS_i 即節點信息熵，在K-Shell值相同的層中， IKS_i 值越大節點重要性越高； k_j 為節點 j 的度。受Ullah等19啟發，用 IKS_i 值來計算任意節點的局部影響力分數（Local Influence Score，LIS），即：

另外，全局影響力分數（GlobalInfluenceScore，GIS）：

其中， dist_ij 表示節點 i 和節點 j 之間的最短路徑長度。將節點的傳播能力與結構影響力進一步計算，在節點傳播能力層面增強局部結構信息，因此對于節點 i 的最終訓練標簽為

label_i=（PS_i+LIS_i）?GIS_i

其中， ? 為矩陣的哈達瑪積。

1.2 特征學習

如圖1中的特征學習階段，本文采用一個特征嵌入向量 ，由五種節點特征構成。分別是節點度中心性，鄰居節點度，鄰居節點平均度，二階鄰居節點平均度以及聚類系數[20]。這些特征在一定程度上能夠反映節點自身和其鄰域的結構信息，有助于模型捕獲那些具有強傳播能力節點以及描述節點連通性。這些特征被拼接成一個特征矩陣 ，并隨網絡結構一同作為模型的輸人。并通過使用一個全連接線性層函數將特征矩陣轉化為高階矩陣表示，即：

其中，W為線性層的待學習參數， T 表示轉置操作， b 為偏置。

隨后，為了更新節點的表示并對鄰居節點進行聚合，采用GAT模型通過堆疊多層注意力機制，動態地計算不同鄰居節點的重要性，并融合高階鄰居節點的信息。分別計算初始分數 與其一階鄰居的聚合，并利用LeakyReLU非線性激活函數且正則化以后得到注意力系數 α_ij ，其計算過程：

其中，模型權重為 ， F^' 是經過圖注意力層后所產生新的節點特征數量， W 為權重矩陣，|表示矩陣拼接。為了進一步加強計算能力，提高模型泛化水平引人多頭注意力機制：

其中， K 代表每層頭數， σ 激活函數選擇 ReLU 函數。 為模型的輸出，代表每個節點的綜合重要性分數。

此外，一旦某個節點受到感染，其影響會擴散到整個網絡。當某一節點充當感染源點時，有必要區分結構相似但相距較遠的節點，以及這些節點可能對網絡的潛在影響。因此，本文提供了一個可學習的全局投影向量參數ζ來學習節點全局影響能力：

其中， ??，?? 表示向量點積。結合傳播能力和結構信息的 形成最終節點在網絡中的重要性分數。

1.3選擇強影響力的關鍵節點集

在排序結果上挑選關鍵節點集有多種方法，其中Top ?K 算法是按照節點的影響力從高到低逐個選擇前 k 個節點。然而，復雜網絡中存在“富人俱樂部\"現象，即度高的節點傾向于連接其他度高的節點，從而形成一個緊密聯系的子集。因此，Top-K方法可能會選擇相互距離較近的節點，導致單個節點多次受到感染，最終限制了傳播范圍，這種現象被稱為影響重疊[21]。圖3展示了影響重疊的過程，左側是某種節點排序算法的輸出，并從最高排名的節點 v₃ 開始傳播，隨后對 v₁，v₂ ，v₄，v₆ 產生影響，然后選擇排名次高的 v₄ ，繼續對v₂°v₃°v₅°v₇ 產生影響，導致 v₂ 出現了影響重疊。

為了避免影響重疊，本文采用了基于最短距離為二跳的關鍵節點選擇算法 MD2[21]，該算法的核心思想是，在已獲取重要性排序的前提下，按順序選擇節點，并跳過已選節點的所有鄰居節點。

1.4 模型訓練

考慮到在大規模網絡上進行多次SIR模擬可能導致較高的計算成本，本文選擇在小型生成網絡上進行模擬來獲取訓練標簽。這些網絡包括BA無標度網絡，WS小世界網絡和PL網絡。

在構建GAT時引入三層圖注意力層，每個層級都采用自注意力機制處理每個節點，每層的頭數為3。損失函數采用均方差損失函數來反映模型與實際數據的差異，定義：

在生成的3000個人工生成網絡中， 95% 作為訓練集， 5% 作為驗證集。

2實驗方法

本文在網絡影響力最大化和精準免疫兩個不同的應用背景，進行了實驗比較，選取了七種關鍵節點識別算法進行對比，分別是度中心性（DC）、緊密中心性（CC）和介數中心性（BC）、K-Shell分解算法、NIRM、改進K-Shell算法和基于MD2節點選擇算法的VNIA。

2.1 實驗數據

為了驗證方法的泛用性，本文選取了共10個不同類別的真實網絡數據集。統計特征如表1所示， ∣V∣ 為節點數， ∣E∣ 為邊數，2? 為網絡度分布， 為 SIR模型傳播閾值， c 為聚類系數，所有網絡均可從https：//networkrepository.com/進行獲取。實驗過程中將這些真實網絡均視為無權無向圖。

2.2 影響最大化能力分析

為了驗證本研究方法的有效性，對比了不同初始感染節點比例下各基線算法在模擬SIR病毒傳播后的感染范圍。不同的感染率對實驗結果有重要影響，為了減少不必要的變化，將結果專注在所選節點集上，將感染率固定為 β=1.5?β_th 以確保病毒能在網絡中爆發[22]。

在每次SIR 模擬中，選擇節點排序前 k=N×p 個節點作為初始感染節點集，其中 Σ_P 為所選比例。與訓練階段不同，初始感染節點集包含 k 個節點而非單個節點，并在網絡中沒有感染狀態時才停止模擬。為了減少隨機性，對于節點數大于1000的大型網絡，執行100次SIR模擬；節點數小于1000的中小型網絡，執行1000次。計算網絡受影響范圍的平均值，即恢復節點R占網絡總數的比例。

實驗結果如圖4所示，橫坐標表示初始感染節點集比例，縱坐標表示受影響節點占網絡節點總數比例。曲線表示不同比例初始感染節點集下受感染節點比例的變化趨勢。可以看到，VNIA模型在擴大感染網絡范圍方面表現較好。在一些網絡，如CS_Phd，各方法結果相近，但VNIA仍略占上風。傳統模型僅關注節點度或所處位置等單一網絡拓撲信息，未能全面反映節點的真實影響力，特別是在稀疏網絡中，例如 Advogato 子圖，VNIA 模型的性能顯著提高。這歸因于其他模型主要考慮局部或全局結構的信息，卻忽略了節點之間的級聯效應，導致挑選許多簇中節點，即度較高，使傳播受限于簇中進而阻礙網絡整體影響范圍。本文則將局部和全局結構信息融合納入模型，通過捕捉有利于傳播的拓撲特征和節點間的相互作用以靈活應對不同網絡結構來提高方法的精準性，跳出可能存在的社區效應以提高有效性。

然而，在一些聚類系數較小的網絡中，基于MD2節點選擇算法的VNIA 的傳播范圍不如 Top-K算法甚至不如傳統基線模型，這是因為VNIA已經融合了局部和全局結構并提煉了節點的影響能力，再考慮影響重疊后，選取的節點過于分散，反而避開了有助于傳播的節點，進而限制了擴散范圍。這說明VNIA本身就能夠敏銳地識別感染能力強的節點，并且能夠在網絡中快速地傳播信息，以最大程度地影響網絡。

2.3免疫隔離能力分析

如果將影響力最大化反其道而行之，針對所選節點集進行免疫隔離，能否有效遏制病毒傳播，做了如下實驗。選取了6個真實網絡，并對排名前 10% 的節點進行免疫操作，即切斷所選節點連接的所有邊，模擬隔離操作以阻斷與其他節點的聯系。然后，在剩余網絡中進行隨機感染，隨機選擇剩余網絡中 1% 的節點作為初始感染節點。為了使結果更貼近實際，本實驗選近似流感的感染率和恢復率，即 β=0.2，γ=0.1 。

圖5記錄了網絡中感染者的數目隨時間步長Step的變化情況。橫坐標代表一次 SIR模擬中的不同時間步長，縱坐標表示對應時間步長時狀態為I的節點數。結果表明，VNIA模型在對選定節點集進行額外隔離或免疫策略后，能夠有效遏制病毒的大范圍傳播，總體上能使感染范圍控制在最小范圍內。

這一實驗結果也證明了網絡中的病毒傳播受多種因素影響，包括病毒傳播能力、級聯效應以及網絡結構等。因此，在應對疫情傳播和網絡安全等問題時，全面考慮這些因素對于制定有效的策略非常重要。

3結論

本文提出了一種基于注意力機制的關鍵節點識別模型VNIA，目的旨在高效識別和排序關鍵節點。首先，VNIA綜合運用SIR模型結合消息傳遞思想，提煉節點傳播能力，此外采用增強K-Shell算法結合局部和全局結構來提煉結構影響力來獲得訓練標簽。接著，通過融合節點度中心性值，鄰居節點度，鄰居節點平均度，二跳鄰居節點平均度以及聚類系數，將節點重要性分數作為訓練目標。最后，通過圖結構數據嵌入基于圖注意力機制的模型進行訓練。實驗證明，VNIA方法不僅在多種真實網絡中達到了最佳和最穩定的網絡影響范圍，還在免疫隔離方面表現出色，從而表現出更廣泛的應用潛力。

本文工作主要關注無權無向無自環網絡。然而，實際網絡往往具有不同的邊權重和有向性。未來的研究方向之一將包括如何在這些更復雜的網絡上進行關鍵節點的識別。此外，還將探索不同的傳染病模型，如 SI、SIRS、SEIR等，以及不同的圖神經網絡模型，如GCN等，以了解它們對排序結果的影響。

參考文獻：

[1]BARABASALNtwokieceJloopcalasactiosfteoyalSciety：Mathetial，hyicaladEngineig，2013，371（1987）：20120375.

[2]ZHONGSZHHENGY.dentificatioofifuentialoesilexetworks：localdgdimensionapproachInfoatioSciences，2022，610：994－1009.

[3]LUOJ，WUJ，ANGWArelatioshiatrixesolvingodelfoentfgialoessedomnityporusticaltks[J].Transactions on Emerging Telecommunications Technologies，2022，33（l）：e4389.

[4]HEQ，WANGX，MAOF，etal.CAOM：Acommunitybasedapproachtotacklepinionmaxiizationforsocialnetworks[J]InfoationSciences，2020，513：252-269.

[5]SUNPGUAQGetaldentifigifuentialgeesirote-roteiiteractietwoks]foratics，454：229-241.

[6]WANDELTS，SHX，SUNX.EstiationandimprovementoftransportationetworkobstessbyxploitingcommunitieslabilityEngineeringamp;System Safety，2021，206：107307.

[7]BOCIHPFactoringndweightingapproacstatussoresandiqueentiatio]JoualofathematicalSocol9（1）：113-120.

[8]PAGEL，BRIN S，MOTWANIR，etal.ThePageRank citationranking：Bringingorderto thewebR].Stanford InfoLab，999.

[9]ZHUD，ANH，Retal.entfatioofkeyodesiowgidedmodiiedageRankagoritJ]nerge25（3）：797.

[10] SABIDUSSI G. The centrality index of a graph[J]. Psychometrika，1966，31（4）：581-603.

[11]NEWMANMEJ.Ameasureof betweenesscentralitybasedonrandom walks[J].Socialnetworks，2o05，27（1）：39－54.

[12]ZHANGJ，WANGBDismantingcomplexetworksbeuralodeltredotinetwoksC//Procedingsofte3stCtea-tional Conference on Information amp;.Knowledge Management. Atlanta GA，USA，2022：2559-2568.[DB/OL].

[13]VELICKOVICP，CUCURULLG，CASANOVA A，et al.Gaphatention networks[DB/OL].[2023-06-24].https：//arxiv.rg/abs/1710.10903.

[14]GRASSIA M，DEDOMENCOM，MANGIONIG.Machinelearingdismantlingandarl-warngsignalsofdisintegrationincomplexsytems[J].NatureCommunications，202l，12（l）：1-10.

[15]HAMILTONW，YIGZ，LESKOVECJIductiveepresentationlearningonlargegraphsJ]AdvancesinNeuralInformatioProcesingSystems，2017，30.

[16]HETHCOTE H W.Three basic epidemiological models[J].Applied Mathematical Ecology，1989：119-144.

[17]CURADOM，ORTOSAL，VICENJFAnovelmeasuretoidentifynfluentialodes：returrandomwalkgavitycentraityIfoation Sciences，2023，628：177-195.

[18]WANGIUtalentifgftiaspredersiplexeokssedpredkshellethod]catatistical Mechanics and Its Applications，202o，554：124229.

[19]UlahA，WangBhengJF，etalIentficatioofodesifuencebasedoglobalstructureodelincomplexnetwoksSintificReports，2021，11（1）：1-11.

[20]LEIM，CHEONGKH.Nodeinfluenceankinginomplexetwrks：alocaltructureentropyapproachJChaos，Soliosamp;ractals，2022，160：112136.

[21]MAJIG，DUTTAA，MALTAMCetalIentfngandrankingsuperspreadersinealworldcomplexnetwokswitoutifenceoerp[J].Expert Systems with Applications，2021，179：115061.

[22]PASTORR，VESPIGNANIA.Epidemic spreading inscale-freenetworks[J].PhysicalReview Leters，20ol，86（14）：3200.

（責任編輯 李進）