陳 娜

(山西工程科技職業(yè)大學 計算機工程學院，山西 晉中 030619)

0 引言

關鍵節(jié)點[1]在復雜網(wǎng)絡中處于重要地位，其行為對復雜網(wǎng)絡中的信息傳播具有極大的影響，分析并預測大規(guī)模復雜網(wǎng)絡的關鍵節(jié)點在輿情傳播、政策宣傳和商業(yè)營銷等領域均具有巨大的應用價值[2]。目前主流的關鍵節(jié)點挖掘方法根據(jù)技術差異可分為4類[3]：基于評分規(guī)則的方法、基于復雜網(wǎng)絡圖的方法、基于影響傳播模型的方法以及多維融合的方法。其中復雜網(wǎng)絡圖[4]包含了豐富的網(wǎng)絡結(jié)構信息，通過拓撲結(jié)構尋找關鍵用戶，具有準確、高效的優(yōu)點。度中心性[5]、接近中心性[5]、中介中心性[6]可從不同角度評估節(jié)點在網(wǎng)絡中的重要性，但這3種評價方法的可靠性均不足。PageRank算法[7]是一種迭代的節(jié)點關鍵性評估指標，該指標基于特征向量中心度(Eigenvector Centrality)提高了評估的可靠性，但其計算量大，難以適用于大規(guī)模復雜網(wǎng)絡。

研究者們嘗試通過圖計算理論[8]挖掘復雜網(wǎng)絡圖的隱含信息，以分析復雜網(wǎng)絡中節(jié)點與連接的關鍵性。然而，圖計算理論不具備自主學習的能力，因此可擴展性與可靠性均較弱。近年來，圖神經(jīng)網(wǎng)絡(Graph Neural Network，GNN)的出現(xiàn)促使人工智能步入“認知智能”時代[9]，現(xiàn)已被成功用于求解推薦系統(tǒng)[10]、數(shù)據(jù)聚類[11]以及圖像處理[12]等問題，并展現(xiàn)出極大的發(fā)展?jié)摿ΑＭǔ?，復雜網(wǎng)絡中節(jié)點的鄰居節(jié)點影響力越大，其自身影響力也越大，而GNN的核心思想是借助神經(jīng)網(wǎng)絡的權重參數(shù)將鄰居節(jié)點信息納入當前節(jié)點，因此GNN可自動考慮節(jié)點相關的復雜網(wǎng)絡拓撲信息。由現(xiàn)有的相關研究成果可知，雖然GNN能自主學習輸入圖模型的拓撲信息，且具有較強的可擴展能力，然而，GNN在大規(guī)模數(shù)據(jù)上的訓練難度較大，且無法自適應地處理動態(tài)變化的網(wǎng)絡問題。

諸多學者將強化學習(Reinforcement Learning，RL)技術[13]引入到深度神經(jīng)網(wǎng)絡的訓練階段，通過RL提高深度神經(jīng)網(wǎng)絡的自學習能力。目前利用RL成功訓練的神經(jīng)網(wǎng)絡模型主要有：循環(huán)神經(jīng)網(wǎng)絡[14]、遞歸神經(jīng)網(wǎng)絡[15]和徑向基函數(shù)神經(jīng)網(wǎng)絡[16]等，RL技術不僅能增強神經(jīng)網(wǎng)絡的自學習能力，而且提高了神經(jīng)網(wǎng)絡在不同任務上的應用效果。受上述研究成果啟發(fā)，本文利用RL技術訓練GNN，增強GNN的自學習能力，進而提高復雜網(wǎng)絡關鍵節(jié)點檢測算法的可擴展性與可靠性。

本文將復雜網(wǎng)絡建模為圖模型，采用雙重魯棒性指標作為節(jié)點的關鍵性評價標準，然后利用GNN的節(jié)點嵌入模塊學習復雜網(wǎng)絡節(jié)點的拓撲結(jié)構信息，利用回歸模塊推理節(jié)點的關鍵性評分。此外，提出了基于RL的GNN訓練方法，該方法通過獎勵函數(shù)學習GNN的超參數(shù)并輸出一個動作序列，該動作序列對應該復雜網(wǎng)絡關鍵節(jié)點識別的GNN模型。實驗結(jié)果表明，本算法使用GNN檢測的關鍵節(jié)點具有較高的準確性，且檢測速度較快。

