基于改進K?shell的復雜網絡關鍵節點識別方法

摘" 要： 在復雜網絡研究中，精確辨識網絡內的關鍵節點對于深入把握網絡的結構特性和功能機制，以及增強復雜網絡運行的穩固性和安全性具有尤為重要的作用。傳統的K?shell方法僅依據節點在網絡中的位置信息，排序結果太粗粒化，使得節點的區分度不大；僅考慮剩余度的影響，默認同層節點的外層節點數相同，這限制了評估結果的精確性和分辨力。為了解決這一問題，文中提出一種新的關鍵節點識別方法，該方法在原始K?shell算法思想之上綜合考慮了局部影響力，補充了鄰居節點和次鄰居節點對所識別節點重要性的影響。首先，通過K?shell算法確定節點全局影響力，計算每個節點的[Ks]值；其次，通過度中心性算法確定所識別節點的鄰居節點的影響力，而次鄰居節點的影響力則通過其影響系數與數量的乘積來表征；最后，通過綜合考慮鄰居節點以及次鄰居節點的作用來評估節點的局部影響力。具體而言，鄰居節點的影響力通過其度中心性來量化，次鄰居節點的影響力則由其影響系數與數量的乘積來表征。以相關性、單調性以及魯棒性為評價標準，將文中方法在6個真實網絡上進行驗證，驗證結果顯示，提出的方法與目前主流方法相比，能更高效、準確地識別復雜網絡中的關鍵節點，并具有較高的分辨率和準確性。

關鍵詞： 復雜網絡； K?shell； 度中心性； 關鍵節點識別； 鄰居節點； 節點影響力

中圖分類號： TN711?34； TP399" " " " " " " " " " 文獻標識碼： A" " " " " " " " " " "文章編號： 1004?373X（2025）07?0095?09

Complex network′s key node identification based on improved K?shell method

LI Tianyu1， TENG Guifa1， YAO Jingfa2

（1. School of Information Science and Technology， Hebei Agricultural University， Baoding 071001， China;

2. Software Engineering Department， Hebei Software Institute， Baoding 071000， China）

Abstract： In the study of complex networks， accurate identification of key nodes in the network is particularly important for deeply grasping the structural characteristics and functional mechanisms of the network， as well as enhancing the stability and security of the operation of complex networks. The traditional K?shell method is based only on the location information of the node in the network， so the sorting results are too coarse?grained， which makes the node discrimination inconspicuous. In addition， it only considers the influence of the redundancy， and the number of outer nodes of the same layer nodes is assumed to be the same， which limits the accuracy and resolution of the evaluation results. In view of the above， this paper proposes a new key node identification method. This method comprehensively considers the local influence on the basis of the idea of the original K?shell algorithm， and supplements the influence of neighbor nodes and sub?neighbor nodes on the importance of the identified nodes. Firstly， the K?shell algorithm is used to determine the global influence of the nodes and calculate the [Ks] value of each node. Secondly， the influence of the neighbor nodes of the identified nodes is determined by the degree centrality algorithm， and the influence of the sub?neighbor nodes is characterized by the products of their influence coefficients and quantities. Finally， the local influence of the nodes is evaluated by considering the role of neighbor nodes and sub?neighbor nodes comprehensively. Specifically， the influence of neighbor nodes is quantified by their degree centrality， and the influence of sub?neighbor nodes is characterized by the products of their influence coefficients and quantities. Finally， the method is verified on 6 real networks with correlation， monotonicity and robustness as evaluation criteria. The verification results show that the proposed method can identify key nodes in complex networks more efficiently and accurately and has higher resolution and accuracy in comparison with the current mainstream methods.

Keywords： complex network; K?shell; degree centrality; key node identification; neighbor node; node influence

0" 引" 言

隨著復雜網絡理論研究的興起，關鍵節點識別逐漸成為該領域的熱點問題，日益受到來自社會網絡[1]、生物網絡[2]、計算機網絡[3]、管理學[4]和經濟學[5]等領域研究人員的廣泛關注。在復雜網絡中，準確識別關鍵節點對于理解網絡的結構與功能，以及提高復雜網絡運行的穩定性和安全性具有重要作用[6?7]。例如，在交通網絡中，找到負載重、易發生交通癱瘓的路段或站點，以便采取有效措施，避免交通擁堵，也可為交通路線規劃提供理論依據[8]；電力系統中關鍵節點的識別對于電網運行具有重要意義。準確定位樞紐節點不僅有助于制定更為高效的電力調度策略，還能顯著提升系統抗風險能力，從而有效預防大規模停電事故的發生。因此，樞紐節點識別方法的研究對保障電網安全穩定運行具有重要的理論和實踐價值[9]。在病毒傳播網絡中，追蹤和管理超級傳播者能有效抑制病毒擴散[10]。此外，關鍵節點識別在糧食安全、輿情管控、案件偵破及市場營銷等多個領域也具有廣闊的應用前景[11?13]。

