摘" 要： 在復(fù)雜網(wǎng)絡(luò)研究中，精確辨識(shí)網(wǎng)絡(luò)內(nèi)的關(guān)鍵節(jié)點(diǎn)對(duì)于深入把握網(wǎng)絡(luò)的結(jié)構(gòu)特性和功能機(jī)制，以及增強(qiáng)復(fù)雜網(wǎng)絡(luò)運(yùn)行的穩(wěn)固性和安全性具有尤為重要的作用。傳統(tǒng)的K?shell方法僅依據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置信息，排序結(jié)果太粗?；沟霉?jié)點(diǎn)的區(qū)分度不大；僅考慮剩余度的影響，默認(rèn)同層節(jié)點(diǎn)的外層節(jié)點(diǎn)數(shù)相同，這限制了評(píng)估結(jié)果的精確性和分辨力。為了解決這一問(wèn)題，文中提出一種新的關(guān)鍵節(jié)點(diǎn)識(shí)別方法，該方法在原始K?shell算法思想之上綜合考慮了局部影響力，補(bǔ)充了鄰居節(jié)點(diǎn)和次鄰居節(jié)點(diǎn)對(duì)所識(shí)別節(jié)點(diǎn)重要性的影響。首先，通過(guò)K?shell算法確定節(jié)點(diǎn)全局影響力，計(jì)算每個(gè)節(jié)點(diǎn)的[Ks]值；其次，通過(guò)度中心性算法確定所識(shí)別節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的影響力，而次鄰居節(jié)點(diǎn)的影響力則通過(guò)其影響系數(shù)與數(shù)量的乘積來(lái)表征；最后，通過(guò)綜合考慮鄰居節(jié)點(diǎn)以及次鄰居節(jié)點(diǎn)的作用來(lái)評(píng)估節(jié)點(diǎn)的局部影響力。具體而言，鄰居節(jié)點(diǎn)的影響力通過(guò)其度中心性來(lái)量化，次鄰居節(jié)點(diǎn)的影響力則由其影響系數(shù)與數(shù)量的乘積來(lái)表征。以相關(guān)性、單調(diào)性以及魯棒性為評(píng)價(jià)標(biāo)準(zhǔn)，將文中方法在6個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果顯示，提出的方法與目前主流方法相比，能更高效、準(zhǔn)確地識(shí)別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，并具有較高的分辨率和準(zhǔn)確性。

關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò)； K?shell； 度中心性； 關(guān)鍵節(jié)點(diǎn)識(shí)別； 鄰居節(jié)點(diǎn)； 節(jié)點(diǎn)影響力

中圖分類(lèi)號(hào)： TN711?34； TP399" " " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " "文章編號(hào)： 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" 引" 言

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

復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別是一個(gè)備受關(guān)注的研究課題，為解決這一問(wèn)題，研究者們提出了多種方法，包括度中心性（Degree Centrality， DC）[14]、特征向量中心性（Eigenvector Centrality， EC）[15]、介數(shù)中心性（Betweenness Centrality， BC）[16]和接近中心性（Closeness Centrality， CC）[17]等。其中度中心性是基于節(jié)點(diǎn)的局部特性，具有較低的時(shí)間復(fù)雜度，但由于忽略了節(jié)點(diǎn)鄰域的拓?fù)浣Y(jié)構(gòu)，其識(shí)別準(zhǔn)確性受到限制[18]；特征向量中心性方法同時(shí)考慮了相鄰節(jié)點(diǎn)的數(shù)量和重要性，但其較高的計(jì)算復(fù)雜度限制了其在大規(guī)模網(wǎng)絡(luò)中的應(yīng)用[19]；介數(shù)中心性和接近中心性是基于全局特性的方法，準(zhǔn)確性很高，但計(jì)算耗時(shí)較長(zhǎng)，限制了它們?cè)诖笮途W(wǎng)絡(luò)中的應(yīng)用[20]。

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