1 網(wǎng)絡模型

假設G=(V,E)表示一個圖，V與E分別為圖的節(jié)點集與連接集，關鍵節(jié)點檢測問題可描述為搜索一個關鍵節(jié)點子集Vc，該子集對圖的魯棒性具有極大的影響。假設u為復雜網(wǎng)絡的一個節(jié)點，v=N(u)為u的鄰居節(jié)點集，那么u的關鍵性評分函數(shù)可表示為：

ru=f(hu,hv)，

(1)

式中，hu，hv分別為節(jié)點u與v的特征向量；ru為關鍵性評分。GNN在訓練過程學習復雜網(wǎng)絡的關鍵性評分關系f()，輸出預測的關鍵性評分關系f′()。

2 基于GNN的關鍵節(jié)點檢測模型

GNN在復雜網(wǎng)絡關鍵節(jié)點檢測問題上的模型包括3部分：① 選取圖魯棒性指標評價節(jié)點的關鍵性，節(jié)點的關鍵性越高成為關鍵節(jié)點的可能性則越大。② 使用GNN的嵌入模塊學習包含鄰居信息的節(jié)點關鍵性評分。③ 使用GNN的回歸模塊推斷未知節(jié)點的關鍵性評分。

2.1 節(jié)點關鍵性評估

系統(tǒng)魯棒性指標在圖理論中反映了某個節(jié)點缺失對圖產(chǎn)生的影響，為了提高本算法的兼容性與魯棒性，采用2個圖魯棒性指標評價節(jié)點的關鍵性：

① 有效圖抗。定義為圖中每對節(jié)點的有效阻抗總和。有效圖抗Rg的計算方法為：

(2)

式中，λi為圖G的拉普拉斯矩陣特征值；c為G包含的連接總數(shù)量。

② 加權譜。定義為圖中n-圓環(huán)的正則化總和。將n-圓環(huán)定義為一個節(jié)點序列u1,u2,…,un，其中ui與ui+1相鄰。加權譜Ws的計算方法為：

(3)

式中，n為圓環(huán)形狀，例如，n=3表示圖中的三角形數(shù)量，本文復雜網(wǎng)絡問題中將n設為4。

2.2 節(jié)點嵌入模塊

GNN第1個子模塊基于圖拓撲結(jié)構信息與節(jié)點關鍵性評分學習復雜網(wǎng)絡每個節(jié)點的嵌入向量。如果節(jié)點在復雜網(wǎng)絡中距離越近，那么節(jié)點在嵌入空間中距離也越近。GNN將復雜網(wǎng)絡節(jié)點映射到嵌入空間的流程如圖1所示。

圖1 GNN的節(jié)點嵌入模塊Fig.1 Node embedding module of GNN

節(jié)點嵌入模塊包含2個步驟：

步驟1：根據(jù)每個節(jié)點及其鄰居節(jié)點學習一個描述符。假設鄰居跳數(shù)為K，例如，K=2表示目標節(jié)點2跳距離以內(nèi)的節(jié)點為該節(jié)點的鄰居。節(jié)點u的鄰居節(jié)點可表示為：

N(u)={u:D(u,v)≤K,?u∈G}，

(4)

式中，函數(shù)D()計算2個節(jié)點之間的最小跳數(shù)；u為目標節(jié)點；v為圖中的其他節(jié)點。

步驟2：通過聚合函數(shù)為每個節(jié)點創(chuàng)建一個鄰居嵌入，并為每個鄰居嵌入分配一個權重。通過注意力模塊自動學習每個鄰居節(jié)點的權重，該步驟的數(shù)學模型可定義為：

(5)

圖G中全部節(jié)點的嵌入可定義為：

(6)

算法1描述了節(jié)點嵌入表示的處理流程。

算法1 節(jié)點嵌入表示算法輸入:圖G,輸入節(jié)點特征Xv,組合權重W,聚合權重Q。輸出:節(jié)點嵌入向量zv。1.h0v=Xv;∥初始化階段2.foreach l from 1 to L do3. foreach v from 1 to V do4. hlN(v)=Att(Qlhl-1k);5. hlv=ReLU(Wl[hl-1v‖hl-2v‖hlN(v)]); ∥ ‖.‖表示聚合運算6. endfor7.endfor8.return hlv;