復雜網絡中關鍵節點的識別是一個備受關注的研究課題，為解決這一問題，研究者們提出了多種方法，包括度中心性（Degree Centrality， DC）[14]、特征向量中心性（Eigenvector Centrality， EC）[15]、介數中心性（Betweenness Centrality， BC）[16]和接近中心性（Closeness Centrality， CC）[17]等。其中度中心性是基于節點的局部特性，具有較低的時間復雜度，但由于忽略了節點鄰域的拓撲結構，其識別準確性受到限制[18]；特征向量中心性方法同時考慮了相鄰節點的數量和重要性，但其較高的計算復雜度限制了其在大規模網絡中的應用[19]；介數中心性和接近中心性是基于全局特性的方法，準確性很高，但計算耗時較長，限制了它們在大型網絡中的應用[20]。

K殼（K?shell）分解方法是一種基于網絡全局特性的方法，該方法基于網絡的整體拓撲結構，通過迭代剝離過程將節點劃分為不同的層級。K殼分解法假設節點的重要性與其在網絡中的位置密切相關，位于網絡核心區域的節點往往具有更高的影響力。這種基于全局特性的分層方法為量化復雜網絡中節點的重要性提供了一個有效的框架[21]。由于該方法具有良好的時間復雜度，廣泛應用于大型網絡，但其缺點是無法區分同層節點的重要性。文獻[22]提出了一種新穎的混合度分解方法（MDD），該方法的獨特之處在于其同時考慮了網絡中被移除節點和余留節點對特定目標節點重要性的雙重影響。這一方法為評估復雜網絡中節點的關鍵性提供了更為全面和精確的框架。文獻[23]通過對具有可調參數[α]的鄰域節點[Ks]值求和來區分節點重要性，提出了改進的鄰域節點K核方法（INK），文獻[24]在此基礎上進一步完善，又提出了鄰域核心中心度方法（Cnc+）。文獻[25]提出了一種新穎的節點重要性評估方法，該方法基于這樣一個假設：在網絡結構中，邊的連接關系和相鄰節點對中心節點的影響程度存在異質性。因此，他們引入了加權機制，通過賦予不同權重來量化這些異質性影響，從而更準確地衡量節點在網絡中的重要程度。文獻[26]提出了加權K?shell度鄰域識別方法（KSD），該方法綜合考慮了節點度、鄰域節點度以及K?shell信息。文獻[27]提出了一種新穎的節點重要性識別方法，即基于鄰域K?shell分布的識別算法（KDN）。該方法創新性地考慮了節點鄰居的K?shell值分布對中心節點重要性的影響，從而提高了復雜網絡中關鍵節點的識別精度。前述方法在節點重要性評估中考量節點鄰居的規模與分布特征，有效提高了節點重要性識別的準確性，但并未深入探究次鄰居節點對節點重要性的潛在影響，這在一定程度上限制了關鍵節點識別的精細程度。

為了在復雜網絡中更全面地刻畫節點的重要性，本文提出了一種基于改進K?shell（Improved K?shell， IK）的復雜網絡關鍵節點識別方法。該方法綜合考慮節點的全局影響和局部影響，通過K?shell方法獲得的節點[Ks]值反映了節點的全局影響，然后通過整合其鄰居節點與次鄰居節點的效應來體現節點的局部影響。具體而言，鄰居節點的影響依據節點的度中心性來量化，而次鄰居節點的影響則通過計算次鄰居節點的影響系數與其數量的乘積來確定。為驗證所提方法的有效性，在6個真實世界網絡上進行了仿真實驗，與現有主流方法相比，本文提出的方法在識別關鍵節點方面表現出顯著的高準確度和分辨率。

1" 理論基礎

1.1" K?shell方法

K?shell分解法是一種自底向上的層次化網絡分析方法，通過對網絡進行層級分解，將節點劃分為不同的殼層，以此衡量節點在網絡中的相對重要性。然而，該方法主要關注節點在網絡中的全局位置，對節點的局部連接特征考慮不足，在一定程度上限制了其在復雜網絡分析中的應用[21]。以圖1為示例，此方法的操作步驟概述如下。

1） 對網絡內全部節點進行度值計算。