為了在復(fù)雜網(wǎng)絡(luò)中更全面地刻畫(huà)節(jié)點(diǎn)的重要性，本文提出了一種基于改進(jìn)K?shell（Improved K?shell， IK）的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法。該方法綜合考慮節(jié)點(diǎn)的全局影響和局部影響，通過(guò)K?shell方法獲得的節(jié)點(diǎn)[Ks]值反映了節(jié)點(diǎn)的全局影響，然后通過(guò)整合其鄰居節(jié)點(diǎn)與次鄰居節(jié)點(diǎn)的效應(yīng)來(lái)體現(xiàn)節(jié)點(diǎn)的局部影響。具體而言，鄰居節(jié)點(diǎn)的影響依據(jù)節(jié)點(diǎn)的度中心性來(lái)量化，而次鄰居節(jié)點(diǎn)的影響則通過(guò)計(jì)算次鄰居節(jié)點(diǎn)的影響系數(shù)與其數(shù)量的乘積來(lái)確定。為驗(yàn)證所提方法的有效性，在6個(gè)真實(shí)世界網(wǎng)絡(luò)上進(jìn)行了仿真實(shí)驗(yàn)，與現(xiàn)有主流方法相比，本文提出的方法在識(shí)別關(guān)鍵節(jié)點(diǎn)方面表現(xiàn)出顯著的高準(zhǔn)確度和分辨率。

1" 理論基礎(chǔ)

1.1" K?shell方法

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

1） 對(duì)網(wǎng)絡(luò)內(nèi)全部節(jié)點(diǎn)進(jìn)行度值計(jì)算。

2） 移除網(wǎng)絡(luò)中所有度數(shù)為1的節(jié)點(diǎn)及其相連邊，隨后更新網(wǎng)絡(luò)結(jié)構(gòu)并重新計(jì)算各節(jié)點(diǎn)的度數(shù)。此過(guò)程需遞歸進(jìn)行，持續(xù)刪除度數(shù)為1的節(jié)點(diǎn)及其邊，直至網(wǎng)絡(luò)內(nèi)不再存在此類(lèi)節(jié)點(diǎn)。將這些被移除的節(jié)點(diǎn)歸類(lèi)為1?shell層，并賦予它們[Ks]值為1。接著，采用相同的方法，移除網(wǎng)絡(luò)中所有度數(shù)為2的節(jié)點(diǎn)及其連接邊，將這部分被刪除的節(jié)點(diǎn)劃入2?shell層，同時(shí)為其分配[Ks]值為2。

3） 重復(fù)上述迭代過(guò)程，直至網(wǎng)絡(luò)中所有節(jié)點(diǎn)被逐層剝離，形成若干個(gè)K?shell結(jié)構(gòu)。根據(jù)節(jié)點(diǎn)所屬的K?shell層，為每個(gè)節(jié)點(diǎn)分配相應(yīng)的K?shell指數(shù)（[Ks]值）。[Ks]值最大的節(jié)點(diǎn)位于網(wǎng)絡(luò)的核心層，這些節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)和功能具有決定性影響，離核心層越遠(yuǎn)，節(jié)點(diǎn)的[Ks]值和重要性也越小。

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

K?shell方法的排序特點(diǎn)是相同[Ks]值的節(jié)點(diǎn)較多，若網(wǎng)絡(luò)規(guī)模越大，相同[Ks]值的節(jié)點(diǎn)數(shù)量就會(huì)越多，其中的重要節(jié)點(diǎn)也就越難以區(qū)分。如圖1所示，節(jié)點(diǎn)5、節(jié)點(diǎn)6、節(jié)點(diǎn)7、節(jié)點(diǎn)8的[Ks]值都為3，但這幾個(gè)節(jié)點(diǎn)的重要性明顯有一定區(qū)別。為了解決這個(gè)問(wèn)題，本文首先用K?shell方法將網(wǎng)絡(luò)中的節(jié)點(diǎn)分層，再根據(jù)同層節(jié)點(diǎn)的局部結(jié)構(gòu)信息進(jìn)一步評(píng)價(jià)節(jié)點(diǎn)的重要性。

1.2" 度中心性

