一種基于局部傳播路徑的復雜網絡關鍵節點識別方法

何欣怡 馬茜 楊丹丹 張茂郁

一種基于局部傳播路徑的復雜網絡關鍵節點識別方法

何欣怡，馬茜，楊丹丹，張茂郁

（天津商業大學，天津? 300134）

摘? 要：復雜網絡中的關鍵節點識別是研究復雜網絡結構、功能、性質的重要基礎，在市場營銷、謠言控制、交通規劃等不同領域都有很強的應用價值。節點的關鍵性等價于節點的影響力，因此，關鍵節點識別問題可看作節點影響力評估問題。文章提出了一種基于局部傳播路徑的復雜網絡關鍵節點識別方法，該方法僅需計算目標節點兩步之內的拓撲結構，還綜合考慮了傳播概率對節點影響力評估的影響。與常見的度中心性、介數中心性、接近中心性、Kshell中心性相比，該算法識別結果更準確，在不同傳播概率下表現更穩定。

關鍵詞：復雜網絡；關鍵節點識別；影響力；傳播路徑

中圖分類號：TP399；O157.5? 文獻標識碼：A? ? 文章編號：2096-4706（2023）02-0008-04

A Method for Identifying Key Nodes in Complex Networks Based on Local Propagation Paths

HE Xinyi， MA Qian， YANG Dandan， ZHANG Maoyu

（Tianjin University of Commerce， Tianjin? 300134， China）

Abstract： The identification of key nodes in complex networks is an important basis for studying the structure， function and nature of complex networks. It has strong application value in marketing， rumor control， traffic planning and other fields. The criticality of nodes is equivalent to the influence of nodes. Therefore， the problem of identifying key nodes can be regarded as the problem of evaluating the influence of nodes. This paper proposes a key node identification method for complex networks based on local propagation paths. This method only needs to calculate the topology structure of the target node in two steps， and it also comprehensively considers the effect of propagation probability on the evaluation of node influence. Compared with the common methods such as degree centrality， betweenness centrality， closeness centrality and kshell centrality， this method is more accurate and stable under different propagation probabilities.

Keywords： complex network; key node identification; influence; propagation path

0? 引? 言

關鍵節點識別是復雜網絡科學關注的熱點和前沿性問題，具有重要的理論意義和應用價值。計算機病毒在網絡中的擴散、某種言論觀點在社交網絡上的傳播、傳染病在人群中的蔓延、國家或城市之間的商品、資金、技術、人員、信息、車輛等的流動都可以看成是服從某種規律的網絡傳播行為。這其中，關鍵節點在觀點、信息、車輛、人群等的傳播或流動中扮演著重要的角色，往往起著推波助瀾或逆轉風向的關鍵作用，識別這些節點可以幫助促進傳播或抑制蔓延[1，2]。同時，網絡功能的正常運轉也極大依賴著這些重要節點。研究表明，復雜網絡中只要5%～10%的重要節點同時失效，整個網絡就會無法正常運轉[3]。識別這些關鍵節點并采取相應的保護措施，可以提高整個網絡的穩健性和安全性。例如，識別交通網絡中的重要樞紐，可以優化交通路線，方便乘客換乘，預防交通擁堵[4]。在電力網絡中對關鍵節點進行優化，可以優化調度，預防大規模停電[5]。關鍵節點識別的一般思路是根據某一指標對節點的影響力進行量化，并根據量化值對節點影響力進行排序，關鍵節點識別問題可看作是節點影響力度量問題。節點影響力主要是通過信息、行為等的傳播體現的。因此，節點的影響力可表示為節點的傳播能力，復雜網絡的關鍵節點識別問題可看作對節點的影響力或傳播能力的評估問題[6]。