2） 移除網絡中所有度數為1的節點及其相連邊，隨后更新網絡結構并重新計算各節點的度數。此過程需遞歸進行，持續刪除度數為1的節點及其邊，直至網絡內不再存在此類節點。將這些被移除的節點歸類為1?shell層，并賦予它們[Ks]值為1。接著，采用相同的方法，移除網絡中所有度數為2的節點及其連接邊，將這部分被刪除的節點劃入2?shell層，同時為其分配[Ks]值為2。

3） 重復上述迭代過程，直至網絡中所有節點被逐層剝離，形成若干個K?shell結構。根據節點所屬的K?shell層，為每個節點分配相應的K?shell指數（[Ks]值）。[Ks]值最大的節點位于網絡的核心層，這些節點對整個網絡的結構和功能具有決定性影響，離核心層越遠，節點的[Ks]值和重要性也越小。

在Ｋ?shell方法執行結束后，圖１中節點的[Ks]值分別為[Ks]=1（節點1、節點2、節點3、節點4），[Ks]=2（節點9、節點10、節點11），[Ks]=3（節點5、節點6、節點7、節點8）。

K?shell方法的排序特點是相同[Ks]值的節點較多，若網絡規模越大，相同[Ks]值的節點數量就會越多，其中的重要節點也就越難以區分。如圖1所示，節點5、節點6、節點7、節點8的[Ks]值都為3，但這幾個節點的重要性明顯有一定區別。為了解決這個問題，本文首先用K?shell方法將網絡中的節點分層，再根據同層節點的局部結構信息進一步評價節點的重要性。

1.2" 度中心性

在無向圖分析中，節點度（Degree）是衡量節點局部影響力的基礎。度中心性通過量化節點的度，直接反映了節點在網絡中的連接程度。度中心性較高的節點通常是網絡中的樞紐節點，對信息的傳播和網絡的穩定性具有重要影響[28]。節點的度中心性可表示為：

[DCi=Di N-1] （1）

式中：[Di]表示節點[i]的度；[N]表示網絡的節點數。節點[i]的度中心性[DCi]在0～1取值，當[DCi]=0時，表示節點[i]與網絡中的其他任何節點均無連接關系；若[DCi]=1，則表示節點[i]與網絡中的其他所有節點均直接相連。

從式（1）中可以看出，利用度中心性衡量節點局部影響力時，僅考慮了鄰居節點對節點重要性的影響，而沒有考慮次鄰居節點的貢獻，但研究表明，次鄰居節點對節點重要性也會產生影響[29]。為此，本文在度中心性方法的基礎上，引入次鄰居節點信息，以更加準確地反映節點的局部影響。

2" 本文提出的復雜網絡關鍵節點識別方法

2.1" 次鄰居節點對節點重要性的影響

由于度中心性忽略了次鄰居節點的作用，特別是在節點的度中心性相同時，該方法就無法衡量節點的局部影響。為了說明次鄰居節點對指定節點重要性的影響，以圖2為例進行解釋。

在圖2中，節點4位于此小網絡的中心，節點4左側的5個節點（節點0、節點1、節點2、節點3、節點10）若要連接到其右側的5個節點（節點5、節點6、節點7、節點8、節點9），必須以節點4為橋梁。在社會網絡中，這種特殊而重要的結構被稱為結構洞[30]。在社交網絡中，個體所占有的“結構洞”數量越多，其于群體內的地位便越顯重要，同時，其運用人際聯系獲取利益的能力亦隨之增強。可見，節點4是極其關鍵的節點。但按度中心性分析，節點4和節點1的度中心性相同，所以認為兩個節點同樣重要。從圖中不難發現，節點4比節點1更為重要，這是因為雖然這兩個節點的度中心性相同，但節點4的次鄰居節點數量（8個）明顯多于節點1（3個），說明在節點的度中心性相同時，次鄰居節點數量越多，節點的重要性也越大，這也表明節點的局部影響，不僅受鄰居節點數量的影響，還受次鄰居節點數量的影響。

由以上分析可知，一個節點雖然與次鄰居節點沒有直接相連，但可以通過次鄰居節點的中介作用影響到更多的其他節點。在衡量節點局部影響時，度中心性方法由于忽略了次鄰居節點的影響，分辨率較低。為此本文提出改進，通過次鄰居節點的數量信息，評估次鄰居節點對節點重要性的影響；同時考慮到節點影響力的傳播具有一定的范圍，并受鄰居階數影響而逐級衰減，導致每個次鄰居節點對指定節點影響力的貢獻小于單個鄰居節點。因此，本文通過定義次鄰居節點影響系數[α]（[α]lt;1），來表示單個次鄰居節點對節點重要性的影響，其計算公式見式（2）：

