摘 要：K-shell分解法能快速識別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，但是無法辨別同殼層內(nèi)節(jié)點重要性的差異，并且低估了處于網(wǎng)絡(luò)邊緣位置的高度值節(jié)點的重要性。針對這兩個問題，提出一種基于K-shell位置和兩階鄰居的節(jié)點重要性評估方法。該方法根據(jù)K-shell分解過程中節(jié)點移除的順序細(xì)化節(jié)點的全局位置信息，然后綜合考慮節(jié)點的局部拓?fù)浣Y(jié)構(gòu)信息和全局位置信息，利用兩步長內(nèi)鄰居節(jié)點的K-shell位置信息度量節(jié)點的重要性。在八個真實網(wǎng)絡(luò)上用傳染病模型進(jìn)行仿真實驗，結(jié)果表明，所提方法與其他五種相關(guān)方法相比能更準(zhǔn)確有效地評估并區(qū)分節(jié)點的重要性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)； 關(guān)鍵節(jié)點； K-shell分解法； 兩階鄰居； 傳染病模型

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2023）03-015-0738-05

doi：10.19734/j.issn.1001-3695.2022.08.0402

Evaluation method of node importance in complex networks based on K-shell

position and neighborhood within two steps

Xiong Caiquan， Gu Xiaohui， Wu Xinyun

（School of Computer Science， Hubei University of Technology， Wuhan 430068， China）

Abstract：K-shell method can quickly identify influential nodes in complex networks. However， it is hard to distinguish the differences in the importance of these nodes. In addition， it underestimates the importance of high degree nodes at the edge of the network. Aiming at these two shortcomings of the K-shell method， this paper proposed an approach based on the K-shell position and neighborhood within two steps to identify influential nodes in complex networks. It refined the global position of the node according to the removal order during K-shell decomposition. Considering the local topology and global position of nodes， the proposed method identified the influential nodes based on the K-shell position of the neighborhood within two steps. To simulate the propagation process with epidemic model on eight real networks， the experiment results show that the proposed method can identify and rank the influential nodes compared with other five relative methods with better accuracy and efficiency.

Key words：complex network; influential nodes; K-shell method; neighborhood within two steps; epidemic model

0 引言

近年來，識別復(fù)雜網(wǎng)絡(luò)中重要節(jié)點的研究引起廣泛的關(guān)注。所謂重要節(jié)點，就是相較于網(wǎng)絡(luò)中其他節(jié)點而言，能夠在更大程度上影響網(wǎng)絡(luò)結(jié)構(gòu)與功能的特殊節(jié)點［1］。例如，交通網(wǎng)絡(luò)中少數(shù)路段的擁堵導(dǎo)致整個城市的交通堵塞，電力網(wǎng)絡(luò)中關(guān)鍵變電站故障可能引發(fā)大規(guī)模停電，病毒傳播網(wǎng)絡(luò)中的超級傳播者會大幅加速病毒的傳播，社交網(wǎng)絡(luò)中名人的言論傳播速度更快、范圍更廣。因此，探究有效節(jié)點重要性評估方法來識別網(wǎng)絡(luò)中具有影響力的關(guān)鍵節(jié)點有重要的理論意義和應(yīng)用價值。

經(jīng)典的節(jié)點重要性評估方法多從節(jié)點近鄰、全局路徑、特征向量和網(wǎng)絡(luò)位置四個角度挖掘節(jié)點的重要程度?；诠?jié)點近鄰的重要性評估方法有度中心性［2］、半局部中心性［3］和H指數(shù)中心性［4］等，度中心性只考慮節(jié)點的直接鄰居、而半局部中心性則擴大考查范圍至4階鄰居，H指數(shù)中心表示節(jié)點有h個度值不小于h的鄰居，兼顧了鄰居節(jié)點的數(shù)目和度值?；诠?jié)點近鄰的評估方法簡單直接，但考慮的節(jié)點信息有限，因此評估的結(jié)果往往并不準(zhǔn)確?；诼窂降墓?jié)點重要性評估方法有介數(shù)中心性［5］、接近中心性［6］和Katz中心性［7］等，介數(shù)中心性和接近中心分別以節(jié)點間的最短路徑數(shù)目和平均距離來刻畫節(jié)點的重要程度，Katz中心性則認(rèn)為除最短路徑外的其他可達(dá)路徑同樣值得考慮，根據(jù)步長對路徑進(jìn)行加權(quán)，路徑越短權(quán)重越大?；诼窂降姆椒〞r間復(fù)雜度過高，不適用于大型網(wǎng)絡(luò)。基于特征向量的評估方法有特征向量中心性［2］、PageRank算法［8］和LeaderRank算法［9］等，特征向量中心性通過計算網(wǎng)絡(luò)鄰接矩陣的特征向量得到節(jié)點的重要性分值，PageRank和LeaderRank算法通過模擬用戶瀏覽網(wǎng)頁的過程，使節(jié)點的重要性分值隨著訪問路徑增加?；谔卣飨蛄康脑u估方法既考慮了鄰居節(jié)點的數(shù)量，也考慮了鄰居節(jié)點的質(zhì)量，但是這