在無(wú)向圖分析中，節(jié)點(diǎn)度（Degree）是衡量節(jié)點(diǎn)局部影響力的基礎(chǔ)。度中心性通過(guò)量化節(jié)點(diǎn)的度，直接反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中的連接程度。度中心性較高的節(jié)點(diǎn)通常是網(wǎng)絡(luò)中的樞紐節(jié)點(diǎn)，對(duì)信息的傳播和網(wǎng)絡(luò)的穩(wěn)定性具有重要影響[28]。節(jié)點(diǎn)的度中心性可表示為：

[DCi=Di N-1] （1）

式中：[Di]表示節(jié)點(diǎn)[i]的度；[N]表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。節(jié)點(diǎn)[i]的度中心性[DCi]在0～1取值，當(dāng)[DCi]=0時(shí)，表示節(jié)點(diǎn)[i]與網(wǎng)絡(luò)中的其他任何節(jié)點(diǎn)均無(wú)連接關(guān)系；若[DCi]=1，則表示節(jié)點(diǎn)[i]與網(wǎng)絡(luò)中的其他所有節(jié)點(diǎn)均直接相連。

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

2" 本文提出的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法

2.1" 次鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)重要性的影響

由于度中心性忽略了次鄰居節(jié)點(diǎn)的作用，特別是在節(jié)點(diǎn)的度中心性相同時(shí)，該方法就無(wú)法衡量節(jié)點(diǎn)的局部影響。為了說(shuō)明次鄰居節(jié)點(diǎn)對(duì)指定節(jié)點(diǎn)重要性的影響，以圖2為例進(jìn)行解釋。

在圖2中，節(jié)點(diǎn)4位于此小網(wǎng)絡(luò)的中心，節(jié)點(diǎn)4左側(cè)的5個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)0、節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3、節(jié)點(diǎn)10）若要連接到其右側(cè)的5個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)5、節(jié)點(diǎn)6、節(jié)點(diǎn)7、節(jié)點(diǎn)8、節(jié)點(diǎn)9），必須以節(jié)點(diǎn)4為橋梁。在社會(huì)網(wǎng)絡(luò)中，這種特殊而重要的結(jié)構(gòu)被稱(chēng)為結(jié)構(gòu)洞[30]。在社交網(wǎng)絡(luò)中，個(gè)體所占有的“結(jié)構(gòu)洞”數(shù)量越多，其于群體內(nèi)的地位便越顯重要，同時(shí)，其運(yùn)用人際聯(lián)系獲取利益的能力亦隨之增強(qiáng)?？梢?jiàn)，節(jié)點(diǎn)4是極其關(guān)鍵的節(jié)點(diǎn)。但按度中心性分析，節(jié)點(diǎn)4和節(jié)點(diǎn)1的度中心性相同，所以認(rèn)為兩個(gè)節(jié)點(diǎn)同樣重要。從圖中不難發(fā)現(xiàn)，節(jié)點(diǎn)4比節(jié)點(diǎn)1更為重要，這是因?yàn)殡m然這兩個(gè)節(jié)點(diǎn)的度中心性相同，但節(jié)點(diǎn)4的次鄰居節(jié)點(diǎn)數(shù)量（8個(gè)）明顯多于節(jié)點(diǎn)1（3個(gè)），說(shuō)明在節(jié)點(diǎn)的度中心性相同時(shí)，次鄰居節(jié)點(diǎn)數(shù)量越多，節(jié)點(diǎn)的重要性也越大，這也表明節(jié)點(diǎn)的局部影響，不僅受鄰居節(jié)點(diǎn)數(shù)量的影響，還受次鄰居節(jié)點(diǎn)數(shù)量的影響。

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

[α=1N-12] （2）

式中：[α]表示次鄰居節(jié)點(diǎn)的影響系數(shù)；[N]表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。

次鄰居節(jié)點(diǎn)的影響為次鄰居節(jié)點(diǎn)的影響系數(shù)[α]與其數(shù)量的乘積，計(jì)算過(guò)程見(jiàn)式（3）：

[Si=α?Di] （3）