2.3 回歸模塊

圖2 GNN的回歸模塊Fig.2 Regression module of GNN

(7)

2.4 節(jié)點關鍵性評分預測模塊

GNN預測復雜網(wǎng)絡中節(jié)點關鍵性示意如圖3所示。GNN模型預測輸入復雜網(wǎng)絡各節(jié)點的關鍵性評分，將復雜網(wǎng)絡的節(jié)點按關鍵性降序排列。

圖3 復雜網(wǎng)絡節(jié)點的關鍵性預測示意Fig.3 Cruciality prediction diagram of complex network nodes

3 GNN的訓練方法

在訓練階段需確定GNN的超參數(shù)，包括GNN的深度、每層的神經(jīng)元數(shù)量以及激活函數(shù)。GNN在復雜網(wǎng)絡上的訓練流程如圖4所示。

圖4 GNN在復雜網(wǎng)絡上的訓練流程Fig.4 GNN training process on complex networks

3.1 傳統(tǒng)GNN訓練方法

GNN的激活函數(shù)設為ReLU(Rectified Linear Units)函數(shù)，使用Adam優(yōu)化器[17]對節(jié)點的關鍵性排名損失進行優(yōu)化，Adam優(yōu)化器的參數(shù)設為TensorFlow-Keras框架[18]的缺省值，在TensorFlow框架中使用Stellargraph作為圖計算的庫。

算法2描述了傳統(tǒng)的GNN訓練流程。每次迭代將節(jié)點嵌入與鄰居嵌入作為輸入數(shù)據(jù)，運行GNN節(jié)點嵌入模塊計算每個節(jié)點的嵌入向量；然后，GNN回歸模塊基于上述嵌入向量計算節(jié)點的關鍵性評分。根據(jù)節(jié)點關鍵性評分估計值與實際值之間的差異來訓練GNN。重復運行上述程序，產(chǎn)生訓練的GNN模型。

算法2 GNN的傳統(tǒng)訓練方法輸入:復雜網(wǎng)絡圖G,最大迭代次數(shù)I,GNN的深度空間與每層的節(jié)點數(shù)量空間。輸出:GNN超參數(shù)1.計算G每個節(jié)點的實際關鍵性評分值;2.foreach i from 1 to I do3. 運行GNN節(jié)點嵌入模塊產(chǎn)生節(jié)點的嵌入表示;4. 運行GNN回歸模塊估計節(jié)點的關鍵性評分;5. 更新式(7)的權重;6. 更新GNN的深度;7.更新GNN每層的節(jié)點數(shù)量;8.endfor9.在復雜網(wǎng)絡測試集G'上運行GNN;10.輸出G'的top-N關鍵節(jié)點;

3.2 基于RL的GNN訓練方法

借助RL框架訓練GNN，訓練目標是最小化節(jié)點關鍵性評分估計值與實際值之間的差異。RL的狀態(tài)為GNN的預測性能，動作為GNN超參數(shù)，RL通過獎勵函數(shù)尋找預測最準確的GNN模型。

3.2.1 RL框架

RL框架主要由狀態(tài)S、動作A與獎勵R三個元素構成，其目標是Agent通過執(zhí)行不同的動作來最大化總獎勵。Agent在每個時間步重復執(zhí)行如下的步驟：若Agent在時間步t的狀態(tài)為S，此時Agent選擇執(zhí)行動作A，然后從當前環(huán)境獲得一個獎勵R。本文采用Q-learning作為RL框架，若當前Agent的最優(yōu)策略為π:S→A，那么環(huán)境獎勵可表示為：

q(st,at)=γRt+γ2Rt+…+γnRn，

(8)

式中，γ為折扣因子；t為當前時間步；s與a分別為Agent的狀態(tài)與動作。

Q-leaning在每個時間步結(jié)束更新Q-table的獎勵，更新的獎勵可定義為：

(9)