[α=1N-12] （2）

式中：[α]表示次鄰居節點的影響系數；[N]表示網絡的節點數。

次鄰居節點的影響為次鄰居節點的影響系數[α]與其數量的乘積，計算過程見式（3）：

[Si=α?Di] （3）

式中：[Si]表示節點[i]的次鄰居節點的影響；[α]表示次鄰居節點的影響系數；[Di]表示節點[i]的次鄰居節點數量。

2.2" 改進K?shell的復雜網絡關鍵節點識別方法

本文針對K?shell算法在節點重要性評估方面的不足，根據網絡局部結構特征，考慮到次鄰居節點對節點重要性的影響，在度中心性方法的基礎上，提出了節點局部影響的計算方法，計算過程見式（4）：

[Ci=DCi+Si] （4）

式中：[Ci]表示節點[i]的局部影響；[DCi]表示節點[i]的度中心性度量；[Si]反映了節點[i]的次鄰居節點影響。

本研究以K?shell算法及節點局部影響力為基石，創新性地提出了一個復雜網絡中關鍵節點的識別策略，即基于改進K?shell的復雜網絡關鍵節點識別方法（IK）。在該策略框架下，首先利用K?shell算法在整體網絡層面識別關鍵節點，以此評估全局結構的重要性；其次，通過綜合考慮直接鄰接節點與次鄰接節點的影響，來精確衡量節點的局部結構影響力。IK方法的計算過程見式（5）：

[IKi=Ksi+Ci] （5）

式中：[IKi]為節點[i]的重要性；[Ksi]為節點[i]的[Ks]值；[Ci]為節點[i]的局部影響。

IK方法的設計思路：首先，用K?shell將網絡分層，獲取每個節點的[Ks]值，以評估節點的全局影響。然后，依據鄰居節點和次鄰居節點對指定節點的影響程度區分同層節點的重要性，以衡量節點的局部影響。具體而言，先根據鄰居節點數量計算節點的度中心性，并以此對同層節點進行重要性排序，如排序相同，再按其次鄰居節點的影響排序。當同層內節點的度中心性相同時，即鄰居節點數量相同時，由于次鄰居節點的影響與其數量正相關，次鄰居節點數量多的節點更重要。IK方法全面評估了全局與局部網絡信息對節點重要性的雙重作用，在計算節點的局部影響力時，僅納入直接鄰居及次級鄰居的信息貢獻，以此降低計算復雜度。該方法因此能高效識別復雜網絡中的核心節點，展現出高準確性及優異的分辨率。

IK方法的具體過程設計如下。

算法1：IK方法

輸入：網絡圖[G=（V，E）]

輸出：節點重要性排序

For" "網絡圖[G]中的節點[V]

Repeat

對于網絡圖[G]中度為[K]的節點

分配其[Ks]值等于[K]

更新節點的[Ks]值

在網絡圖中刪除節點[V]

Until網絡圖[G]中所有剩余節點的度gt;[K]，[K=K+1]

計算節點的直接相連鄰居節點數[Pi]和次鄰居節點數[Di]

根據公式（2）計算次鄰居節點的影響系數[α]

根據公式（3）計算次鄰居節點的影響[Si]

根據公式（4）計算節點的局部影響[Ci]

根據公式（5）計算節點的重要性[IKi]

End for

[Ks]值大的節點先輸出，再按[Pi]值大的進行輸出，最后按[IKi]值輸出

2.3" 實例分析

本文用IK方法分析圖1網絡中各節點的層次及重要性，并與K?shell、DC、MDD、CN和BC等的分析結果比較。各方法的節點重要性排序結果如表1所示。從表中可以看出，與本文提出的IK方法相比，K?shell、DC、MDD、CN和BC等方法的分辨率均較低。其中，K?shell方法分辨率最低，將網絡中的節點共分為3層，DC和CN方法將節點分為5層，MDD和BC方法分辨率較高，將網絡中的節點分為7層，而IK方法的分辨率最高，將所有節點分為9層，不能區分的節點僅為第6層的節點10和節點11以及第8層的節點1和節點2。但由圖1可知，節點10和節點11具有同等的重要性；與之類似，節點1和節點2在網絡中的重要性也相同，說明IK方法的排序結果真實地反映了圖1網絡中各節點的重要性。因此，與其他方法相比，本文提出的IK方法對網絡中各節點重要性的區分度更大，且排序結果也更為準確。