本文提出一種基于局部傳播路徑的復雜網絡關鍵節點識別方法。本方法在獨立級聯模型的基礎上，首先遍歷搜索從目標節點出發2步之內能到達的所有節點，這些節點被稱為受影響節點，然后搜索從目標節點出發到達受影響節點的所有路徑。基于每條傳播路徑計算激活概率，并基于此計算目標節點對該受影響節點的所有2步之內的傳播路徑的激活概率之和。將目標節點對所有受影響節點的激活概率之和作為目標節點的影響力。本方法除了考慮目標節點的局部拓撲結構外，還綜合考慮了傳播概率對節點影響力評估的影響。通過在不同數據集上進行實驗可以發現，該方法可以在不同的傳播概率下更準確地識別關鍵節點。

1? 相關工作

關鍵節點識別的前提是對節點的影響力進行評估，節點的影響力評估是指采用一定的標準對節點影響力的大小進行衡量、排序的問題。目前，復雜網絡中的節點影響力評估方法大部分都是基于網絡拓撲結構進行的。該類方法多數較為簡單，實用性強，且網絡拓撲結構數據，尤其是局部網絡拓撲結構數據較易獲得，因此受到大量的關注。在這類方法中，節點的影響力可理解為該節點在網絡中與其他節點相連使其具有的重要性。因此，節點的影響力也常被稱作節點的中心性（Centrality）[7-9]。

目前，較為常見的中心性方法包括基于局部網絡結構的評價方法——度中心性（Degree Centrality）。此方法將目標節點的鄰居數量作為影響力評估指標，簡單直觀，時間復雜度低，但在多數情況下，該方法衡量節點影響力的結果不夠準確，因為其考慮的信息太過局限。基于全局網絡結構的評估方法考慮了節點在整個網絡結構中位置的重要性，包括介數中心性（Betweenness Centrality， BC）、接近中心性（Closeness Centrality， CC）等。介數中心性、接近中心性均假設節點影響力沿最短路徑向全網傳播。與基于局部網絡結構的評價方法相比，基于全局網絡結構的方法的評估結果更為準確。但因網絡結構一般較為復雜，規模龐大，該類方法的時間復雜度很高。而且現實中的很多復雜網絡的拓撲結構很難完整獲取，因此，該類方法有較大的局限性。Kitsak等人[10]認為節點在網絡中的位置決定了節點的影響力，越接近網絡核心其影響力越大，并據此提出了k殼中心性（Kshell Centrality， KS）評價方法。該方法時間復雜度較低，但賦予很多節點相同的評估值，導致它們的影響力難以區分。此外，基于特征向量的評價方法也是評估節點影響力的重要方法，代表性的算法為谷歌的PageRank算法。基于特征向量的評價方法雖然可取得較好的評價效果，但它們只適用于有向、連通的網絡，應用范圍有限，且也面臨著網絡結構難以完整獲取的問題。近年來，很多工作致力于研究不同指標的適用范圍，及在動態網絡中的影響力評估問題[11-14]。

2? 本文涉及的基礎知識

2.1? 網絡表示

一般用圖的形式來表示復雜網絡。一個具體的復雜網絡可抽象為圖G=（V， E），其中V表示網絡中的節點集合，節點的數目用n表示，E表示邊集合，邊的數目用m表示。為方便處理和計算，圖G可表示成鄰接矩陣A={auv}∈{0，1}n×n的形式。auv=1則表示節點u和節點v之間有邊直接相連，auv=0則表示無邊直接相連。

2.2? 獨立級聯模型

在關鍵節點識別的工作中一般會根據傳播模型對目標節點的影響力傳播過程進行模擬，即假設節點影響力的傳播遵從某種模型。本文以獨立級聯模型（Independent Cascade Model， ICM）進行相關工作并進行實驗。該模型是一種信息傳播模型，原理簡單，且使用廣泛。根據ICM模型，網絡中的節點只有兩種狀態——激活（active）和非激活（inactive）。某一時刻網絡中的每一個節點須處于這兩種狀態中的一種[15]。用戶收到某信息并會將該信息傳播給予它直接相連的鄰居節點，則稱該節點處于激活狀態；相反，用戶沒有收到該信息或者收到該信息但并不會傳播給予它相連的鄰居節點，則稱該節點處于未激活狀態。ICM在離散時間點t點的動態傳播過程如下：