Q-learning使用GNN預測Q-table中的獎勵，即GNN作為Q-learning框架的Q-函數(shù)。給定一個輸入狀態(tài)S，GNN輸出所有“狀態(tài)-動作”的Q-值，原Q-learning在每個時間步結(jié)束更新Q-table。本文對Q-learning框架的Q-table機制進行修改，保存過去全部時間步的狀態(tài)、動作與獎勵值，記為Q-matrix，對Q-matrix隨機采樣產(chǎn)生一個子集，將該子集作為GNN的訓練集以減少訓練數(shù)據(jù)量。

3.2.2 RL獎勵函數(shù)

若排除節(jié)點v導致復雜網(wǎng)絡的魯棒性發(fā)生大幅降低，那么節(jié)點v的關鍵性評分應較高。對復雜網(wǎng)絡的有效圖抗與加權譜差分值做加權調(diào)和運算，其結(jié)果作為RL的獎勵。Q-learning的獎勵函數(shù)可定義為：

(10)

3.2.3 RL隨機采樣訓練

Q-matrix中保存了Q-learning所有時間步的狀態(tài)、動作與獎勵數(shù)據(jù)，假設Q-matrix共有M個Q-value，Q-learning訓練階段對Q-matrix隨機采樣K次，產(chǎn)生包含K個Q-value的訓練集?；跉W氏距離度量實際Q-value與期望Q-value之間的距離，由此可獲得每對數(shù)據(jù)的損失函數(shù)：

(11)

式中，rt表示在時間步t的第i個Q-value。

將每對訓練數(shù)據(jù)的損失累加，產(chǎn)生訓練集的總損失：

(12)

式中，i表示訓練集中Q-value的索引；M表示訓練集中Q-value的總數(shù)量。

4 實驗與結(jié)果分析

文中使用Gephi version 0.9.2軟件分析復雜網(wǎng)絡數(shù)據(jù)，使用Python 3.6實現(xiàn)文中相關算法，編程環(huán)境為Pycharm與Eclipse集成的開發(fā)平臺。PC機的配置為Intel Core i7-11700，主頻為2.5 GHz，內(nèi)存為16 GB，操作系統(tǒng)為Windows 10。

4.1 數(shù)據(jù)集

采用wiki vote數(shù)據(jù)集[19]作為實驗的真實數(shù)據(jù)集，共包含7 115個節(jié)點與103 689條連接。數(shù)據(jù)集包含了一個用戶對另一個用戶的投票信息來推選Wikipedia上的關鍵節(jié)點。網(wǎng)絡模塊度(Network Modularity)是由Newman提出的一種衡量復雜網(wǎng)絡中社區(qū)強度與穩(wěn)定性的常用評價方法，模塊度的范圍為[-1，1]。wiki vote數(shù)據(jù)集的模塊度為0.428，說明該復雜網(wǎng)絡包含密集的社區(qū)結(jié)構。網(wǎng)絡的平均集聚系數(shù)度量了復雜網(wǎng)絡中頂點之間結(jié)集成團的程度，具體而言，反映了復雜網(wǎng)絡中用戶與相鄰用戶之間的密切程度。wiki vote數(shù)據(jù)集的平均集聚系數(shù)為0.140 9，說明該復雜網(wǎng)絡中封閉三角形拓撲結(jié)構較少。綜合分析wiki vote數(shù)據(jù)集的模塊度與集聚系數(shù)可知，該復雜網(wǎng)絡的社區(qū)內(nèi)連接較密集，而社區(qū)之間的關系較稀疏，這也體現(xiàn)了當前主流大規(guī)模復雜網(wǎng)絡的拓撲結(jié)構特點。

4.2 評價指標

本文使用中介中心度(Betweenness Centrality，BC)、度中心度(Degree Centrality，DC)與接近中心度(Closeness Centrality，CC)評估每個用戶在復雜網(wǎng)絡中的聲望。此外，通過Page Rank(PR)指標評價節(jié)點在復雜網(wǎng)絡中的重要性，PR的計算方法可參考文獻[20]中的實現(xiàn)實例。

BC的計算公式為：

(13)

式中，c(i, j)(x)表示經(jīng)過節(jié)點x的路徑總數(shù)量；節(jié)點i與j表示路徑的兩端。

DC的計算公式為：

(14)