3" 實驗數據與結果分析

3.1" 實驗數據

為了全面評估IK方法在節點識別任務中的性能，本文選取了6個具有代表性的真實網絡數據集進行實驗和仿真，6個網絡分別為：Les miserables網絡[31]、Crime網絡[32]、Email網絡[33]、Facebook網絡[34]、 PowerGrid[35]網絡和Train網絡[36]。6個網絡的信息如表2所示。其中：[N]為網絡節點數；[M]為網絡邊數；〈[k]〉為網絡的平均度；[kmax]為網絡中節點的最大度值；[c]為網絡的聚類系數；[βth]表示網絡的流行閾值；[β]為網絡的感染概率。

3.2" 評價標準

3.2.1" 相關性指標

為了評價不同方法的準確性，選用6種方法（K?shell、DC、MDD、CN、BC和IK）在6個典型復雜網絡（Les miserables、Crime、Email、Facebook、PowerGrid和Train）中進行對比實驗。首先，采用了6種不同方法來評估網絡中各節點的重要性并排序；其次，為驗證所提方法的有效性，本文采用經典的SIR模型對識別出的關鍵節點進行傳播模擬。通過比較不同方法所得節點重要性排序與SIR模型模擬得到的節點傳播效率排序，計算Kendall相關系數（[τ]），以量化不同方法與真實傳播過程的一致性。

1） SIR模型

本文采用經典的SIR（Susceptible?Infected?Recovered）傳播模型來模擬節點影響力的擴散過程[27]，將網絡中的節點狀態劃分為易感、感染和恢復三種。實驗初始時，僅指定一個節點為感染態，其余節點均為易感態。在每個離散時間步，感染節點以概率[β]嘗試感染其鄰接的易感節點，成功則后者轉變為感染態。同時，感染節點以概率[γ]轉為恢復態，且此后不再受感染。

模擬過程持續進行，直至網絡中不再存在處于感染狀態的節點。此時，處于恢復狀態的節點總數被視為初始感染節點對整個網絡的影響力。通過對網絡中每個節點重復此過程，可以計算并比較各節點的影響力，進而生成按影響力降序排列的SIR排序列表，這為評估節點在網絡中的相對重要性提供了定量基礎。本文采用傳播閾值[βth]=[kk2]，感染率[β]的取值位于傳播閾值附近，設定恢復概率[γ]為0.01，為了排除偶然性干擾，將100次傳播過程的平均值視作真實影響力。

2） Kendall系數

將不同識別方法和SIR模型仿真得到的排序結果進行比較，計算Kendall相關系數[τ]值[27]。[τ]值越高，說明該方法與SIR排序結果的相關性越強，即該方法關鍵節點識別的準確度越高。Kendall相關系數[τ]的定義如下：

[τ=2（C-D）N（N-1）] （6）

式中：[C]代表兩序列中一致性序列對的數量；[D]為不一致性序列對的數量；[N]是網絡中節點的總數。

3.2.2" 單調性指標

為了量化不同識別方法的分辨率，使用排名列表[R]的單調性指標[M（R）]進行驗證[27]。單調性指標[M（R）]被廣泛用于評估排序結果的區分度，其值越大，表明擁有相同重要性評分的節點越少，即排序結果的單調性越強。單調性指標[MR]的表達式為：

[MR=1-r∈Rnr（nr-1）n（n-1）2] （7）

式中：[R]代表節點重要性排序結果；[n]代表排序結果中節點的總數；[nr]代表節點重要性排序結果中相同的節點個數。用[MR]衡量節點重要性排序結果的單調性，[MR]在0和1之間取值，其中[MR]=0時，代表網絡中全部節點的重要性均相同；[MR]=1時，代表網絡中全部節點的重要性均不同。

3.2.3" 魯棒性驗證

為了評價關鍵節點識別方法的有效性，本文從網絡魯棒性角度分析了節點移除后網絡連通性的變化[37]。在復雜網絡環境中，連通分量構成網絡的子圖，其中任意兩節點間均保持連通狀態。特別地，最大連通子圖指的是在節點刪除導致網絡分裂后，所含節點數量最多的那個連通分量，此指標能有效表征復雜網絡的整體連通水平。當移除網絡中的關鍵節點時，網絡的最大連通子圖規模將顯著縮減。為了量化這種影響，本文采用最大連通系數作為評價指標，其定義為：移除節點后，網絡中最大連通子圖所包含的節點數與原始網絡節點總數的比值[37]，計算公式如式（8）所示：

[r=Sn] （8）