類方法鄰間的重要性會相互增強，導(dǎo)致局部聚集程度高的節(jié)點的重要性容易出現(xiàn)虛高的現(xiàn)象?；诰W(wǎng)絡(luò)位置的評估方法最常見的是K-shell分解法［10］及其改進(jìn)方法［11～14］，通過判斷節(jié)點是否處在網(wǎng)絡(luò)的中心位置來評估節(jié)點的重要性，簡單并且高效。

一般認(rèn)為，節(jié)點越靠近網(wǎng)絡(luò)中心位置，其影響力就越大?；谶@一思想，Kitsak等人［10］開創(chuàng)性地提出K-shell分解法，通過遞歸剝離度小于等于K的節(jié)點將網(wǎng)絡(luò)逐層劃分，因其具有較低的時間復(fù)雜度而被廣泛地研究和應(yīng)用，但區(qū)分度過于粗?；?，導(dǎo)致節(jié)點的重要性評估不夠精準(zhǔn)。目前，許多研究工作都是以提高K-shell分解法的區(qū)分度為目的展開的。Zeng等人［11］提出了一種同時考慮剩余鄰居節(jié)點和被移除鄰居節(jié)點的混合度分解方法（MDD）。Wang等人［12］用K-shell分解時遞歸剝離的迭代次數(shù)來區(qū)分同一殼層內(nèi)的節(jié)點。Bae等人［13］在改進(jìn)K-shell算法時利用第二層鄰居節(jié)點的K-shell值之和作為鄰域核心度來評估節(jié)點的重要性。Wang等人［14］引入節(jié)點信息熵反映節(jié)點的影響力，依次移除每個K-shell層中信息熵最高的節(jié)點，同時兼顧核心位置和邊緣位置的高影響力節(jié)點。李懂等人［15］從多屬性融合的角度提出一種融合度和K核迭代次數(shù)的方法，綜合考慮了節(jié)點的局部和全局屬性。Yang等人［16］基于K-shell分解提出一種改進(jìn)的重力模型來識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點。Giridhar［17］利用節(jié)點的度和K-shell值來給邊加權(quán)，將節(jié)點的全局位置信息和局部影響力相結(jié)合來體現(xiàn)節(jié)點的重要程度。游倩婧等人［18］提出一種基于重疊盒覆蓋的節(jié)點重要性評估方法，綜合考慮了節(jié)點自身屬性以及整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)?，F(xiàn)有的基于K-shell分解法的改進(jìn)方法忽略了節(jié)點更確切的全局位置信息，并且沒有充分考慮鄰居節(jié)點對節(jié)點影響力貢獻(xiàn)的差異。

本文提出了一種基于K-shell位置和兩階鄰居的節(jié)點重要性評估方法（method based on K-shell position and neighborhood within two steps，KPN）。利用K-shell分解時節(jié)點的剝離順序細(xì)化節(jié)點的全局拓?fù)湮恢眯畔?，在一定程度上克服了K-shell分解時同層節(jié)點無法區(qū)分的缺點。用兩層鄰居的全局位置信息量化鄰居節(jié)點對節(jié)點影響力的貢獻(xiàn)，這種貢獻(xiàn)逐層衰減。本文方法綜合了節(jié)點的全局位置與局部拓?fù)浣Y(jié)構(gòu)信息，對節(jié)點重要性的評估更合理。

1 理論基礎(chǔ)

1.1 K-shell方法

K-shell分解法［10］是一種粗粒度化的節(jié)點重要性分類方法，根據(jù)節(jié)點位置信息由邊緣到核心逐層劃分網(wǎng)絡(luò)。K-shell值反映了節(jié)點在網(wǎng)絡(luò)中的全局位置，K-shell值越大，節(jié)點的位置越核心，節(jié)點也就越重要。K-shell分解法的步驟如下：a）計算網(wǎng)絡(luò)中所有節(jié)點的度數(shù)，取最小的度值記為K；b）刪除網(wǎng)絡(luò)中所有度為K的節(jié)點，更新網(wǎng)絡(luò)并重新計算度值，遞歸刪除度小于等于K的節(jié)點直到網(wǎng)絡(luò)中的節(jié)點度都大于K，將刪除的節(jié)點都標(biāo)記為K-shell；c）重復(fù)步驟a）b），直到網(wǎng)絡(luò)中所有節(jié)點都被剝離，并標(biāo)記了K-shell值。