式中：[Si]表示節(jié)點(diǎn)[i]的次鄰居節(jié)點(diǎn)的影響；[α]表示次鄰居節(jié)點(diǎn)的影響系數(shù)；[Di]表示節(jié)點(diǎn)[i]的次鄰居節(jié)點(diǎn)數(shù)量。

2.2" 改進(jìn)K?shell的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法

本文針對(duì)K?shell算法在節(jié)點(diǎn)重要性評(píng)估方面的不足，根據(jù)網(wǎng)絡(luò)局部結(jié)構(gòu)特征，考慮到次鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)重要性的影響，在度中心性方法的基礎(chǔ)上，提出了節(jié)點(diǎn)局部影響的計(jì)算方法，計(jì)算過(guò)程見(jiàn)式（4）：

[Ci=DCi+Si] （4）

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

本研究以K?shell算法及節(jié)點(diǎn)局部影響力為基石，創(chuàng)新性地提出了一個(gè)復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別策略，即基于改進(jìn)K?shell的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法（IK）。在該策略框架下，首先利用K?shell算法在整體網(wǎng)絡(luò)層面識(shí)別關(guān)鍵節(jié)點(diǎn)，以此評(píng)估全局結(jié)構(gòu)的重要性；其次，通過(guò)綜合考慮直接鄰接節(jié)點(diǎn)與次鄰接節(jié)點(diǎn)的影響，來(lái)精確衡量節(jié)點(diǎn)的局部結(jié)構(gòu)影響力。IK方法的計(jì)算過(guò)程見(jiàn)式（5）：

[IKi=Ksi+Ci] （5）

式中：[IKi]為節(jié)點(diǎn)[i]的重要性；[Ksi]為節(jié)點(diǎn)[i]的[Ks]值；[Ci]為節(jié)點(diǎn)[i]的局部影響。

IK方法的設(shè)計(jì)思路：首先，用K?shell將網(wǎng)絡(luò)分層，獲取每個(gè)節(jié)點(diǎn)的[Ks]值，以評(píng)估節(jié)點(diǎn)的全局影響。然后，依據(jù)鄰居節(jié)點(diǎn)和次鄰居節(jié)點(diǎn)對(duì)指定節(jié)點(diǎn)的影響程度區(qū)分同層節(jié)點(diǎn)的重要性，以衡量節(jié)點(diǎn)的局部影響。具體而言，先根據(jù)鄰居節(jié)點(diǎn)數(shù)量計(jì)算節(jié)點(diǎn)的度中心性，并以此對(duì)同層節(jié)點(diǎn)進(jìn)行重要性排序，如排序相同，再按其次鄰居節(jié)點(diǎn)的影響排序。當(dāng)同層內(nèi)節(jié)點(diǎn)的度中心性相同時(shí)，即鄰居節(jié)點(diǎn)數(shù)量相同時(shí)，由于次鄰居節(jié)點(diǎn)的影響與其數(shù)量正相關(guān)，次鄰居節(jié)點(diǎn)數(shù)量多的節(jié)點(diǎn)更重要。IK方法全面評(píng)估了全局與局部網(wǎng)絡(luò)信息對(duì)節(jié)點(diǎn)重要性的雙重作用，在計(jì)算節(jié)點(diǎn)的局部影響力時(shí)，僅納入直接鄰居及次級(jí)鄰居的信息貢獻(xiàn)，以此降低計(jì)算復(fù)雜度。該方法因此能高效識(shí)別復(fù)雜網(wǎng)絡(luò)中的核心節(jié)點(diǎn)，展現(xiàn)出高準(zhǔn)確性及優(yōu)異的分辨率。

IK方法的具體過(guò)程設(shè)計(jì)如下。

算法1：IK方法

輸入：網(wǎng)絡(luò)圖[G=（V，E）]

輸出：節(jié)點(diǎn)重要性排序

For" "網(wǎng)絡(luò)圖[G]中的節(jié)點(diǎn)[V]

Repeat

對(duì)于網(wǎng)絡(luò)圖[G]中度為[K]的節(jié)點(diǎn)

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

更新節(jié)點(diǎn)的[Ks]值

在網(wǎng)絡(luò)圖中刪除節(jié)點(diǎn)[V]