式中，d(x，y)表示節(jié)點x與y之間的最短路徑長度；n表示與x建立路徑的節(jié)點數(shù)量。

CC的計算公式為：

CC(x)=dig(x)，

(15)

式中，dig()函數(shù)為節(jié)點x的度。

節(jié)點i在復雜網(wǎng)絡中的聲望可定義為：

(16)

式中，BC(x)，CC(x)，DC(x)與C(x)分別表示節(jié)點x的中介中心度、接近中心度、度中心度與集聚系數(shù)；D為用戶x與社區(qū)中心位置的距離。聲望RP(x)越大，表示用戶x成為關鍵節(jié)點的可能性越大。

4.3 GNN訓練

從wiki vote數(shù)據(jù)集的7 115個節(jié)點中隨機選擇60%(即4 269個)作為訓練集，剩余的40%(即2 846個)作為測試集。首先采用第3部分中基于RL的方法訓練GNN，GNN的超參數(shù)范圍如表1所示。經(jīng)過訓練輸出的GNN超參數(shù)如下：① 節(jié)點嵌入模塊的深度為4，每層的神經(jīng)元數(shù)量為128，64，32，16；② 回歸模塊的深度為3，每層的神經(jīng)元數(shù)量為12，8，1。下文采用訓練的GNN網(wǎng)絡預測測試集的社交領袖。

表1 GNN訓練階段的參數(shù)范圍Tab.1 GNN parameters during training

4.4 對比算法

采用多個關鍵節(jié)點檢測算法來構建對比實驗，以全面評估各復雜網(wǎng)絡關鍵節(jié)點檢測算法的有效性。所考慮的對比算法包括：

FFA算法[21]：該算法是一種基于螢火蟲優(yōu)化算法(Firefly Algorithm)的復雜網(wǎng)絡關鍵節(jié)點檢測算法，先使用Louvain方法將復雜網(wǎng)絡劃分成社區(qū)，并在節(jié)點重要性評估標準中考慮了局部社區(qū)的拓撲信息，然后利用螢火蟲優(yōu)化算法搜索復雜網(wǎng)絡中重要性最高的節(jié)點。

PCP算法[22]：該算法是一種基于多階段分簇的復雜網(wǎng)絡關鍵節(jié)點檢測算法，通過先分簇后排名的關鍵節(jié)點檢測策略篩選候選關鍵節(jié)點子集，由此避免了對網(wǎng)絡全部節(jié)點的搜索。

OLMiner算法[23]：該算法是一種基于兩階段聚類的復雜網(wǎng)絡關鍵節(jié)點檢測算法，第一階段采用社區(qū)檢測技術解決社區(qū)間的影響力重疊問題，同時縮小候選子集的規(guī)模；第二階段進一步搜索準確的關鍵節(jié)點。

FTS算法[24]：該算法是一種基于模糊信任系統(tǒng)的復雜網(wǎng)絡關鍵節(jié)點檢測算法，先采用模糊系統(tǒng)建模網(wǎng)絡的社交關系，再利用模糊理論推斷網(wǎng)絡中最受信任的節(jié)點，從而獲得復雜網(wǎng)絡中的關鍵節(jié)點。

4.5 實驗結(jié)果與分析

4.5.1 復雜網(wǎng)絡關鍵節(jié)點檢測性能實驗

wiki vote數(shù)據(jù)集的復雜網(wǎng)絡共有28個社區(qū)，首先對復雜網(wǎng)絡全部測試集運行關鍵節(jié)點檢測算法，輸出排名最高的10個節(jié)點。表2統(tǒng)計了BC，DC，CC與PR對應的top10節(jié)點及其結(jié)果值。由表2可知，基于不同評價指標在同一數(shù)據(jù)集上產(chǎn)生的關鍵節(jié)點排名存在差異。為了分析各指標的綜合排名結(jié)果，將每個排名中出現(xiàn)次數(shù)最多的節(jié)點作為該排名的正定節(jié)點，最終產(chǎn)生的top10節(jié)點序號分別為{3 461，568，1 725，2 896，772，3 397，3 180，6 713，5 421，4 220/5 421/75}，其中排名第10的節(jié)點中4 220，5 421和75各出現(xiàn)一次。

