基于圖神經(jīng)網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)算法

陳 娜

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

0 引言

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

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

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

本文將復(fù)雜網(wǎng)絡(luò)建模為圖模型，采用雙重魯棒性指標(biāo)作為節(jié)點(diǎn)的關(guān)鍵性評(píng)價(jià)標(biāo)準(zhǔn)，然后利用GNN的節(jié)點(diǎn)嵌入模塊學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息，利用回歸模塊推理節(jié)點(diǎn)的關(guān)鍵性評(píng)分。此外，提出了基于RL的GNN訓(xùn)練方法，該方法通過(guò)獎(jiǎng)勵(lì)函數(shù)學(xué)習(xí)GNN的超參數(shù)并輸出一個(gè)動(dòng)作序列，該動(dòng)作序列對(duì)應(yīng)該復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別的GNN模型。實(shí)驗(yàn)結(jié)果表明，本算法使用GNN檢測(cè)的關(guān)鍵節(jié)點(diǎn)具有較高的準(zhǔn)確性，且檢測(cè)速度較快。

1 網(wǎng)絡(luò)模型

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

ru=f(hu,hv)，

(1)

式中，hu，hv分別為節(jié)點(diǎn)u與v的特征向量；ru為關(guān)鍵性評(píng)分。GNN在訓(xùn)練過(guò)程學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)的關(guān)鍵性評(píng)分關(guān)系f()，輸出預(yù)測(cè)的關(guān)鍵性評(píng)分關(guān)系f′()。

2 基于GNN的關(guān)鍵節(jié)點(diǎn)檢測(cè)模型

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

2.1 節(jié)點(diǎn)關(guān)鍵性評(píng)估

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

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

(2)

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

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

(3)

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

2.2 節(jié)點(diǎn)嵌入模塊

GNN第1個(gè)子模塊基于圖拓?fù)浣Y(jié)構(gòu)信息與節(jié)點(diǎn)關(guān)鍵性評(píng)分學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的嵌入向量。如果節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中距離越近，那么節(jié)點(diǎn)在嵌入空間中距離也越近。GNN將復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)映射到嵌入空間的流程如圖1所示。

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

節(jié)點(diǎn)嵌入模塊包含2個(gè)步驟：

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

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

(4)

式中，函數(shù)D()計(jì)算2個(gè)節(jié)點(diǎn)之間的最小跳數(shù)；u為目標(biāo)節(jié)點(diǎn)；v為圖中的其他節(jié)點(diǎn)。

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

(5)

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

(6)

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

算法1 節(jié)點(diǎn)嵌入表示算法輸入:圖G,輸入節(jié)點(diǎn)特征Xv,組合權(quán)重W,聚合權(quán)重Q。輸出:節(jié)點(diǎn)嵌入向量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)]); ∥ ‖.‖表示聚合運(yùn)算6. endfor7.endfor8.return hlv;

2.3 回歸模塊

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

(7)

2.4 節(jié)點(diǎn)關(guān)鍵性評(píng)分預(yù)測(cè)模塊

GNN預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)鍵性示意如圖3所示。GNN模型預(yù)測(cè)輸入復(fù)雜網(wǎng)絡(luò)各節(jié)點(diǎn)的關(guān)鍵性評(píng)分，將復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)按關(guān)鍵性降序排列。

圖3 復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的關(guān)鍵性預(yù)測(cè)示意Fig.3 Cruciality prediction diagram of complex network nodes

3 GNN的訓(xùn)練方法

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

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

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

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

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

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

3.2 基于RL的GNN訓(xùn)練方法

借助RL框架訓(xùn)練GNN，訓(xùn)練目標(biāo)是最小化節(jié)點(diǎn)關(guān)鍵性評(píng)分估計(jì)值與實(shí)際值之間的差異。RL的狀態(tài)為GNN的預(yù)測(cè)性能，動(dòng)作為GNN超參數(shù)，RL通過(guò)獎(jiǎng)勵(lì)函數(shù)尋找預(yù)測(cè)最準(zhǔn)確的GNN模型。