Until網(wǎng)絡(luò)圖[G]中所有剩余節(jié)點(diǎn)的度gt;[K]，[K=K+1]

計(jì)算節(jié)點(diǎn)的直接相連鄰居節(jié)點(diǎn)數(shù)[Pi]和次鄰居節(jié)點(diǎn)數(shù)[Di]

根據(jù)公式（2）計(jì)算次鄰居節(jié)點(diǎn)的影響系數(shù)[α]

根據(jù)公式（3）計(jì)算次鄰居節(jié)點(diǎn)的影響[Si]

根據(jù)公式（4）計(jì)算節(jié)點(diǎn)的局部影響[Ci]

根據(jù)公式（5）計(jì)算節(jié)點(diǎn)的重要性[IKi]

End for

[Ks]值大的節(jié)點(diǎn)先輸出，再按[Pi]值大的進(jìn)行輸出，最后按[IKi]值輸出

2.3" 實(shí)例分析

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

3" 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析

3.1" 實(shí)驗(yàn)數(shù)據(jù)

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

3.2" 評(píng)價(jià)標(biāo)準(zhǔn)

3.2.1" 相關(guān)性指標(biāo)

為了評(píng)價(jià)不同方法的準(zhǔn)確性，選用6種方法（K?shell、DC、MDD、CN、BC和IK）在6個(gè)典型復(fù)雜網(wǎng)絡(luò)（Les miserables、Crime、Email、Facebook、PowerGrid和Train）中進(jìn)行對(duì)比實(shí)驗(yàn)。首先，采用了6種不同方法來(lái)評(píng)估網(wǎng)絡(luò)中各節(jié)點(diǎn)的重要性并排序；其次，為驗(yàn)證所提方法的有效性，本文采用經(jīng)典的SIR模型對(duì)識(shí)別出的關(guān)鍵節(jié)點(diǎn)進(jìn)行傳播模擬。通過(guò)比較不同方法所得節(jié)點(diǎn)重要性排序與SIR模型模擬得到的節(jié)點(diǎn)傳播效率排序，計(jì)算Kendall相關(guān)系數(shù)（[τ]），以量化不同方法與真實(shí)傳播過(guò)程的一致性。

1） SIR模型

本文采用經(jīng)典的SIR（Susceptible?Infected?Recovered）傳播模型來(lái)模擬節(jié)點(diǎn)影響力的擴(kuò)散過(guò)程[27]，將網(wǎng)絡(luò)中的節(jié)點(diǎn)狀態(tài)劃分為易感、感染和恢復(fù)三種。實(shí)驗(yàn)初始時(shí)，僅指定一個(gè)節(jié)點(diǎn)為感染態(tài)，其余節(jié)點(diǎn)均為易感態(tài)。在每個(gè)離散時(shí)間步，感染節(jié)點(diǎn)以概率[β]嘗試感染其鄰接的易感節(jié)點(diǎn)，成功則后者轉(zhuǎn)變?yōu)楦腥緫B(tài)。同時(shí)，感染節(jié)點(diǎn)以概率[γ]轉(zhuǎn)為恢復(fù)態(tài)，且此后不再受感染。

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

2） Kendall系數(shù)

將不同識(shí)別方法和SIR模型仿真得到的排序結(jié)果進(jìn)行比較，計(jì)算Kendall相關(guān)系數(shù)[τ]值[27]。[τ]值越高，說(shuō)明該方法與SIR排序結(jié)果的相關(guān)性越強(qiáng)，即該方法關(guān)鍵節(jié)點(diǎn)識(shí)別的準(zhǔn)確度越高。Kendall相關(guān)系數(shù)[τ]的定義如下：

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

式中：[C]代表兩序列中一致性序列對(duì)的數(shù)量；[D]為不一致性序列對(duì)的數(shù)量；[N]是網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)。

3.2.2" 單調(diào)性指標(biāo)

