考慮二階鄰居信息的K-shell重要節點識別算法研究

2025-02-26 00:00:00姚曦煜謝玉峰

現代信息科技 2025年1期

摘" 要：在真實網絡中，找出一些關鍵的節點進行保護能夠有效維持系統的穩定，同時對于復雜網絡中的病毒控制與傳播、交通網絡的故障控制、社交網絡中影響力識別等都有重要作用。在現有關鍵節點識別算法K-shell的基礎上，提出了一種考慮二階鄰居信息的K-shell的關鍵節點識別算法，該算法綜合考慮節點的全局與局部信息，同時引入節點的一階鄰居節點和二階鄰居節點的相關信息，計算節點在網絡中的重要性。為了驗證該算法的性能，以隨機攻擊和蓄意攻擊兩種攻擊方式在網絡中的節點進行仿真實驗，實驗結果表明，考慮二階鄰居信息的K-shell方法能夠有效地檢測節點的重要性，識別網絡中的關鍵節點。

關鍵詞：復雜網絡；節點識別；K-shell算法；二階鄰居

中圖分類號：N945.12；N945.13 文獻標識碼：A 文章編號：2096-4706（2025）01-0040-05

Research on the K-shell Important Node Identification Algorithm Considering Second-order Neighbor Information

Abstract： In real networks， identifying some key nodes for protection can effectively maintain the stability of the system. Meanwhile， it also plays important roles in virus control and propagation in complex networks， fault control in transportation networks and influence identification in social networks. Based on the existing key node identification algorithm of K-shell， a key node identification algorithm of K-shell considering the second-order neighbor information is proposed. This algorithm comprehensively considers the global and local information of nodes， and simultaneously introduces the relevant information of first-order neighbor nodes and second-order neighbor nodes of nodes to calculate the importance of nodes in the networks. In order to verify the performance of this algorithm， simulation experiments are carried out on nodes in the networks of the two kinds of attacks of random attacks and deliberate attacks. The experimental results show that the K-shell method considering second-order neighbor information can effectively detect the importance of nodes and identify the key nodes in the networks.

Keywords： complex network; node identification; K-shell algorithm; second-order neighbor

0" 引" 言

隨著信息技術的快速發展，復雜網絡已經成為理解和分析現實世界系統的關鍵工具。從社交網絡到生物網絡，再到技術基礎設施，這些網絡由相互連接的節點構成，節點間的交互模式揭示了系統的結構和功能特性[1-2]。在這些網絡中，某些節點因其在網絡中的獨特位置或屬性而顯得尤為重要，這些節點通常被稱為關鍵節點。無論是生物網絡、社會網絡還是信息網絡，都由節點和邊構成，其中節點代表實體，邊則代表實體之間的聯系。在這些網絡中，識別重要節點是至關重要的，因為它們往往對網絡的整體結構和動態行為產生顯著影響。關鍵節點在傳播過程中的作用尤其顯著，例如在信息傳播、疾病擴散以及網絡魯棒性方面[3-6]。重要節點識別不僅有助于理解網絡的內在組織原則，而且在實踐中具有廣泛的應用價值。例如，在社會網絡中，識別意見領袖或關鍵傳播者對于營銷策略的制定至關重要[7]；在生物網絡中，關鍵節點的識別對于理解疾病傳播機制和藥物靶點的發現有重要意義[8]；在互聯網和通信網絡中，識別關鍵節點有助于優化網絡流量管理和網絡安全[9]；在復雜系統中，識別重要環節進行保護能有效地維持系統的穩定性。因此，識別網絡中的關鍵節點已成為復雜網絡研究中的一個重要課題。

近年來，隨著復雜網絡成為研究熱點，研究人員開發出了多種方法來識別復雜網絡中的關鍵節點。這些方法不僅包括傳統的基于中心性的度量，如度中心性[10]、介數中心性[11]和接近中心性[12]等，還包括更先進的基于社區結構的方法和基于網絡動力學的分析[13-14]、關注于動態網絡環境下的關鍵節點識別問題，這在不斷變化的網絡結構中尤為重要[15]。

盡管已經取得了許多進展，但識別復雜網絡中的關鍵節點仍然是一個具有挑戰性的任務。但它們往往忽略了網絡的多層次結構和節點的局部環境特征。近年來，研究者提出了各種先進的方法，如K-shell分解、社區檢測和擴散模型，以更全面地評估節點的重要性。這是因為現實世界中的網絡往往表現出高度的異質性和復雜性，單一的度量標準可能無法準確捕捉到所有重要的節點特征。此外，隨著網絡規模的增長，計算效率也成為一個不容忽視的問題。為了克服這些挑戰，本研究旨在提出一種新的方法來有效地識別復雜網絡中的關鍵節點，對于復雜網絡重要節點識別有一定的指導意義。