3.2.1 RL框架

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

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

(8)

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

Q-leaning在每個(gè)時(shí)間步結(jié)束更新Q-table的獎(jiǎng)勵(lì)，更新的獎(jiǎng)勵(lì)可定義為：

(9)

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

3.2.2 RL獎(jiǎng)勵(lì)函數(shù)

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

(10)

3.2.3 RL隨機(jī)采樣訓(xùn)練

Q-matrix中保存了Q-learning所有時(shí)間步的狀態(tài)、動(dòng)作與獎(jiǎng)勵(lì)數(shù)據(jù)，假設(shè)Q-matrix共有M個(gè)Q-value，Q-learning訓(xùn)練階段對(duì)Q-matrix隨機(jī)采樣K次，產(chǎn)生包含K個(gè)Q-value的訓(xùn)練集。基于歐氏距離度量實(shí)際Q-value與期望Q-value之間的距離，由此可獲得每對(duì)數(shù)據(jù)的損失函數(shù)：

(11)

式中，rt表示在時(shí)間步t的第i個(gè)Q-value。

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

(12)

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

4 實(shí)驗(yàn)與結(jié)果分析

文中使用Gephi version 0.9.2軟件分析復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)，使用Python 3.6實(shí)現(xiàn)文中相關(guān)算法，編程環(huán)境為Pycharm與Eclipse集成的開(kāi)發(fā)平臺(tái)。PC機(jī)的配置為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í)驗(yàn)的真實(shí)數(shù)據(jù)集，共包含7 115個(gè)節(jié)點(diǎn)與103 689條連接。數(shù)據(jù)集包含了一個(gè)用戶對(duì)另一個(gè)用戶的投票信息來(lái)推選Wikipedia上的關(guān)鍵節(jié)點(diǎn)。網(wǎng)絡(luò)模塊度(Network Modularity)是由Newman提出的一種衡量復(fù)雜網(wǎng)絡(luò)中社區(qū)強(qiáng)度與穩(wěn)定性的常用評(píng)價(jià)方法，模塊度的范圍為[-1，1]。wiki vote數(shù)據(jù)集的模塊度為0.428，說(shuō)明該復(fù)雜網(wǎng)絡(luò)包含密集的社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)的平均集聚系數(shù)度量了復(fù)雜網(wǎng)絡(luò)中頂點(diǎn)之間結(jié)集成團(tuán)的程度，具體而言，反映了復(fù)雜網(wǎng)絡(luò)中用戶與相鄰用戶之間的密切程度。wiki vote數(shù)據(jù)集的平均集聚系數(shù)為0.140 9，說(shuō)明該復(fù)雜網(wǎng)絡(luò)中封閉三角形拓?fù)浣Y(jié)構(gòu)較少。綜合分析wiki vote數(shù)據(jù)集的模塊度與集聚系數(shù)可知，該復(fù)雜網(wǎng)絡(luò)的社區(qū)內(nèi)連接較密集，而社區(qū)之間的關(guān)系較稀疏，這也體現(xiàn)了當(dāng)前主流大規(guī)模復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特點(diǎn)。

4.2 評(píng)價(jià)指標(biāo)

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

BC的計(jì)算公式為：

(13)

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

DC的計(jì)算公式為：

(14)

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

CC的計(jì)算公式為：

CC(x)=dig(x)，

(15)

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

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

(16)

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

4.3 GNN訓(xùn)練

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

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

4.4 對(duì)比算法

采用多個(gè)關(guān)鍵節(jié)點(diǎn)檢測(cè)算法來(lái)構(gòu)建對(duì)比實(shí)驗(yàn)，以全面評(píng)估各復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)算法的有效性。所考慮的對(duì)比算法包括：