（1）在t=0時，網絡中大部分節點處于非激活狀態，只有少量節點處于激活狀態，這些處于激活狀態的節點被稱為種子節點。種子節點一般為提前指定的。

（2）在t≥1的任何時刻，每一個在t-1時刻被激活的節點u都有且僅有一次機會去嘗試激活它處于非激活狀態的所有鄰居節點v，激活成功的概率為puv。

（3）當多個節點u1， u2， u3嘗試激活它們共同的處于未激活狀態的鄰居節點v時，它們嘗試激活的順序是隨機的，且嘗試激活的行為是互相獨立不受影響的。

（4）以上過程不斷重復，當網絡中不再有新的節點被激活時，本次傳播終止。此時，網絡中處于激活狀態的節點的數量就是本次傳播中種子節點的影響力。

由于每次根據ICM模型進行模擬產生的傳播結果可能不同，因此在實際應用中通常要進行1 000次以上的大量模擬來降低不確定性。一般取多次模擬出的處于激活狀態的節點數目的平均值作為初始種子節點的最終影響力。在關鍵節點影響力識別問題中，通常依次把每一個節點作為種子節點，把根據ICM模型進行大量模擬得出的結果作為其真實影響力值。

2.3? 評價指標

關鍵節點識別問題等價于節點影響力評估問題。目前評價各種影響力評估方法好壞的主要思路是：按照某種評估方法計算網絡中每一個節點的影響力評估值，將所有節點按照評估值大小降序排列。同時依次將網絡中的每一個節點作為種子節點根據傳播模型進行多次模擬求平均，這個值被看作是節點的真實影響力值，將所有節點的真實影響力值降序排列。通過計算這兩個序列的一致性來評價該評估方法的優劣，這兩個序列越一致，則說明該方法越有效。Kendall's Tau（τ）系數常被用來衡量上述兩個排序列表的一致性，該系數的相關定義如下：

考慮兩個序列x和y。對任意一對觀測值（xi， yi）和（xj， yj），計算（xi-xj）（ yi-yj），如果大于0則稱這對觀測值是一致的，如果小于0則稱這對觀測值是不一致的；如果等于0則稱這對觀測值既不是一致的也不是不一致的。具體的計算公式為：

（1）

Nc和Nd分別表示一致的和不一致的觀測對數量。τ值越接近1，則兩個序列越一致，說明該評估方法準確性越高。

2.4? 常用評估方法

度中心性（Degree Centrality， DC）。指與該節點直接相連的鄰居節點的個數。度中心性屬于基于局部拓撲結構的方法，計算非常簡單，用來分析節點的直接影響力。

介數中心性（Betweenness Centrality， BC）。指網絡中通過該節點的最短路徑的數目與所有節點對之間最短路徑數目的比值，屬于全局影響力方法，計算復雜度較高。

接近中心性（Closeness Centraity， CC）。指的是目標節點到網絡中所有其他節點的最短距離和，屬于全局影響力方法，計算復雜度高，但評估效果較好。

中心性Kshell中心性（Kshell Centrality， KS）。具體計算方法如下：首先將網絡中所有DC=1的節點及與它們相連的邊去掉，這些節點的KS值為1，重復這個過程直到網絡中沒有度值為1的節點存在；然后采用同樣的方式去掉網絡中度值為2的節點及與它們相連的邊，這些節點的KS值為2。重復上述過程直到網絡中的所有節點均被移除，此時，網絡中的每個節點都有一個KS值。

3? 基于局部傳播路徑的關鍵節點識別方法