1" 理論基礎

1.1" K-shell方法

K-shell算法主要利用節點的度值和所處的位置信息，根據網絡中節點的度值和所處位置信息比如：在整個網絡的核心部分還是邊緣部分，分配不同的K-shell值來評價該節點在整個網絡中的重要性，K-shell算法步驟如下：首先，找到網絡中節點度值為1的節點進行移除，然后在余下整個網絡中度為1的節點進行移除直至不再存在度值為1的節點，將這個過程當中移除節點分配K-shell值為1。以此類推，可以得到不同K-shell值的節點，根據不同的K-shell值劃分為不同的層次，具體示意圖如圖1所示[16]。

在圖1中，先找到度值為1的節點，分別有節點9，10，12，13，14和15，移除這些節點后，發現節點11的度值也為1，可以看出，最后被分配度值為1的節點有9，10，11，12，13，14和15。同理分配度值為2的節點有5，6，7和8。分配度值為3的節點有1，2，3和4。分配K-shell越大的節點被認為是越重要的節點，也就越處于網絡的核心地帶。K-shell方法的提出對于復雜網絡重要節點識別有著不容忽視的推進作用，對復雜系統的保護有著一定的指導意義。

1.2" 二階鄰居

在復雜網絡中，二階鄰居是指與一個節點直接相連的節點鄰居的鄰居。對于網絡中的節點i，其一階鄰居的集合N（i）包含所有直接與i相連的節點，對于任意節點j ∈ N（i），j的一階鄰居節點集合包含所有直接與j相連的節點，除去i之外，N（ j）中所有的節點都是i的二階鄰居。在圖1中，節點3的一階為節點1，2和4，二階鄰居為節點5，6，7，8和9。再例如在圖2中，節點5的一階鄰居為節點4和節點7，二階鄰居為節點2，6，8和9。節點的鄰居信息在節點重要性識別上也是不容忽視的，特別是一階鄰居和二階鄰居，從信息傳播的角度來講，節點一階鄰居和二階鄰居是和節點交流最密切的。在圖神經網絡（Graph Neural Networks， GNNs）和其他基于圖的數據結構的應用中，選擇只考慮二階鄰居（即每個節點的鄰居的鄰居）而不考慮更高階的鄰居（例如三階鄰居）。考慮更高階的鄰居會導致計算量顯著增加。隨著鄰居階數的增加，每個節點的鄰居數量會迅速增長，這可能導致計算資源需求的急劇上升。同時，當考慮到更高階的鄰居時，原始節點的信息會被更多的鄰居信息“稀釋”。這意味著節點本身的信息可能會變得不那么重要，而來自更遠節點的信息可能對預測沒有太大的幫助。許多應用上的任務主要依賴于節點及其直接鄰居的信息。因此，二階鄰居通常已經足夠捕捉到重要的局部結構特征。在實踐中，人們發現使用二階鄰居通常就能取得很好的性能，而不需要進一步考慮更高階的信息。總的來說，只考慮二階鄰居是一種比較合理的方案。不過，這并不是一個絕對的方案，在現實生活中，少數情況下確實需要考慮更高階的鄰居信息，特別是在那些長距離依賴關系非常重要的場景中。

2" 研究方法

K-shell方法是復雜網絡領域中重要節點識別問題上有著重要的作用，該方法是從全局的角度去考量節點的重要性，通過網絡中節點所處的位置和節點的度值去識別節點的重要性。但是在現實中的真實網絡，必須要考慮網絡的局部問題，將全局問題和局部問題綜合考量會更加全面。在局部問題中，以往的研究中也考慮節點的鄰居節點，但都為了研究的便利性，只考慮節點的一階鄰居，二階鄰居的信息也應該作為節點的重要性判斷依據。考慮二階鄰居信息的K-shell方法可以提升節點重要性的識別能力。

如圖2所示，按照K-shell方法給節點1和12分配的K-shell值都是1，但是節點12離核心位置更近，在網絡中扮演更重要的角色，換句話說，節點12的鄰居節點的比節點1的鄰居節點更重要。但是按照K-shell方法不能很好地區分，不能有效識別部分節點的重要性。

為了更好地描述節點的重要性，在K-shell方法的基礎之上引入節點的一階鄰居和二階鄰居的K-shell值作為新的指標衡量網絡中節點的重要性。在現實社交網絡中，一個節點的重要性不僅僅由自身的影響力覺得，與之相連的其他節點的影響力也在某種程度上決定著該節點的影響力。本文用unite_K-shell表示聯合二階鄰居信息的識別方法，具體的計算公式為：