FFA算法[21]：該算法是一種基于螢火蟲(chóng)優(yōu)化算法(Firefly Algorithm)的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)算法，先使用Louvain方法將復(fù)雜網(wǎng)絡(luò)劃分成社區(qū)，并在節(jié)點(diǎn)重要性評(píng)估標(biāo)準(zhǔn)中考慮了局部社區(qū)的拓?fù)湫畔ⅲ缓罄梦灮鹣x(chóng)優(yōu)化算法搜索復(fù)雜網(wǎng)絡(luò)中重要性最高的節(jié)點(diǎn)。

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

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

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

4.5 實(shí)驗(yàn)結(jié)果與分析

4.5.1 復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)性能實(shí)驗(yàn)

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

表2 wiki vote數(shù)據(jù)集各評(píng)價(jià)標(biāo)準(zhǔn)的關(guān)鍵節(jié)點(diǎn)Tab.2 Crucial nodes detected with all evaluation criterions on wiki vote dataset

各關(guān)鍵節(jié)點(diǎn)檢測(cè)算法輸出的top10關(guān)鍵節(jié)點(diǎn)如表3所示。

表3 各算法檢測(cè)的關(guān)鍵節(jié)點(diǎn)Tab.3 Crucial nodes detected by all algorithms

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

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

圖5 復(fù)雜網(wǎng)絡(luò)top200的關(guān)鍵節(jié)點(diǎn)識(shí)別性能Fig.5 Top200 crucial nodes recognition performance in complex networks

4.5.2 社區(qū)關(guān)鍵節(jié)點(diǎn)檢測(cè)性能實(shí)驗(yàn)

目前，大規(guī)模復(fù)雜網(wǎng)絡(luò)通常呈現(xiàn)出社區(qū)性拓?fù)浣Y(jié)構(gòu)的特性，節(jié)點(diǎn)在社區(qū)內(nèi)關(guān)系緊密而在社區(qū)間關(guān)系稀疏，每個(gè)社區(qū)內(nèi)的關(guān)鍵節(jié)點(diǎn)對(duì)該社區(qū)內(nèi)節(jié)點(diǎn)的影響力較大，而對(duì)其他社區(qū)內(nèi)節(jié)點(diǎn)的影響力較小，因此識(shí)別每個(gè)社區(qū)的關(guān)鍵節(jié)點(diǎn)也是關(guān)鍵節(jié)點(diǎn)檢測(cè)算法的一個(gè)重要研究目標(biāo)。wiki vote數(shù)據(jù)集的測(cè)試集共有28個(gè)社區(qū)，表4統(tǒng)計(jì)了BC，DC，CC與PR識(shí)別的各社區(qū)關(guān)鍵節(jié)點(diǎn)。由表4可知，基于不同評(píng)價(jià)指標(biāo)產(chǎn)生的社區(qū)關(guān)鍵節(jié)點(diǎn)存在差異。為了分析各指標(biāo)的綜合識(shí)別結(jié)果，將每個(gè)社區(qū)中出現(xiàn)次數(shù)最多的關(guān)鍵節(jié)點(diǎn)作為該社區(qū)的正定關(guān)鍵節(jié)點(diǎn)，最終產(chǎn)生的top10節(jié)點(diǎn)序號(hào)分別為{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ù)集各評(píng)價(jià)標(biāo)準(zhǔn)的社區(qū)關(guān)鍵節(jié)點(diǎn)Tab.4 Crucial community nodes detected with all evaluation criterions on wiki vote dataset

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

表5 wiki vote數(shù)據(jù)集各評(píng)價(jià)標(biāo)準(zhǔn)的關(guān)鍵節(jié)點(diǎn)Tab.5 Crucial community nodes detected with all evaluation criterions on wiki vote dataset

4.5.3 算法效率實(shí)驗(yàn)

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

表6 關(guān)鍵節(jié)點(diǎn)檢測(cè)算法的平均計(jì)算時(shí)間Tab.6 Average computation time of crucial nodes detection algorithms 單位：ms

5 結(jié)束語(yǔ)

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