表2 wiki vote數(shù)據(jù)集各評價標準的關鍵節(jié)點Tab.2 Crucial nodes detected with all evaluation criterions on wiki vote dataset

各關鍵節(jié)點檢測算法輸出的top10關鍵節(jié)點如表3所示。

表3 各算法檢測的關鍵節(jié)點Tab.3 Crucial nodes detected by all algorithms

由表3可知，F(xiàn)FA算法成功預測的關鍵節(jié)點排名為{1,3,7,8,9,10}，PCP算法成功預測的關鍵節(jié)點排名為{1,4,5,6,7,8,10}，OLMiner算法成功預測的關鍵節(jié)點排名為{1,2,4,6,9}，F(xiàn)TS算法成功預測的關鍵節(jié)點排名為{1,2,3,5,6,7,8,10}，GNN算法成功預測的關鍵節(jié)點排名為{1,2,3,4,5,6,7,8,9,10}。從各算法預測的排名結(jié)果可以看出，F(xiàn)TS與GNN預測的排名較可靠，F(xiàn)FA，PCP與OLMiner預測的排名可靠性較低。

為評估各對比算法識別全網(wǎng)復雜網(wǎng)絡中關鍵節(jié)點的性能，建立一組對比實驗：先采用各算法分別搜索復雜網(wǎng)絡測試集top200的節(jié)點列表，再通過準確率、召回率、精度與F1-score評價識別結(jié)果與正定結(jié)果之間的匹配度，結(jié)果如圖5所示。從圖5可以看出，OLMiner算法的準確率、召回率、精度與F1-score均明顯低于其他4種對比算法，該算法是一種基于兩階段聚類的復雜網(wǎng)絡關鍵節(jié)點檢測算法，其優(yōu)勢是通過聚類處理降低了社區(qū)間連接對關鍵節(jié)點識別的干擾，然而對于全網(wǎng)關鍵節(jié)點的識別性能較差。FTS算法采用模糊系統(tǒng)建模網(wǎng)絡的社交關系，再利用模糊理論推斷網(wǎng)絡中最受信任的節(jié)點，其推理效果明顯好于FFA算法與PCP算法。本文借助GNN的權重參數(shù)將鄰居節(jié)點信息納入當前節(jié)點，因此GNN可自動考慮節(jié)點相關的復雜網(wǎng)絡拓撲信息，GNN的信息包含了復雜網(wǎng)絡的全局拓撲信息與局部社區(qū)信息，因此其性能較好。觀察表2的結(jié)果可知，不同評價標準所選出的關鍵節(jié)點存在不可忽略的差異，因此很難產(chǎn)生統(tǒng)一的關鍵節(jié)點集。綜合而言，本文算法的關鍵節(jié)點命中率明顯高于其他對比算法。

圖5 復雜網(wǎng)絡top200的關鍵節(jié)點識別性能Fig.5 Top200 crucial nodes recognition performance in complex networks

4.5.2 社區(qū)關鍵節(jié)點檢測性能實驗

目前，大規(guī)模復雜網(wǎng)絡通常呈現(xiàn)出社區(qū)性拓撲結(jié)構的特性，節(jié)點在社區(qū)內(nèi)關系緊密而在社區(qū)間關系稀疏，每個社區(qū)內(nèi)的關鍵節(jié)點對該社區(qū)內(nèi)節(jié)點的影響力較大，而對其他社區(qū)內(nèi)節(jié)點的影響力較小，因此識別每個社區(qū)的關鍵節(jié)點也是關鍵節(jié)點檢測算法的一個重要研究目標。wiki vote數(shù)據(jù)集的測試集共有28個社區(qū)，表4統(tǒng)計了BC，DC，CC與PR識別的各社區(qū)關鍵節(jié)點。由表4可知，基于不同評價指標產(chǎn)生的社區(qū)關鍵節(jié)點存在差異。為了分析各指標的綜合識別結(jié)果，將每個社區(qū)中出現(xiàn)次數(shù)最多的關鍵節(jié)點作為該社區(qū)的正定關鍵節(jié)點，最終產(chǎn)生的top10節(jié)點序號分別為{7452233 0661 089，3 397，165，6 713，28，72，4 2204 434，75，4 4402 268，2 896，772，1 373，522，3 461，3683 398，2 849，2 990，1 725，8 493，128，5 421，1 9841 5786 8232 748，568，47}。