1.2 SIR模型

經(jīng)典傳染病模型有SI［19］、SIR［20］和SIS［21］，常用于信息傳播過程仿真，其中應(yīng)用最為廣泛的就是SIR模型。本文采用SIR模型對節(jié)點的影響力擴散過程進(jìn)行仿真實驗，將實驗結(jié)果作為節(jié)點的真實影響力，并以此為目標(biāo)值評價節(jié)點重要性評估方法的有效性。在SIR模型中，每個節(jié)點都有一個狀態(tài)：易感染（susceptible state）、感染態(tài)（infected state）、恢復(fù)態(tài)（recovered state）。初始時，除一個節(jié)點是感染態(tài)以外，所有節(jié)點都為易感染態(tài)，在每一個時間間隔內(nèi)，感染態(tài)的節(jié)點都以概率β去感染它易感染狀態(tài)的鄰居，以概率γ轉(zhuǎn)為恢復(fù)狀態(tài)，一旦恢復(fù)就會免疫不再被感染。這個過程重復(fù)執(zhí)行直到網(wǎng)絡(luò)中沒有感染態(tài)的節(jié)點。傳播停止時恢復(fù)節(jié)點的數(shù)目作為初始感染節(jié)點的傳播能力，即影響力。不失一般性，本文設(shè)定傳播閾值βth =〈k〉/〈k2〉，感染率β在傳播閾值附近取值，恢復(fù)概率γ為1。執(zhí)行傳播過程100次取平均值作為節(jié)點的真實影響力。

1.3 SI模型

SI模型是最簡單的傳染病模型，本文采用SI模型模擬節(jié)點影響力擴散的過程，根據(jù)網(wǎng)絡(luò)中節(jié)點狀態(tài)變化的快慢評價各節(jié)點重要性評估方法的優(yōu)劣。在SI模型中，網(wǎng)絡(luò)中的節(jié)點可能的狀態(tài)只有易感染（susceptible state）和感染態(tài)（infected state）兩種。在每一個時間間隔內(nèi)，感染態(tài)的節(jié)點都以概率β去感染它易感染狀態(tài)的鄰居，節(jié)點一旦被感染則永遠(yuǎn)無法恢復(fù)，并且還具備感染其他易感染態(tài)節(jié)點的能力，直到網(wǎng)絡(luò)中所有節(jié)點都處于感染態(tài)，傳播過程結(jié)束。感染率β在傳播閾值βth附近取值，為減小隨機誤差，實驗結(jié)果取100次實驗的平均值。

2 基于K-shell位置和兩階鄰居節(jié)點重要性評估法

2.1 同K-shell值節(jié)點的重要性區(qū)分方法

用K-shell值代表節(jié)點的重要性過于粗略，大量結(jié)構(gòu)和功能存在明顯差異的節(jié)點具有相同的K-shell值。遞歸移除過程中的移除順序隱含了同一K-shell層內(nèi)節(jié)點之間的相對位置信息，遞歸層次越深，節(jié)點越晚被移除，節(jié)點的位置也越靠近下一殼層。因此，可以用節(jié)點的移除順序確定節(jié)點在同層殼內(nèi)的位置信息。標(biāo)記節(jié)點移除順序R-order的過程如下：a）計算網(wǎng)絡(luò)中所有節(jié)點的度，取最小的度值記為K，并且將所有節(jié)點的R-order值初始化為1；b）刪除網(wǎng)絡(luò)中所有度為K的節(jié)點，將這些節(jié)點的移除順序標(biāo)記為R-order，更新網(wǎng)絡(luò)并重新計算度值，遞歸刪除度小于等于K的節(jié)點并標(biāo)記相應(yīng)的R-order，直到網(wǎng)絡(luò)中的節(jié)點度都大于K，在每一次遞歸的過程中，R-order值遞增1；c）重復(fù)步驟a）b），直到網(wǎng)絡(luò)中所有節(jié)點都被剝離，并標(biāo)記了R-order。

如圖1所示，根據(jù)R-order在K-shell層內(nèi)繼續(xù)分層，具有相同K-shell值的節(jié)點之間的差異更加明顯了，節(jié)點在網(wǎng)絡(luò)中的位置也更精準(zhǔn)。考慮遞歸移除順序的K-shell位置信息KPi為