為了量化不同識(shí)別方法的分辨率，使用排名列表[R]的單調(diào)性指標(biāo)[M（R）]進(jìn)行驗(yàn)證[27]。單調(diào)性指標(biāo)[M（R）]被廣泛用于評(píng)估排序結(jié)果的區(qū)分度，其值越大，表明擁有相同重要性評(píng)分的節(jié)點(diǎn)越少，即排序結(jié)果的單調(diào)性越強(qiáng)。單調(diào)性指標(biāo)[MR]的表達(dá)式為：

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

式中：[R]代表節(jié)點(diǎn)重要性排序結(jié)果；[n]代表排序結(jié)果中節(jié)點(diǎn)的總數(shù)；[nr]代表節(jié)點(diǎn)重要性排序結(jié)果中相同的節(jié)點(diǎn)個(gè)數(shù)。用[MR]衡量節(jié)點(diǎn)重要性排序結(jié)果的單調(diào)性，[MR]在0和1之間取值，其中[MR]=0時(shí)，代表網(wǎng)絡(luò)中全部節(jié)點(diǎn)的重要性均相同；[MR]=1時(shí)，代表網(wǎng)絡(luò)中全部節(jié)點(diǎn)的重要性均不同。

3.2.3" 魯棒性驗(yàn)證

為了評(píng)價(jià)關(guān)鍵節(jié)點(diǎn)識(shí)別方法的有效性，本文從網(wǎng)絡(luò)魯棒性角度分析了節(jié)點(diǎn)移除后網(wǎng)絡(luò)連通性的變化[37]。在復(fù)雜網(wǎng)絡(luò)環(huán)境中，連通分量構(gòu)成網(wǎng)絡(luò)的子圖，其中任意兩節(jié)點(diǎn)間均保持連通狀態(tài)。特別地，最大連通子圖指的是在節(jié)點(diǎn)刪除導(dǎo)致網(wǎng)絡(luò)分裂后，所含節(jié)點(diǎn)數(shù)量最多的那個(gè)連通分量，此指標(biāo)能有效表征復(fù)雜網(wǎng)絡(luò)的整體連通水平。當(dāng)移除網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)的最大連通子圖規(guī)模將顯著縮減。為了量化這種影響，本文采用最大連通系數(shù)作為評(píng)價(jià)指標(biāo)，其定義為：移除節(jié)點(diǎn)后，網(wǎng)絡(luò)中最大連通子圖所包含的節(jié)點(diǎn)數(shù)與原始網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比值[37]，計(jì)算公式如式（8）所示：

[r=Sn] （8）

式中：[r]表示網(wǎng)絡(luò)的最大連通系數(shù)；[n]為原始網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)；[S]表示移除部分節(jié)點(diǎn)后網(wǎng)絡(luò)的最大連通子圖包含的節(jié)點(diǎn)數(shù)。

網(wǎng)絡(luò)魯棒性是用來(lái)衡量移除任意節(jié)點(diǎn)后網(wǎng)絡(luò)中的剩余節(jié)點(diǎn)之間仍然能夠保持連通能力的平均影響力[38]。利用最大連通系數(shù)來(lái)計(jì)算網(wǎng)絡(luò)的魯棒性，計(jì)算公式如式（9）所示：

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

式中：[R]表示網(wǎng)絡(luò)的魯棒性；[rj]表示移除[j]個(gè)節(jié)點(diǎn)后的最大連通系數(shù)。

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

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

3.3.1" 準(zhǔn)確性分析

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

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

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

3.3.3" 魯棒性實(shí)驗(yàn)

為了評(píng)價(jià)節(jié)點(diǎn)識(shí)別方法的有效性，本文利用6種識(shí)別方法分別將6個(gè)網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)實(shí)施了重要性評(píng)估與排序。隨后，依據(jù)節(jié)點(diǎn)重要性的遞減次序，依次移除節(jié)點(diǎn)及其連邊，分析網(wǎng)絡(luò)最大連通系數(shù)的變化趨勢(shì)，分析不同識(shí)別方法對(duì)網(wǎng)絡(luò)魯棒性的影響，從而評(píng)價(jià)方法的有效性，結(jié)果如圖4和表5所示。