DC只統計目標節點的鄰居數目，考慮的拓撲結構過少導致其效果不好。而BC、CC評估效果有改善但需要在整個網絡上進行最短路徑的計算，盡管有很多優化算法，但在大規模網絡中計算復雜度依然很高，且完整的網絡結構難以獲取。KS方法計算復雜度介于DC和BC、CC之間，但對節點影響力的區分度不好，即很多節點的KS值相同。基于此，本文提出了一種基于局部拓撲結構和傳播路徑的節點影響力評估方法——局部傳播路徑法（Local Propagation Paths， LPP）。該方法將目標節點對兩步之內能到達的所有節點的所有兩步之內的傳播路徑的激活概率之和作為目標節點的影響力，因為僅考慮了兩步之內的節點，所以計算復雜度不高；又因為考慮的范圍比DC要大，且包含傳播概率等信息，評估會更加準確。該方法的具體計算方法如下：

對于網絡中的每一個節點v∈V，計算節點v對兩步之內能到達的所有節點w的影響力之和，計算方法如下：

（2）

其中，PATHvw={path1， path2， …， pathk， …， pathL}，PATHvw表示節點v到節點w所有路徑（共有L條）的集合，pathk表示節點v到節點w的第k條具體路徑：

（3）

其中， 指節點Vi和節點Vi+1之間的傳播概率。因為LPP只考慮了目標節點對兩步之內節點的影響力，所以1≤n≤2。

圖1展示了利用LPP評估方法識別關鍵節點的流程。對網絡中的每一個節點，根據式（2）、式（3）計算節點的LPP值。然后將所有節點按LPP值由大到小的順序排序，得到序列R。在序列R中，位置越靠前代表影響力越大，然后根據需要選擇前K個節點作為關鍵節點。

4? 實驗結果

為了評估LPP評估方法的表現，本文在四個真實復雜網絡上進行了實驗，分別為空手道俱樂部網絡Karate、爵士音樂家網絡Jazz、郵件往來網絡Email、MSN博客空間博主之間的交流關系網Blog。這四個數據集均為網絡公開數據集，網絡基本情況如表1所示，其中，n表示網絡節點數量，m表示網絡邊的數量（四個網絡均為無向網絡），k表示網絡節點平均度。實驗的硬件環境為：3.2 GHz的Intel（R）Core（TM）i5-3470 CPU，3.89 GB的內存。軟件環境為MATLAB R2013a。

網絡節點的真實影響力采用ICM模型模擬獲得，模型中的傳播概率p取0.01～0.1之間。對每一個傳播概率，依次將每個節點作為初始激活的種子節點進行模擬傳播，傳播終止時網絡中處于激活狀態的節點的數量作為該種子節點的影響力。為了結果準確，本文對每個節點模擬10 000次取平均值作為該節點的真實影響力。將節點按其模擬出的真實影響力由大到小的順序排列，得到真實影響力排序序列。本文將LPP的評估效果與DC、BC、CC、KS對比。對每一種方法，計算網絡中所有節點在該方法下的評估值，按評估值由高到低的順序排序得到該方法的排序序列。然后計算真實影響力序列與該方法的排序序列的一致性τ。實驗結果如圖2所示，橫軸代表傳播概率p，縱軸代表肯達爾系數τ。τ值越大，表明該方法準確性越高。

如圖2所示，在這四個數據集中，在絕大多數傳播概率下，LPP均能取得最大的τ值，說明LPP在大多數傳播概率下評估效果最好。在Jazz網絡中，當傳播概率較大時LPP表現稍遜于DC，但差距并不明顯。從圖2中還可以看出，DC、KS、BC等的評估效果隨傳播概率的變化而產生較大波動，例如在Email和Blog數據集中，DC、BC等的評估效果隨傳播概率增大而明顯變差。LPP也有波動但幅度較小，說明該方法較為健壯。總體看來，BC和KS效果最差，和它們為很多節點賦予相同的評估值導致這些節點的影響力無法區分有很大關系。