其中：ks為節(jié)點vi的K-shell值；ks|next為下一殼層的K-shell值;Ri為節(jié)點vi的移除順序R-order的值;Rmax為節(jié)點vi這一K-shell節(jié)點移除順序的最大值。另外，當(dāng)節(jié)點處于K-shell值最大的殼層時，ks|next=ks+1。圖1中所有節(jié)點的KP值計算結(jié)果如表1所示。不難看出，KP值比K-shell值能更進(jìn)一步區(qū)分節(jié)點的重要性，KP值反映的節(jié)點在網(wǎng)絡(luò)中的位置信息也更加詳細(xì)。

2.2 兩階鄰居對影響力的貢獻(xiàn)

詳細(xì)的K-shell位置信息KP在一定程度上識別了同殼層內(nèi)節(jié)點的重要性差異，但基于網(wǎng)絡(luò)全局屬性的度量不可避免地忽略了節(jié)點的鄰域結(jié)構(gòu)信息，而節(jié)點影響力的傳播往往發(fā)生在有限的范圍內(nèi)［22］，因此，節(jié)點的局部傳播能力更能反映節(jié)點的影響力。一般認(rèn)為，節(jié)點的影響會擴散到有效范圍內(nèi)的鄰居節(jié)點，反之，節(jié)點的影響力是有效范圍內(nèi)鄰居節(jié)點共同影響的結(jié)果?？紤]到影響力的傳播具有有效范圍有限和逐級衰減的特性，所以僅考慮兩步長內(nèi)的鄰居節(jié)點，并且直接鄰居對節(jié)點的影響大于間接鄰居。另外，具有不同影響力的鄰居對節(jié)點的影響力的貢獻(xiàn)必然不同，將詳細(xì)的K-shell位置作為鄰居節(jié)點對節(jié)點影響力的貢獻(xiàn)值，既體現(xiàn)了這種貢獻(xiàn)的差異，還兼顧了節(jié)點的全局位置信息。因此，對兩步長內(nèi)鄰居節(jié)點的KP值加權(quán)求和來度量節(jié)點的影響力。基于以上分析，計算節(jié)點影響力的公式為

其中：0≤β≤α≤1，α + β = 1。為不失一般性，本文實驗中， α=0.7，β=0.3，j∈Γ（i）為vi的一階鄰居節(jié)點集，k∈Γ（j）為vj的二階鄰居節(jié)點集。

2.3 實例分析

圖1中網(wǎng)絡(luò)在KPN方法及其對比方法下的排序結(jié)果如表2所示。由表2可知，DC方法［2］、KS方法［10］和MDD方法［11］對節(jié)點重要性的區(qū)分能力明顯低于另外三種方法。KSIF方法［12］中節(jié)點c的排名比節(jié)點a靠前，節(jié)點e的排名比節(jié)點f靠前，但是節(jié)點a與c的網(wǎng)絡(luò)位置相同，鄰居卻比節(jié)點c多，并且刪除節(jié)點a后網(wǎng)絡(luò)將不是一個連通圖，顯然節(jié)點a比節(jié)點c更重要，節(jié)點e與f同理。IKS方法［14］中節(jié)點k比節(jié)點e靠前，其他五種方法則相反，雖然節(jié)點k的鄰居數(shù)量比節(jié)點e多，但節(jié)點e鄰居的質(zhì)量要更好，并且節(jié)點e比節(jié)點k更靠近網(wǎng)絡(luò)核心，綜合來看節(jié)點e的排名應(yīng)該優(yōu)于節(jié)點k，因此KPN方法的排序結(jié)果最優(yōu)。

2.4 時間復(fù)雜度分析

本節(jié)將對KPN算法進(jìn)行時間復(fù)雜度分析，其具體計算步驟如算法1所示。首先，標(biāo)記每個節(jié)點的K-shell內(nèi)移除順序Ri，其時間復(fù)雜度為O（m + n）。根據(jù)ks值和移除順序Ri遍歷圖中的每個節(jié)點求其詳細(xì)的K-shell位置KP，其時間復(fù)雜度為O（n）。其次，根據(jù)兩階鄰居的KP值計算節(jié)點的KPN 值，需要遍歷節(jié)點的一階、二階鄰居，每階平均訪問〈k〉個節(jié)點，所以時間復(fù)雜度為O（n ×〈k〉2）。由此可以看出，KPN算法的時間復(fù)雜度取決于KPN值的計算，時間復(fù)雜度為O（n ×〈k〉2），其中，n為網(wǎng)絡(luò)的節(jié)點數(shù)，〈k〉為網(wǎng)絡(luò)的平均度。

算法1 KPN算法

輸入：復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集圖G（V，E）。

輸出：每個節(jié)點的重要性得分值KPN。

for i=1 to n

KP［i］←ksi+Rimax（Ri）+1（ksnext-ksi）

end for