其中ks表示節點的K-shell值，N（i） = {j|（i，j） ∈ E}表示節點i的一階鄰居節點，N 2（i）" = Uk ∈ N（i）{N（k）＼{i}}且i ≠ j ≠ k。該表達式考量了K-shell值以及節點一階鄰居和二階鄰居的信息，從全局和局部的角度衡量節點的重要性，得出的uks越高，意味著節點越重要。

另外，為了驗證方法的可靠性，通過移除網絡中p比例的節點模擬現實生活中的網絡攻擊，通過攻擊后網絡發生級聯效應最后存活的極大連通子圖的比例作為網絡魯棒性的一個指標。具體的指標計算公式如下：

其中ni表示網絡未收到攻擊前的節點總數，ns表示網絡達到穩定后的節點總數。ni～ns表示在攻擊過程中失效的節點數，那么S表示攻擊過程中失效的節點比例。該指標在很多研究當中都得到了應用，能很好地說明網絡在受到攻擊之后的魯棒性。

3" 實驗分析與結果

本文復雜網絡基本的三種網絡模型上進行仿真，分別是ER隨機網絡、BA無標度網絡以及WS小世界網絡。另外在兩種不同類型的真實網絡進行實驗和仿真，分別是美國航空網絡（USAir）和美國電網（USPowGrid），其中真實網絡由網絡數據庫（https：//networkrepository.com/index.php）提供。每次實驗的初始節點數為104，仿真結果都是10次運行結果的平均值。每次仿真都在三種攻擊方式下進行，分別是隨機攻擊、K-shell值蓄意攻擊以及本文的uks值蓄意攻擊，隨機攻擊是隨機選取網絡中的p比例的節點進行移除，然后計算網絡中達到穩態后的極大連通子圖的比例；K-shell值蓄意攻擊是先計算每個節點的K-shell值，然后按照由大到小進行排序，按照從大到小依次移除p比例的節點，最后計算網絡中達到穩態后的極大連通子圖的比例；uks值蓄意攻擊是先計算每個節點的K-shell值，然后計算節點的一階鄰居和二階鄰居的K-shell值，接著計算每個節點的uks值，然后按照由大到小進行排序，按照從大到小依次移除p比例的節點，最后計算網絡中達到穩態后的極大連通子圖的比例；具體的uks算法過程為：

如圖3、圖4和圖5所示，其分別代表在BA無標度網絡、WS小世界網絡以及ER隨機網絡的仿真結果。圓圈代表隨機攻擊方式；正方形代表K-shell值蓄意攻擊；三角形代表uks值蓄意攻擊。無論是ER隨機網絡、BA無標度網絡還是WS小世界網絡，伴隨著移除節點比例p的不斷變化，網絡的魯棒性指標S指標在本文提出的方法下降的是最快的，表示網絡蓄意攻擊受到的破壞最嚴重，無論是何種類型的網絡，取同一移除比例p，最終網絡中存活下來的節點的比例在本文提出的方法下是最少的，從另一個角度表明該方法能更好的進行重要節點識別。在圖5中，由于是ER隨機規則網絡，只有移除一定比例之后網絡才會發生明顯變化，所以近似在p = 0.9之前隨著移除比例的增加，S的變化幾乎是線性的。但在之后的移除比例當中，仍然是本文提出的方法存活下來的節點數是最少的，表明本文提出的方法更能有效識別網絡中節點的重要性。

為了驗證方法的一般性和有效性，如圖6和圖7所示，分別代表在美國航空網絡（USAir）和美國電網（USPowGrid）網絡的仿真結果。仍然是圓圈代表隨機攻擊方式；正方形代表K-shell值蓄意攻擊；三角形代表uks值蓄意攻擊。同樣無論是美國航空網絡（USAir）和美國電網（USPowGrid）網絡，伴隨著移除節點比例p的不斷變化，網絡的魯棒性指標S指標在本文提出的方法下降的是最快的，表示網絡蓄意攻擊受到的破壞最嚴重，從真實網絡的角度表明該方法能更好地進行重要節點識別。

4" 結" 論