式中：[r]表示網絡的最大連通系數；[n]為原始網絡中節點總數；[S]表示移除部分節點后網絡的最大連通子圖包含的節點數。

網絡魯棒性是用來衡量移除任意節點后網絡中的剩余節點之間仍然能夠保持連通能力的平均影響力[38]。利用最大連通系數來計算網絡的魯棒性，計算公式如式（9）所示：

[R=1nj=1nrj] （9）

式中：[R]表示網絡的魯棒性；[rj]表示移除[j]個節點后的最大連通系數。

本文首先利用6種識別方法（K?shell、DC、MDD、CN、BC和IK）分別將6個網絡（Les miserables、Crime、Email、Facebook、PowerGrid和Train）中的所有節點進行重要性排序，然后按重要性由大到小的順序，依次移除節點及其相關的邊，在每次移除操作后，計算殘余網絡的最大連通子圖規模，并以此計算網絡的魯棒性。[R]值越小，表明網絡越容易發生崩潰問題，移除的節點對網絡結構的影響越大，進而驗證了節點識別方法的有效性。

3.3" 實驗結果分析

3.3.1" 準確性分析

為了驗證IK方法的準確性，本文采用6種識別方法（K?shell、DC、MDD、CN、BC和IK）和SIR模型分別對6個網絡（Les miserables、Crime、Email、Facebook、PowerGrid和Train）節點的排序結果進行比較，得到各網絡的Kendall相關系數[τ]，如表3所示，表中的[β]為網絡的感染率。由表3可知，除PowerGrid網絡外，IK方法在其他5個網絡中的Kendall系數均為最高。在PowerGrid網絡中，IK方法得到的[τ]值僅低于BC方法，且兩者相差不大，分析表明，采用IK方法所得節點重要性排序與節點實際影響力排序高度一致，展現出較高的精確度。

圖3為不同識別方法得到的排序結果與不同感染率下SIR排序結果之間的Kendall相關系數的變化情況，圖中垂直虛線的橫坐標為[βth]值。在[βth]值附近，除PowerGrid網絡外，IK方法在其他5個網絡中的Kendall系數均為最高值；在PowerGrid網絡中，IK方法的Kendall系數值略低于CN和BC方法，但明顯高于其他3種方法。以上結果表明，在絕大多數情況下，IK方法具有較高的準確性，這是由于該方法綜合考慮了節點的全局和局部影響，從而提高了關鍵節點識別的準確性。3.3.2" 單調性分析

為了驗證IK方法的分辨率，在6個真實網絡下對6種方法（K?shell、DC、MDD、CN、BC和IK）所得到的單調性指標[M（R）]進行比較，結果如表4所示。由表可知，除Email網絡外，IK方法在其他5個真實網絡中得到的節點重要性排序結果均具有最高的單調性。在Email網絡中，該方法排序結果的單調性指標值僅低于BC，但兩者差異很小。因此，與其他幾種方法相比，IK方法具有較高的分辨率。

3.3.3" 魯棒性實驗

為了評價節點識別方法的有效性，本文利用6種識別方法分別將6個網絡內的節點實施了重要性評估與排序。隨后，依據節點重要性的遞減次序，依次移除節點及其連邊，分析網絡最大連通系數的變化趨勢，分析不同識別方法對網絡魯棒性的影響，從而評價方法的有效性，結果如圖4和表5所示。

圖4顯示了節點的移除比例與網絡最大連通系數的關系曲線，橫坐標是節點的移除比例，即移除的節點數量占總節點數量的比例，縱坐標為移除節點后的最大連通系數[r] 。由圖4可知：在6個網絡中，隨著移除節點比例的增大，網絡的最大連通系數均表現為下降的趨勢；在Les miserables、Crime、Email和PowerGrid網絡中，當節點移除比例達到0.2時，IK方法相較于其他識別方法，網絡最大連通系數的下降幅度更為顯著，分別為87.1%、88.5%、48.4%和97.8%，表明IK方法在這4個網絡中表現最佳。

在Train網絡中，只有在0.187～0.485范圍內的移除節點比例時，通過IK方法移除節點后的最大連通系數大于BC，且小于其他方法，表明在此范圍內BC方法關鍵節點識別能力最佳，IK方法次之；而當移除的節點比例在此范圍之外時，特別是在移除節點初期，IK方法的節點識別能力最佳，而BC方法表現不理想。

綜合來看，與其他方法相比，IK方法在Train網絡中具有較好的節點識別能力。同理，在Facebook網絡中，BC方法的節點識別效果最佳，IK次之。