for i=1 to n

KPN［i］←KP［i］

for 節(jié)點j為節(jié)點i的鄰居

KPN［i］←KPN［i］+α×KP［j］

for 節(jié)點k為節(jié)點j的鄰居

if k = i //節(jié)點的二階鄰居為自身

continue

end if

KPN［i］←KPN［i］+β×KP［k］

end for

end for

end for

表3列出了六種不同評估方法的時間復(fù)雜度，這六種評估方法所包含的網(wǎng)絡(luò)信息有局部、全局和兩者混合三種類型。其中n為節(jié)點總數(shù)，m為連邊總數(shù)，一般的n＜m，〈k〉為網(wǎng)絡(luò)的平均度。

3 實驗數(shù)據(jù)與結(jié)果分析

3.1 實驗數(shù)據(jù)

為了評價算法排序結(jié)果的準(zhǔn)確性，本文選取了八個真實網(wǎng)絡(luò)數(shù)據(jù)集，如表3所示，實驗過程中將這些真實網(wǎng)絡(luò)均視為無權(quán)無向圖。這八個真實網(wǎng)絡(luò)分別是：a）Jazz［23］，爵士音樂家合作網(wǎng)絡(luò)；b）USAir［24］，1997年美國航班路線網(wǎng)絡(luò)；c）Email［25］，西班牙Rovira大學(xué)電子郵件網(wǎng)絡(luò)；d）PowerGrid［26］，美國電力網(wǎng)絡(luò)；e）Hamsterster，名為Hamsterster的網(wǎng)站上用戶之間的親友關(guān)系網(wǎng)絡(luò)；f）Hepth［27］，高能理論科學(xué)家合作網(wǎng)絡(luò)；g）PGP［28］，隱私保護(hù)算法的用戶網(wǎng)絡(luò)；h）Enron［29］，電子郵件交流網(wǎng)絡(luò)。網(wǎng)絡(luò)的統(tǒng)計特征如表4所示，其中n為節(jié)點數(shù)，m為邊數(shù)，〈k〉為網(wǎng)絡(luò)平均度，c為聚類系數(shù)，〈d〉為平均最短路徑，βth為SIR模型傳播閾值，β為實際傳播率取值。

3.2 評價標(biāo)準(zhǔn)

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

為了評價節(jié)點重要性排序算法的有效性，需要求算法得出的排序結(jié)果與真實影響力排序序列的相關(guān)性。利用肯德爾系數(shù)［30］來測量兩個排序列表的相關(guān)性，一個排序列表為節(jié)點重要性排序算法得出的排序結(jié)果，另一個是應(yīng)用SIR模型獲得的節(jié)點真實影響力排序列表?？系聽栂嚓P(guān)系數(shù)的值越大，說明該節(jié)點重要性評估算法的效果越好。假設(shè)存在兩個包含n個節(jié)點的序列X和Y，從排序列表X和Y中隨機選擇一對觀察組（xi ，yi） （xj，yj），如果xi＞xj ， yi＞yj（或者xi＜xj，yi＜yj）則說明觀察組是相關(guān)的（concordant），若xi＞ xj，yi＜yj（或者xi＜xj ， yi＞yj）則說明是不相關(guān)的（discordant）。對于序列X與Y，肯德爾相關(guān)系數(shù)τ的定義如下：

τ（X，Y）=nc-nd（nt-nt1）（nt-nt2）（3）其中：nc是相關(guān)觀察組的數(shù)量；nd是不相關(guān)觀察組的數(shù)量；nt=n（n-1）/2，n是排序向量里元素個數(shù)；nt1=∑iti（ti-1）/2;nt2=∑jtj（tj-1）/2。將X中的相同元素組成小集合，ti表示第i個集合所包含的元素數(shù)。

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

單調(diào)性指標(biāo)［13］反映了重要性排序結(jié)果的單調(diào)程度，單調(diào)性指標(biāo)值越大，具有相同重要性的節(jié)點數(shù)目越少，算法的效果就越好。單調(diào)性指標(biāo)的定義如下：

其中：R為節(jié)點重要性排序算法得到的重要性排序向量;N為網(wǎng)絡(luò)的節(jié)點個數(shù)；Nr為重要性相同的節(jié)點數(shù)量。M（R）∈［0，1］，當(dāng)M（R）=1時，排序向量R完全單調(diào)，表示網(wǎng)絡(luò)中所有節(jié)點的重要性都不同；當(dāng)M（R）=0時，則表示網(wǎng)絡(luò)中所有節(jié)點的重要性都相同。

3.3 實驗結(jié)果分析