圖4顯示了節(jié)點(diǎn)的移除比例與網(wǎng)絡(luò)最大連通系數(shù)的關(guān)系曲線，橫坐標(biāo)是節(jié)點(diǎn)的移除比例，即移除的節(jié)點(diǎn)數(shù)量占總節(jié)點(diǎn)數(shù)量的比例，縱坐標(biāo)為移除節(jié)點(diǎn)后的最大連通系數(shù)[r] 。由圖4可知：在6個(gè)網(wǎng)絡(luò)中，隨著移除節(jié)點(diǎn)比例的增大，網(wǎng)絡(luò)的最大連通系數(shù)均表現(xiàn)為下降的趨勢(shì)；在Les miserables、Crime、Email和PowerGrid網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)移除比例達(dá)到0.2時(shí)，IK方法相較于其他識(shí)別方法，網(wǎng)絡(luò)最大連通系數(shù)的下降幅度更為顯著，分別為87.1%、88.5%、48.4%和97.8%，表明IK方法在這4個(gè)網(wǎng)絡(luò)中表現(xiàn)最佳。

在Train網(wǎng)絡(luò)中，只有在0.187～0.485范圍內(nèi)的移除節(jié)點(diǎn)比例時(shí)，通過(guò)IK方法移除節(jié)點(diǎn)后的最大連通系數(shù)大于BC，且小于其他方法，表明在此范圍內(nèi)BC方法關(guān)鍵節(jié)點(diǎn)識(shí)別能力最佳，IK方法次之；而當(dāng)移除的節(jié)點(diǎn)比例在此范圍之外時(shí)，特別是在移除節(jié)點(diǎn)初期，IK方法的節(jié)點(diǎn)識(shí)別能力最佳，而B(niǎo)C方法表現(xiàn)不理想。

綜合來(lái)看，與其他方法相比，IK方法在Train網(wǎng)絡(luò)中具有較好的節(jié)點(diǎn)識(shí)別能力。同理，在Facebook網(wǎng)絡(luò)中，BC方法的節(jié)點(diǎn)識(shí)別效果最佳，IK次之。

綜上所述，在不同的復(fù)雜網(wǎng)絡(luò)中，IK是一種較為有效的關(guān)鍵節(jié)點(diǎn)識(shí)別方法。表5顯示了6種方法識(shí)別的節(jié)點(diǎn)被移除后網(wǎng)絡(luò)的魯棒性[R]值。[R]值越小，說(shuō)明該方法識(shí)別的關(guān)鍵節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)魯棒性的影響越大，該方法的性能也就越好。

由表5可知，在除Facebook外的其他5個(gè)網(wǎng)絡(luò)中，IK方法識(shí)別的節(jié)點(diǎn)被移除后網(wǎng)絡(luò)的[R]值最小，說(shuō)明IK方法在這5個(gè)網(wǎng)絡(luò)中的識(shí)別效果最佳；在Facebook網(wǎng)絡(luò)中，利用IK方法得到的[R]值僅低于BC，表明IK方法在該網(wǎng)絡(luò)中具有較好的節(jié)點(diǎn)識(shí)別能力。因此，本文提出的方法能夠有效地識(shí)別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

4" 結(jié)" 論

本文針對(duì)傳統(tǒng)K?shell方法存在的準(zhǔn)確性和分辨率不高的問(wèn)題，綜合考慮節(jié)點(diǎn)的全局和局部影響，提出了一種基于改進(jìn)K?shell的關(guān)鍵節(jié)點(diǎn)識(shí)別方法（IK）。

首先，運(yùn)用K?shell算法對(duì)網(wǎng)絡(luò)進(jìn)行分層處理，以獲取網(wǎng)絡(luò)中各節(jié)點(diǎn)的[Ks]值，該值用以衡量節(jié)點(diǎn)的全局影響力。

隨后，通過(guò)分析節(jié)點(diǎn)的鄰居及次鄰居對(duì)其重要性的貢獻(xiàn)，來(lái)揭示節(jié)點(diǎn)的局部影響力特征。其中，鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的影響程度以其度中心性來(lái)具體表征；在評(píng)價(jià)次鄰居節(jié)點(diǎn)的影響時(shí)，通過(guò)定義次鄰居節(jié)點(diǎn)的影響系數(shù)[α]來(lái)表示單個(gè)次鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)重要性的影響，然后用次鄰居節(jié)點(diǎn)影響系數(shù)與次鄰居節(jié)點(diǎn)數(shù)量的乘積來(lái)表征次鄰居節(jié)點(diǎn)的影響。