除了比較各評估方法的評估效果外，本文還比較了各方法的運行時間。因Karate和Jazz網絡規模小，運行時間差距不明顯，本文只比較了各方法在Email和Blog中的運行時間，結果如表2所示。基于網絡局部結構的評估方法DC、LPP的運行時間比BC、CC等基于全局網絡結構的方法的運行時間短。在網絡規模較大時DC、LPP的優勢將更明顯。

5? 結? 論

復雜網絡中的關鍵節點識別問題等價于節點影響力評估問題。本文分析了常見節點影響力評估方法DC、CC、KS等存在的問題，提出了一種基于局部傳播路徑的度量方法LPP。該方法結合了DC、CC的優點，基于局部拓撲結構進行計算使其能在大規模網絡上運行，考慮了兩步之內的節點的個數及它們之間的傳播概率，使得結果更加準確。在四個真實復雜網絡上的實驗證明LPP方法在準確性、健壯性、運行時間方面均有優勢。

在未來的工作中，本文將嘗試在評估方法中加入更多的現實信息，例如考慮網絡的異質性、社區結構等因素，使得節點影響力評估結果更加準確、貼近現實。

參考文獻：

[1] 王敏.復雜網絡中關鍵節點挖掘與社區發現算法研究 [D].成都：電子科技大學，2020.

[2] 王安.基于復雜網絡結構特征的節點重要性評估方法研究 [D].北京：中國人民公安大學，2020.

[3] 王晉，王伯禮.基于復雜網絡的城市群鐵路網絡節點重要度研究 [J].內蒙古公路與運輸，2021（4）：52-57.

[4] 汪軍，夏永躍，王運明，等.基于貪心介數的地鐵-公交復合網絡關鍵車站識別算法 [J].鐵道標準設計，2022，66（7）：132-137.

[5] 朱大銳，王睿，程文姬，等.基于改進PageRank算法的輸電網關鍵節點辨識方法研究 [J].電力系統保護與控制，2022，50（5）：86-93.

[6] 馬茜.社會網絡中的節點影響力度量和k-節點集的影響力最大化問題研究 [D].濟南：山東大學，2017.

[7] 修志博.城市交通復雜網絡節點重要度評估與級聯失效研究 [D].長春：吉林大學，2020.

[8] 羅浩，閆光輝，張萌，等.融合多元信息的多關系社交網絡節點重要性研究 [J].計算機研究與發展，2020，57（5）：954-970.

[9] 郭程遠，陳鴻昶，王庚潤，等.復雜網絡節點重要性排序算法及應用綜述 [J].信息工程大學學報，2021，22（3）：313-320+358.

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

[11] 周庚.復雜網絡節點中心性度量算法的研究及應用 [D].蘭州：蘭州理工大學，2020.

[12] 馬媛媛，韓華.基于有效距離的復雜網絡節點影響力度量方法 [J].復雜系統與復雜性科學，2022，19（1）：12-19.

[13] 蔣偉進，楊瑩，羅田甜，等.基于全局—局部屬性的復雜網絡節點綜合影響力評估算法 [J].物聯網學報，2022，6（3）：133-145.

[14] 楊書新，梁文，朱凱麗.基于三級鄰居的復雜網絡節點影響力度量方法 [J].電子與信息學報，2020，42（5）：1140-1148.

[15] 邵玉，陳崚，劉維.獨立級聯模型下基于最大似然的負影響力源定位方法 [J].計算機科學，2022，49（2）：204-215.

作者簡介：何欣怡（2001—），女，漢族，貴州六盤水人，本科在讀，研究方向：數據挖掘；通訊作者：馬茜（1989—），女，漢族，山東威海人，講師，博士，研究方向：復雜網絡。

收稿日期：2022-09-12

基金項目：天津市大學生創新創業訓練計劃項目（202210069069）；天津市教委科研計劃項目（2021SK141）