本文選取度中心性（DC）［2］、K-shell分解法（KS）［10］、混合度分解法（MDD）［11］、K-shell分解迭代特征法（KSIF）［12］、改進(jìn)的K-shell分解法（IKS）［14］作為對比方法，并記錄了不同的節(jié)點重要性評估方法在八個真實網(wǎng)絡(luò)數(shù)據(jù)集中的實驗結(jié)果，從有效性、單調(diào)性兩個方面比較不同節(jié)點重要性評估方法的表現(xiàn)。

3.3.1 有效性分析

為了驗證KPN算法的有效性，對比各節(jié)點重要性評估方法的排序結(jié)果與在不同傳播概率下SIR模型得到節(jié)點影響力排序結(jié)果之間的肯德爾相關(guān)系數(shù)。如圖2所示，傳播率β在βth附近取值，垂直虛線的橫坐標(biāo)取值為βth。

在PowerGrid 和Hepth數(shù)據(jù)集中，各評估方法的相關(guān)系數(shù)隨著傳播率的升高反而降低，DC、K-shell和MDD三種方法下降尤為明顯。因為在傳播率較小時SIR傳播的范圍局限于節(jié)點的鄰域，當(dāng)傳播率過大時，感染態(tài)的節(jié)點會快速影響到整個網(wǎng)絡(luò)，從而無法有效識別出關(guān)鍵節(jié)點。節(jié)點的度或全局位置等單一網(wǎng)絡(luò)信息不能全面地反映節(jié)點的真實影響力，這種缺陷在稀疏網(wǎng)絡(luò)中表現(xiàn)尤為明顯。而在Jazz、Email、Hamsterster、PGP和Enron數(shù)據(jù)集中，當(dāng)傳播率β接近或大于βth時，KPN算法與節(jié)點真實影響力的相關(guān)性顯著高于其他算法，說明KPN算法得出的節(jié)點重要性排序結(jié)果更接近節(jié)點真實影響力排序結(jié)果，尤其在聚類系數(shù)較低的網(wǎng)絡(luò)中?？傮w上，KPN算法的相關(guān)系數(shù)表現(xiàn)優(yōu)于其他方法，與IKS方法在一些數(shù)據(jù)集上結(jié)果較為接近。

為了進(jìn)一步評估KPN算法的有效性，即能否準(zhǔn)確識別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，在SI模型上再進(jìn)行傳播仿真實驗，選取各評估方法得分前十的節(jié)點作為初始感染節(jié)點，記錄網(wǎng)絡(luò)中感染態(tài)節(jié)點數(shù)目F（t）隨時間步長t的變化情況。如圖3所示，在Jazz和USAir網(wǎng)絡(luò)中，以KPN算法評估的重要性排名前十的節(jié)點作為初始感染節(jié)點時，網(wǎng)絡(luò)中感染節(jié)點數(shù)目上升的速度是最快的，說明KPN算法識別出的網(wǎng)絡(luò)關(guān)鍵節(jié)點能在網(wǎng)絡(luò)中更快速地傳遞信息，影響力最大。而在Email和PGP網(wǎng)絡(luò)中，傳播初期，KPN算法的效果略差于IKS算法，是因為網(wǎng)絡(luò)較為稀疏，信息不容易擴散；但在當(dāng)傳播進(jìn)行一段時間后，感染節(jié)點數(shù)目加速上升，KPN算法得分前十的初始感染節(jié)點率先感染了網(wǎng)絡(luò)中的所有節(jié)點。整體來看，KPN算法更能準(zhǔn)確地識別網(wǎng)絡(luò)中最具影響力的節(jié)點。

3.3.2 單調(diào)性分析

為了比較不同節(jié)點重要性排序算法對節(jié)點重要性的區(qū)分能力，采用單調(diào)性指標(biāo)M（R）來量化這一能力。不同評估方法在八個真實網(wǎng)絡(luò)數(shù)據(jù)集中得出的節(jié)點重要性排序的單調(diào)性指標(biāo)如表5所示。

KPN算法在八個數(shù)據(jù)集中都有優(yōu)異表現(xiàn)，在Jazz、USAir、Email、Hamsterster、PowerGrid、Hepth、PGP七個數(shù)據(jù)集中的排序結(jié)果的單調(diào)性指標(biāo)高于其他方法，而且數(shù)值接近為1。在Enron數(shù)據(jù)集中排序結(jié)果的單調(diào)性指標(biāo)僅次于最高值。因此，KPN算法相較其他五種方法能夠更好地區(qū)分節(jié)點的重要性。

4 KPN方法的最優(yōu)α值分析