識別網絡中節點的重要性一直是復雜網絡研究的核心議題之一。節點的重要程度不僅決定了網絡的結構穩定性，還影響著網絡中信息傳播的效率和范圍。傳統的節點重要性識別方法大多依賴于節點的局部屬性，這些方法往往忽略了節點在更廣泛網絡結構中的角色和影響力。本文在此基礎上，提出了一種改進的節點重要性識別方法——uks方法，該方法綜合考慮節點的一階鄰居節點和二階鄰居節點的K-shell值。這種方法不僅保留了K-shell方法的優點，即從全局視角評估節點的重要性，而且還引入了節點局部結構的信息，從而更加全面地反映節點在網絡中的位置和作用。具體而言，uks方法不僅考慮了節點自身的K-shell值，還考慮了該節點的直接鄰居（一階鄰居）以及鄰居的鄰居（二階鄰居）的K-shell值。通過這種方式，不僅能夠捕捉到節點的局部連接特性，還能了解節點在更廣泛的網絡結構中的位置和影響力。

通過一系列仿真實驗，本文驗證了uks方法的有效性。無論是在經典復雜網絡模型（如無標度網絡、規則格子網絡等）還是在真實世界網絡中，uks方法都能夠有效地識別出網絡中的關鍵節點。實驗結果顯示，相比于傳統的方法，uks方法在識別和保護重要節點方面表現更佳，能夠更準確地識別出對網絡結構穩定性和信息傳播能力至關重要的節點。這對于復雜系統的管理和維護具有重要的實踐價值，例如在網絡攻擊防御、疾病傳播控制以及信息傳播優化等方面都有著潛在的應用前景。總之，uks方法通過綜合考慮節點的全局和局部信息，為復雜網絡中節點重要性的識別提供了一種新的思路。這種方法不僅提高了識別精度，而且在實際應用中也表現出了良好的效果，對于復雜系統的重要節點保護和管理具有重要的指導意義。

當然，盡管本文提出的方法在某些方面展現了較好的性能，但仍有一些局限性和不足之處需要進一步改進和完善。以下是對本文不足之處的詳細闡述以及對未來研究方向的展望。在進行仿真實驗時，出于實驗的便利性和設備計算能力的限制，我們只考慮了節點數量級在104級別的網絡。然而，在現實世界中，許多網絡（如社交網絡、互聯網等）的規模要大得多，節點數量往往達到百萬甚至億級別。這種規模的網絡對計算資源的要求非常高，而本文的方法尚未在如此大規模的網絡上進行驗證。另外，本文僅在兩個真實網絡上進行了仿真測試，雖然這些網絡具有代表性，但仍然不足以充分證明方法在更廣泛的真實網絡中的有效性。為了更全面地評估方法的適用性和魯棒性，有必要在更多的真實網絡數據集上進行實驗。未來，除了簡單無向圖之外，未來的研究還可以考慮更復雜的網絡結構，如加權圖、有向圖、多層網絡等。這些網絡結構在許多實際應用中更為常見，因此對它們進行研究是非常有意義的。同時，許多真實世界網絡是動態變化的，節點和邊的數量隨時間而變化。未來的研究可以考慮如何將uks方法擴展到動態網絡環境下，以實時地識別關鍵節點并跟蹤其重要性的變化。

參考文獻：

[1] 何靜.基于改進物理模型的復雜網絡關鍵節點識別技術研究 [D].濟南：齊魯工業大學，2024.

[2] 王天宇.切換網絡可控性的魯棒性和優化研究 [D].濟南：齊魯工業大學，2024.

[3] 王光，張瑩.基于網絡演化博弈的信息傳播行為分析 [J].軟件導刊，2024，23（7）：126-132.

[4] 于躍，霍良安.多層網絡中的信息-行為-資源-疾病耦合傳播模型研究 [J].系統工程理論與實踐，2024，44（10）：3386-3399.

[5] 武兵杰，霍良安.疾病傳播過程中的層間耦合影響問題研究 [J].上海理工大學學報，2024，46（4）：452-463.

[6] 盛華芳.新冠疫情后大型體育賽事重啟評估建模研究 [J].計算機工程與應用，2020，56（17）：33-40.

[7] 張科，李昊驊，方立兵，等.網絡論壇意見領袖的情緒傳播：基于同群公司股價變化的證據 [J].系統管理學報，2024，33（6）：1570-1583.

[8] 涂貴宇，潘文林，張天軍.基于超網絡的新冠肺炎輿情關鍵節點識別研究 [J].計算機與數字工程，2023，51（1）：219-225.

[9] 劉勇.一種計算機網絡關鍵節點識別方法 [J].電子設計工程，2021，29（17）：99-103+108.

[10] 王昕楠，任艷麗，宋智，等.基于度中心性的AFDX網絡拓撲優化 [J].計算機仿真，2024，41（4）：363-367+372.

[11] 王嘯，李晗.基于介度中心性熵的復雜網絡關鍵節點識別算法 [J].計算機與數字工程，2024，52（3）：677-680+687.