綜上所述，在不同的復雜網絡中，IK是一種較為有效的關鍵節點識別方法。表5顯示了6種方法識別的節點被移除后網絡的魯棒性[R]值。[R]值越小，說明該方法識別的關鍵節點對網絡魯棒性的影響越大，該方法的性能也就越好。

由表5可知，在除Facebook外的其他5個網絡中，IK方法識別的節點被移除后網絡的[R]值最小，說明IK方法在這5個網絡中的識別效果最佳；在Facebook網絡中，利用IK方法得到的[R]值僅低于BC，表明IK方法在該網絡中具有較好的節點識別能力。因此，本文提出的方法能夠有效地識別復雜網絡中的關鍵節點。

4" 結" 論

本文針對傳統K?shell方法存在的準確性和分辨率不高的問題，綜合考慮節點的全局和局部影響，提出了一種基于改進K?shell的關鍵節點識別方法（IK）。

首先，運用K?shell算法對網絡進行分層處理，以獲取網絡中各節點的[Ks]值，該值用以衡量節點的全局影響力。

隨后，通過分析節點的鄰居及次鄰居對其重要性的貢獻，來揭示節點的局部影響力特征。其中，鄰居節點對節點的影響程度以其度中心性來具體表征；在評價次鄰居節點的影響時，通過定義次鄰居節點的影響系數[α]來表示單個次鄰居節點對節點重要性的影響，然后用次鄰居節點影響系數與次鄰居節點數量的乘積來表征次鄰居節點的影響。

最終，利用節點的[Ks]值和度中心性以及次鄰居節點的影響三者之和來評價節點的重要性。對于同殼層節點而言，節點的度中心性相同時，即鄰居節點數相同時，次鄰居節點數量多的節點更重要。以相關性、單調性以及魯棒性為評價標準，將該方法在6個真實網絡上進行驗證。實驗結果表明，與其他方法相比，本文提出的方法能有效地識別不同復雜網絡中的關鍵節點，并具有較高的分辨率和準確性。

注：本文通訊作者為滕桂法。

參考文獻

[1] PEI S， TENG X， SHAMAN J， et al. Efficient collective influence maximization in cascading processes with first?order transitions [J]. Scientific reports， 2017， 7： 45240.

[2] SCHADT E E. Molecular networks as sensors and drivers of common human diseases [J]. Nature， 2009， 461（7261）： 218?223.

[3] ULLAH A， WANG B， SHENG J F， et al. Identifying vital nodes from local and global perspectives in complex networks [J]. Expert systems with applications， 2021， 186： 115778.

[4] AMANCIO D R， NUNES M G V， OLIVEIRA O N， Jr， et al. Using metrics from complex networks to evaluate machine translation [J]. Physica A： Statistical mechanics and its applications， 2011， 390（1）： 131?142.

[5] GARAS A， ARGYRAKIS P， ROZENBLAT C， et al. Worldwide spreading of economic crisis [J]. New journal of physics， 2010， 12（11）： 113043.

[6] MILO R， SHEN?ORR S， ITZKOVITZ S， et al. Network motifs： Simple building blocks of complex networks [J]. Science， 2002， 298（5594）： 824?827.

[7] COHEN R， HAVLIN S， BEN?AVRAHAM D. Efficient immunization strategies for computer networks and populations [J]. Physical review letters， 2003， 91（24）： 247901.

[8] 楊景峰，朱大鵬，趙瑞琳.城市軌道交通網絡特性與級聯失效魯棒性分析[J].計算機工程與應用，2022，58（7）：250?258.

[9] 郭明健，高巖.基于復雜網絡理論的電力網絡抗毀性分析[J].復雜系統與復雜性科學，2022，19（4）：1?6.

[10] LUO X F， JIN Z. A new insight into isolating the high?degree nodes in network to control infectious diseases [J]. Communications in nonlinear science and numerical simulation， 2020， 91： 105363.

[11] 姜敏勤，石小晶，楊鈺，等.基于多屬性評價的糧食供應鏈網絡關鍵節點識別[J].糧食科技與經濟，2023，48（4）：83?89.

[12] 韓奕，孫百兵，王軍國，等.基于關鍵節點識別算法的重點人分析研究[J].北京航空航天大學學報，2024，50（7）：2074?2082.

[13] SHEIKHAHMADI A， ZAREIE A. Identifying influential sprea?ders using multi?objective artificial bee colony optimization [J]. Applied soft computing journal， 2020， 94： 106436.

[14] FREEMAN W J. Spatial properties of an EEG event in the olfactory bulb and cortex [J]. Electroencephalography and clinical neurophysiology， 1978， 44（5）： 586?605.