不同網(wǎng)絡(luò)中節(jié)點的一、二階鄰居對節(jié)點重要性的貢獻(xiàn)程度可能不同， 因此KPN方法的最優(yōu)參數(shù)α值會隨網(wǎng)絡(luò)結(jié)構(gòu)的變化而變化。為了分析參數(shù)α對KPN方法性能的影響，計算不同α值對應(yīng)的KPN方法生成的節(jié)點重要性排序序列與不同傳播率下SIR生成的節(jié)點影響力序列的肯德爾系數(shù)的平均值為

〈τα〉=1n∑βmaxβminτ（KPNα，SIRβ）（5）

其中：β表示傳播率；βmin和βmax表示傳播率的最大和最小取值；n表示傳播率取值的個數(shù)；KPNα表示參數(shù)α取值時KPN方法生成的節(jié)點重要性序列；SIRβ表示傳播率為β時SIR生成的節(jié)點真實影響力序列。由于式（2）中α≥β且α + β =1，所以α取值為0.5～1，間隔為0.02，此外，將傳播區(qū)間設(shè)置為［βth-7%，βth+7%］。實驗結(jié)果如圖4所示，Jazz、USAir、Email、PowerGrid、Hepth、PGP和Enron數(shù)據(jù)集對應(yīng)的最佳α值分別為1.0、1.0、0.76、0.82、0.70、0.74、0.72、0.70。由此可見，對于聚類系數(shù)較高的網(wǎng)絡(luò)，如Jazz、USAir和Hepth等，可適當(dāng)調(diào)高α值，從而保證KPN方法可以獲得最佳性能。對于一般的網(wǎng)絡(luò)，KPN方法的最佳α值在0.7～0.8。

5 結(jié)束語

本文提出一種KPN方法，能有效評估節(jié)點的重要性并對其排序。KPN方法綜合了節(jié)點的全局位置信息和鄰域傳播力，既通過K-shell分解時節(jié)點移除的順序細(xì)化全局位置信息，改進(jìn)了K-shell方法區(qū)分粗粒度的缺點，又利用節(jié)點的鄰域結(jié)構(gòu)充分反映節(jié)點的局部傳播能力。最后，在八個真實網(wǎng)絡(luò)數(shù)據(jù)集上實驗驗證的結(jié)果表明，與其他節(jié)點重要性評估方法相比，KPN方法能夠更加有效地區(qū)分節(jié)點的重要性，并能準(zhǔn)確評估節(jié)點的重要程度。本文方法雖然改進(jìn)了K-shell分解法并取得了較好的表現(xiàn)，但仍可從以下方面繼續(xù)優(yōu)化改進(jìn)。例如，網(wǎng)絡(luò)中所有的邊的重要程度都被視為相等的。實際上，不同的邊對網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響不同，甚至與同一個節(jié)點相連的不同邊對節(jié)點重要程度的影響也不同。探究連邊對節(jié)點重要性刻畫的作用，尋求有效的邊加權(quán)方法將是后續(xù)研究工作的重點。

參考文獻(xiàn)：

［1］任曉龍， 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點排序綜述［J］. 科學(xué)通報， 2014，59（13）：1175-1196. （Ren Xiaolong，Lyu Linyuan. Review of ran-king nodes in complex networks［J］.Chinese Science Bulletin，2014，59（13）：1175-1197.）

［2］Bonacich P. Factoring and weighting approaches to status scores and clique identification［J］. Journal of Mathematical Sociology，1972，2： 113-120.

［3］Chen Duanbing，Lu Linyuan，Shang Mingsheng，et al. Identifying influential nodes in complex networks［J］. Physica A： Statistical Mechanics and Its Applications，2012，391（4）： 1777-1787.

［4］Lu Linyuan，Zhou Tao，Zhang Qianming，et al. The H-index of a network node and its relation to degree and coreness［J］. Nature Communications，2016，7： 10168.

［5］Freeman L C. A set of measures of centrality based on betweenness［J］. Sociometry，1977，40（1）： 35-41.

［6］Freeman L C. Centrality in social networks conceptual clarification［J］. Social Networks，1979，1： 215-239.

［7］Katz L. A new status index derived from sociometric analysis［J］. Psychometrika，1953，18： 39-43.

［8］Gu Ke，F(xiàn)an Ying，Di Zengru. Signed PageRank on online rating systems［J］. Journal of Systems Science amp; Complexity，2022，35（1）： 58-80.

［9］Yang Wanxia，Rehman S，Que Wenhui. Identifying event-specific opinion leaders by local weighted LeaderRank［J］. Intelligent Automation and Soft Computing，2021，26（6）： 1561-1574.

［10］Kitsak M，Gallos L K，Havlin S，et al. Identification of influential spreaders in complex networks［J］. Nature Physics，2010，6（11）： 888-893.