表4 wiki vote數(shù)據(jù)集各評價標準的社區(qū)關鍵節(jié)點Tab.4 Crucial community nodes detected with all evaluation criterions on wiki vote dataset

為了評估關鍵節(jié)點檢測算法對社區(qū)關鍵節(jié)點的識別性能，運行各算法分別處理每個社區(qū)的局部數(shù)據(jù)，各算法識別的社區(qū)領袖如表5所示。由表5可知，F(xiàn)FA算法正確預測的社區(qū)領袖數(shù)量為17，準確率為70.83%；PCP算法正確預測的社區(qū)領袖數(shù)量為17，準確率為70.83%；OLMiner算法正確預測的社區(qū)領袖數(shù)量為15，準確率為62.5%；FTS算法正確預測的社區(qū)領袖數(shù)量為16，準確率為66.67%；GNN算法正確預測的社區(qū)領袖數(shù)量為21，準確率為87.5%。FFA算法與PCP算法均為基于社區(qū)的關鍵節(jié)點挖掘算法，其性能優(yōu)于OLMiner算法與FTS算法。此外，GNN對全局網(wǎng)絡與局部網(wǎng)絡的學習能力均較強，因此GNN算法正確預測的社區(qū)社交領袖數(shù)量最多，高于其他4個對比算法。觀察表5的結(jié)果可知，不同評價標準所選出的關鍵節(jié)點存在不可忽略的差異，因此很難產(chǎn)生統(tǒng)一的關鍵節(jié)點集。綜合而言，本文算法的關鍵節(jié)點命中率明顯高于其他對比算法。

表5 wiki vote數(shù)據(jù)集各評價標準的關鍵節(jié)點Tab.5 Crucial community nodes detected with all evaluation criterions on wiki vote dataset

4.5.3 算法效率實驗

由于復雜網(wǎng)絡具有動態(tài)變化的特點，因此計算效率是影響相關算法是否具備可擴展能力的重要因素。實驗中每個算法在wiki vote數(shù)據(jù)集上獨立運行10次，計算每個算法的平均運行時間，結(jié)果如表6所示。觀察表6中的結(jié)果可知，OLMiner算法的平均計算時間最短，其原因主要是OLMiner算法在第1階段采用社區(qū)檢測技術以緩解社區(qū)間的影響力重疊現(xiàn)象，該措施大幅減小了候選子集的數(shù)據(jù)規(guī)模，有效縮短了第2階段搜索關鍵節(jié)點的計算時間。然而，F(xiàn)TS算法先采用模糊系統(tǒng)建模網(wǎng)絡的社交關系，再利用模糊理論推斷網(wǎng)絡中最受信任的節(jié)點，由于模糊系統(tǒng)在大數(shù)據(jù)上的工作效率較低，因此FTS算法的平均計算時間最長。本文GNN算法的平均計算時間為次優(yōu)值，略慢于OLMiner算法，但明顯快于FFA算法、PCP算法與FTS算法。

表6 關鍵節(jié)點檢測算法的平均計算時間Tab.6 Average computation time of crucial nodes detection algorithms 單位：ms

5 結(jié)束語

為了解決傳統(tǒng)復雜網(wǎng)絡關鍵節(jié)點檢測算法準確性低以及可靠性不足的問題，結(jié)合GNN模型提出了一種可擴展復雜網(wǎng)絡關鍵節(jié)點檢測算法。將復雜網(wǎng)絡建模為圖模型，利用GNN評估網(wǎng)絡中節(jié)點與連接的關鍵性評分。在GNN訓練方面，為了改善關鍵節(jié)點檢測算法的可擴展性及可靠性，采用RL搜索GNN的超參數(shù)。通過GNN的權重參數(shù)將鄰居節(jié)點信息納入當前節(jié)點，GNN的信息包含了復雜網(wǎng)絡的全局拓撲信息與局部社區(qū)信息，因此GNN對全局網(wǎng)絡與局部網(wǎng)絡的學習能力均較強，對全局復雜網(wǎng)絡與局部社區(qū)的關鍵節(jié)點識別問題均達到了較好的效果。