最終，利用節(jié)點(diǎn)的[Ks]值和度中心性以及次鄰居節(jié)點(diǎn)的影響三者之和來(lái)評(píng)價(jià)節(jié)點(diǎn)的重要性。對(duì)于同殼層節(jié)點(diǎn)而言，節(jié)點(diǎn)的度中心性相同時(shí)，即鄰居節(jié)點(diǎn)數(shù)相同時(shí)，次鄰居節(jié)點(diǎn)數(shù)量多的節(jié)點(diǎn)更重要。以相關(guān)性、單調(diào)性以及魯棒性為評(píng)價(jià)標(biāo)準(zhǔn)，將該方法在6個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，與其他方法相比，本文提出的方法能有效地識(shí)別不同復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，并具有較高的分辨率和準(zhǔn)確性。

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

參考文獻(xiàn)

[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] 楊景峰，朱大鵬，趙瑞琳.城市軌道交通網(wǎng)絡(luò)特性與級(jí)聯(lián)失效魯棒性分析[J].計(jì)算機(jī)工程與應(yīng)用，2022，58（7）：250?258.

[9] 郭明健，高巖.基于復(fù)雜網(wǎng)絡(luò)理論的電力網(wǎng)絡(luò)抗毀性分析[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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] 姜敏勤，石小晶，楊鈺，等.基于多屬性評(píng)價(jià)的糧食供應(yīng)鏈網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別[J].糧食科技與經(jīng)濟(jì)，2023，48（4）：83?89.

[12] 韓奕，孫百兵，王軍國(guó)，等.基于關(guān)鍵節(jié)點(diǎn)識(shí)別算法的重點(diǎn)人分析研究[J].北京航空航天大學(xué)學(xué)報(bào)，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] 朱曉霞，胡小雪.基于改進(jìn)k?shell算法的節(jié)點(diǎn)影響力的識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用，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] 吳亞麗，任遠(yuǎn)光，董昂，等.基于鄰域K?shell分布的關(guān)鍵節(jié)點(diǎn)識(shí)別方法[J].計(jì)算機(jī)工程與應(yīng)用，2024，60（2）：87?95.

[28] 閆泓任，馬國(guó)帥，錢(qián)宇華.基于節(jié)點(diǎn)度中心性的無(wú)監(jiān)督特征選擇[J].數(shù)據(jù)采集與處理，2019，34（2）：312?321.

[29] 謝麗霞，孫紅紅，楊宏宇，等.基于K?shell的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 吳英晗，田闊，李明達(dá)，等.利用節(jié)點(diǎn)傳播熵識(shí)別超網(wǎng)絡(luò)重要節(jié)點(diǎn)[J].計(jì)算機(jī)工程與應(yīng)用，2023，59（19）：66?74.

[38] 陳雯柏，崔曉麗，郝翠，等.一種物聯(lián)網(wǎng)系統(tǒng)層次型抗毀性拓?fù)錁?gòu)建方法[J].北京郵電大學(xué)學(xué)報(bào)，2018，41（5）：103?109.

作者簡(jiǎn)介：李天雨（1996—），男，河北保定人，碩士研究生，主要從事社會(huì)網(wǎng)絡(luò)數(shù)字化研究與應(yīng)用。

滕桂法（1963—），男，河北衡水人，博士研究生，教授，博士生導(dǎo)師，主要研究方向?yàn)槿斯ぶ悄芘c大數(shù)據(jù)、智能農(nóng)業(yè)。

姚竟發(fā)（1983—），男，河北衡水人，博士研究生，講師，主要研究方向?yàn)槿斯ぶ悄芘c多模態(tài)大數(shù)據(jù)技術(shù)。

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（U20A20180）；河北省人力資源和社會(huì)保障課題（JRS?2023?3078）