[15] BONACICH E， LIGHT I H， WONG C C. Koreans in business [J]. Society， 1977， 14（6）： 54?59.

[16] BRANDES U. A faster algorithm for betweenness centrality [J]. Journal of mathematical sociology， 2001， 25（2）： 163?177.

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

[18] YANG Y， WANG X， CHEN Y， et al. Identifying key nodes in complex networks based on global structure [J]. IEEE access， 2020， 8： 32904?32913.

[19] WAMBEKE B W， LIU M， HSIANG S M. Using Pajek and centrality analysis to identify a social network of construction trades [J]. Journal of construction engineering and management， 2012， 138（10）： 1192?1201.

[20] ULLAH A， WANG B， SHENG J F， et al. Identification of influential nodes via effective distance?based centrality mechanism in complex networks [J]. Complexity， 2021（1）： 8403738.

[21] KITSAK M， GALLOS L K， HAVLIN S， et al. Identification of influential spreaders in complex networks [J]. Nature physics， 2010， 6（11）： 888?893.

[22] ZENG A， ZHANG C J. Ranking spreaders by decomposing complex networks [J]. Physics letters A， 2013， 377（14）： 1031?1035.

[23] LIN J H， GUO Q， DONG W Z， et al. Identifying the node spreading influence with largest k?core values [J]. Physics letters A， 2014， 378： 3279?3284.

[24] BAE J， KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness [J]. Physica A： Statistical mechanics and its applications， 2014， 395： 549?559.

[25] 朱曉霞，胡小雪.基于改進k?shell算法的節點影響力的識別[J].計算機工程與應用，2019，55（1）：35?41.

[26] LAI Q， ZHANG H H. Analysis of identification methods of key nodes in transportation network [J]. Chinese physics B， 2022， 31（6）： 068905.

[27] 吳亞麗，任遠光，董昂，等.基于鄰域K?shell分布的關鍵節點識別方法[J].計算機工程與應用，2024，60（2）：87?95.

[28] 閆泓任，馬國帥，錢宇華.基于節點度中心性的無監督特征選擇[J].數據采集與處理，2019，34（2）：312?321.

[29] 謝麗霞，孫紅紅，楊宏宇，等.基于K?shell的復雜網絡關鍵節點識別方法[J].清華大學學報（自然科學版），2022，62（5）：849?861.

[30] LIN Z H， ZHANG Y W， GONG Q Y， et al. Structural hole theory in social network analysis： A review [J]. IEEE transactions on computational social systems， 2021， 9（3）： 724?739.

[31] JUN S P， YOO H S， CHOI S. Ten years of research change using Google Trends： From the perspective of big data utilizations and applications [J]. Technological forecasting and social change， 2018， 130： 69?87.

[32] KAZEMI S M， GOEL R， JAIN K， et al. Representation learning for dynamic graphs： A survey [J]. The journal of machine learning research， 2020， 21（1）： 2648?2720.

[33] GUIMERA R， DANON L， DIAZ?GUILERA A， et al. Self?similar community structure in a network of human interactions [J]. Physical review E， 2003， 68（6）： 065103.

[34] JIN D， YU Z Z， JIAO P F， et al. A survey of community detection approaches： From statistical modeling to deep learning [J]. IEEE transactions on knowledge and data engineering， 2023， 35（2）： 1149?1170.

[35] JUSUP M， HOLME P， KANAZAWA K， et al. Social physics [J]. Physics reports， 2022， 948： 1?148.

[36] HAYES B. Computing science： Connecting the dots [J]. American scientist， 2006， 94（5）： 400?404.

[37] 吳英晗，田闊，李明達，等.利用節點傳播熵識別超網絡重要節點[J].計算機工程與應用，2023，59（19）：66?74.

[38] 陳雯柏，崔曉麗，郝翠，等.一種物聯網系統層次型抗毀性拓撲構建方法[J].北京郵電大學學報，2018，41（5）：103?109.

作者簡介：李天雨（1996—），男，河北保定人，碩士研究生，主要從事社會網絡數字化研究與應用。

滕桂法（1963—），男，河北衡水人，博士研究生，教授，博士生導師，主要研究方向為人工智能與大數據、智能農業。

姚竟發（1983—），男，河北衡水人，博士研究生，講師，主要研究方向為人工智能與多模態大數據技術。

收稿日期：2024?06?14" " " " " "修回日期：2024?07?08

基金項目：國家自然科學基金項目（U20A20180）；河北省人力資源和社會保障課題（JRS?2023?3078）