［11］Zeng An，Zhang Chengjun. Ranking spreaders by decomposing complex networks［J］. Physics Letters A，2013，377（14）： 1031-1035.

［12］Wang Zhixiao，Zhao Ya，Xi Jingke，et al. Fast ranking influential nodes in complex networks using K-shell iteration［J］. Physica A： Statistical Mechanics and Its Applications，2016，416： 171-181.

［13］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.

［14］Wang Min，Li Wanchun，Guo Yuning，et al. Identifying influential spreaders in complex networks based on improved K-shell method［J］. Physica A： Statistical Mechanics and Its Applications， 2020，554： 124229.

［15］李懂，席景科，孫成成. 融合度和K核迭代次數(shù)的節(jié)點重要性排序算法［J］. 計算機工程與設(shè)計，2019，40（6）： 1518-1522. （Li Dong，Xi Jingke，Sun Chengcheng. Node importance ranking algorithm with fusing degree and K-shell iteration number［J］. Computer Engineering and Design，2019，40（6）： 1518-1522.）

［16］Yang Xuan，Xiao Fuyuan. An improved gravity model to identify influential nodes in complex networks based on K-shell method［J］. Knowledge Based Systems，2021，227： 107198.

［17］Giridhar M. Influential spreaders identification in complex networks with potential edge weight based K-shell degree neighborhood method［J］. Journal of Computational Science，2020，39： 101055.

［18］游倩婧，鄭巍，劉方利. 基于重疊盒覆蓋算法的節(jié)點重要度評估［J］. 計算機應(yīng)用研究，2021，38（11）： 3354-3358. （You Qianjing，Zheng Wei，Liu Fangli. Node importance evaluation based on overlapping box covering algorithm［J］. Application Research of Compu-ters，2021，38（11）： 3354-3358.）

［19］Duan Moran，Chang Lili，Jin Zhen. Turing patterns of an SI epidemic model with cross-diffusion on complex networks［J］. Physica A： Statistical Mechanics and Its Applications，2019，533： 122023.

［20］Li Xiang，Liu Yangyang，Zhao Chengli，et al. Locating multiple sources of contagion in complex networks under the SIR model［J］. Applied Sciences，2019，9（20）： 4472.

［21］Wang Xinhe，Wang Zhen，Shen Hao. Dynamical analysis of a discrete-time SIS epidemic model on complex networks［J］. Applied Mathematics Letters，2019，94： 292-299.

［22］Christakis N A，F(xiàn)owler J H. Social contagion theory： examining dynamic social networks and human behavior［J］. Statistics in Medicine，2013，32（4）： 556-577.

［23］Gleiser P，Danon L. Jazz musicians network［J］. Advances in Complex System，2003，6： 565-573.

［24］Colizza V，Pastor-Satorras R，Vespignani A. Reaction diffusion processes and metapopulation models in heterogeneous networks［J］. Nature Physics，2007，3： 276-282.

［25］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： 065103.

［26］Watts D J，Strogatz S H. Collective dynamics of “small-world” networks［J］. Nature，1998，393： 440-442.

［27］Newman M E J. The structure of scientific collaboration networks［J］.Proceedings of the National Academy of Sciences， 2001，98（2）：404-409.

［28］Bogu M，Pastor-Satorras R，Daz-Guilera A，et al. Models of social networks based on social distance attachment［J］. Physical Review E， 2004，70： 056122.

［29］Mahoney M，Dasgupta A，Leskovec J，et al. Community structure in large networks： natural cluster sizes and the absence of large well-defined clusters［J］. Internet Mathematics，2009，6（1）： 29-123.

［30］Kamnitui N，Genest C，Jaworski P，et al. On the size of the class of bivariate extreme-value copulas with a fixed value of Spearman’s RHO or Kendall’s tau［J］. Journal of Mathematical Analysis and Applications，2019，472（1）： 920-936.

收稿日期：2022-08-06；修回日期：2022-10-10 基金項目：國家自然科學(xué)基金資助項目（61902116）；湖北省科技計劃資助項目（2021BLB171）；湖北工業(yè)大學(xué)綠色工業(yè)科技引領(lǐng)計劃資助項目（CPYF2017008）

作者簡介：熊才權(quán)（1966-），男，湖北鄂州人，教授，博士，主要研究方向為辯論模型和復(fù)雜網(wǎng)絡(luò)；古小惠（1998-），女（通信作者），湖北紅安人，碩士研究生，主要研究方向為復(fù)雜網(wǎng)絡(luò)節(jié)點重要性（1227815677@qq.com）；吳歆韻（1987-），男，江蘇丹陽人，副教授，博士，主要研究方向為圖與組合優(yōu)化算法．