楊洋 王俊峰

準(zhǔn)確識別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點是復(fù)雜網(wǎng)絡(luò)研究的重要內(nèi)容之一.現(xiàn)存的關(guān)鍵節(jié)點識別方法多數(shù)是基于網(wǎng)絡(luò)結(jié)構(gòu)提出的中心性度量方法，識別準(zhǔn)確率低且適用范圍具有局限性.因此本文提出了基于圖卷積網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別方法，不僅考慮了節(jié)點屬性，還考慮了網(wǎng)絡(luò)結(jié)構(gòu)和鄰居節(jié)點結(jié)構(gòu).首先，根據(jù)網(wǎng)絡(luò)圖例數(shù)據(jù)提取多維度特征并構(gòu)建特征向量;其次，將節(jié)點特征向量輸入到GCN層學(xué)習(xí);最后，通過回歸損失函數(shù)計算出最小損失，識別出關(guān)鍵節(jié)點.本文選取傳播動力學(xué)中的SIR模擬實驗和牽制控制實驗作為評價方式，在不同類型的真實網(wǎng)絡(luò)上進(jìn)行驗證.結(jié)果表明本文提出的方法在適用范圍和準(zhǔn)確率方面較其他方法更具優(yōu)勢.

關(guān)鍵節(jié)點; 復(fù)雜網(wǎng)絡(luò); 圖卷積網(wǎng)絡(luò)

TP301.6A2023.032002

收稿日期： 2022-06-28

基金項目： 基礎(chǔ)加強(qiáng)計劃重點項目（2019-JCJQ-ZD-113）; 國家自然科學(xué)基金（U2133208）； 四川省青年科技創(chuàng)新研究團(tuán)隊（2022JDTD0014）

作者簡介： 楊洋（1998-）， 河南平頂山人， 碩士研究生， 研究方向為網(wǎng)絡(luò)空間安全. E-mail： 305004556@qq.com

通訊作者： 王俊峰. E-mail： wangjf@scu.edu.cn

Research on key node identification of complex network based on GCN

YANG Yang， WANG Jun-Feng

（College of Computer Science， Sichuan University， Chengdu 610065， China）

Accurately identifying the key nodes in the network is one of the important research topics in complex networks. Most of the existing key node identification methods are based on the centrality measurement method by the network structure， which has low identification accuracy and limited scope of application. A key node identification method， based on Graph Convolutional Network （GCN）， is proposed in this paper， which considers not only the node attributes， but also the network structure and neighbor node structure. Multidimensional features are extracted first from the network legend data to construct feature vectors and then the node feature vector is input to the GCN layer for learning. Finally， the minimum loss is calculated with the regression loss function， and the key nodes are identified. In this paper， SIR （Susceptible Infected Removed） is choosed as the evaluation method in the propagation dynamics simulation experiment and Pinning Control experiment， the proposed method is verified on different types of real networks， the results show that the GCN-based method proposed in this paper outperforms other methods in terms of scope of application and accuracy.

Key node; Complex network; Graph convolutional network

1 引 言

在網(wǎng)絡(luò)理論的研究中，生物網(wǎng)絡(luò)、電力網(wǎng)絡(luò)以及通訊網(wǎng)絡(luò)等都被證實為復(fù)雜網(wǎng)絡(luò)［1］.關(guān)鍵節(jié)點［2］是能高度影響復(fù)雜網(wǎng)絡(luò)功能的少數(shù)特殊節(jié)點.定位關(guān)鍵節(jié)點對網(wǎng)絡(luò)信息傳遞、網(wǎng)絡(luò)同步、網(wǎng)絡(luò)控制起著至關(guān)重要的作用［3］.例如：社交網(wǎng)絡(luò)中權(quán)威賬號對輿論的引導(dǎo)作用明顯;社會網(wǎng)絡(luò)中控制流行病的爆發(fā)點能抑制傳染病大規(guī)模傳播;交通網(wǎng)絡(luò)中挖掘關(guān)鍵樞紐能夠為規(guī)劃航線做出理論支撐［4］.此外，研究復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點在案件偵察、輿情控制等方面也有廣闊前景［5］.

目前存在的關(guān)鍵節(jié)點識別方法是基于網(wǎng)絡(luò)物理結(jié)構(gòu)的中心性度量方法［6-8］，他們從網(wǎng)絡(luò)的局部屬性、全局屬性、位置屬性以及不同的隨機(jī)游走策略4個方面度量節(jié)點的關(guān)鍵程度［9］.相關(guān)方法有：度中心性（Degree Centrality）算法、介數(shù)中心性（Betweenness Cen-trality）算法、K-Shell算法、PageRank算法等［10］.由于這些方法通常從單一角度尋找反映節(jié)點關(guān)鍵程度的因素，考慮得并不全面，且忽略了不同網(wǎng)絡(luò)的結(jié)構(gòu)差異性，導(dǎo)致識別準(zhǔn)確率較低.

相關(guān)研究［9］表明，節(jié)點的關(guān)鍵性與多種因素有關(guān)，例如：網(wǎng)絡(luò)的結(jié)構(gòu)、節(jié)點的特征以及鄰居節(jié)點間的結(jié)構(gòu).因此，對網(wǎng)絡(luò)中多類信息進(jìn)行融合分析能更準(zhǔn)確地反映網(wǎng)絡(luò)的真實情況，識別出關(guān)鍵節(jié)點.圖卷積網(wǎng)絡(luò)（Graph Convolutional Network， GCN）［11］是一種深度學(xué)習(xí)模型，由于它能夠處理圖形結(jié)構(gòu)數(shù)據(jù)，且能研究網(wǎng)絡(luò)拓?fù)渲械墓?jié)點和連邊信息，因此已經(jīng)成為處理復(fù)雜網(wǎng)絡(luò)相關(guān)任務(wù)的有效方法之一［12］.對于關(guān)鍵節(jié)點識別任務(wù)， GCN能夠迭代地聚集網(wǎng)絡(luò)中節(jié)點及鄰居節(jié)點間的結(jié)構(gòu)信息，綜合分析影響節(jié)點關(guān)鍵性的多種因素.

基于此，本文提出了基于GCN的關(guān)鍵節(jié)點識別方法.該方法從節(jié)點自身屬性、復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)與鄰居節(jié)點間的結(jié)構(gòu)等三方面提取了7個具有代表性的特征，結(jié)合節(jié)點的二度子圖進(jìn)行分析.這些特征綜合了網(wǎng)絡(luò)局部屬性、全局屬性、位置屬性以及隨機(jī)游走屬性，適用于不同類型的復(fù)雜網(wǎng)絡(luò)［13-18］.此外，本方法還增加了節(jié)點的圈比［13］、橋接性［16］、節(jié)點嵌入［17］3個更具判別能力的特征，相較于單一特征工程方法［18］，特征維度更加廣泛.本文在8個真實的復(fù)雜網(wǎng)絡(luò)上對此方法進(jìn)行驗證，使用傳播動力學(xué)中的SIR模擬實驗和牽制控制實驗作為評價方式［13］.在SIR模擬實驗中平均感染率為其他方法的1.3倍;在牽制控制實驗中牽制效率P的性能在36次實驗中有34次排名第一，2次排名第二.實驗結(jié)果表明，本文提出的方法在準(zhǔn)確性和適用范圍方面較其他方法更具有優(yōu)勢.

2 相關(guān)工作

基于中心性的關(guān)鍵節(jié)點識別方法［19］主要從復(fù)雜網(wǎng)絡(luò)的局部屬性、全局屬性、位置屬性以及隨機(jī)游走四個方面進(jìn)行研究.

（1） 局部屬性. 基于網(wǎng)絡(luò)局部屬性的關(guān)鍵節(jié)點識別方法主要考慮了節(jié)點自身的屬性及其鄰居的相關(guān)信息，這些指標(biāo)的計算復(fù)雜度較低，在結(jié)構(gòu)復(fù)雜的大規(guī)模網(wǎng)絡(luò)中使用廣泛.度中心性算法［20］是網(wǎng)絡(luò)中刻畫節(jié)點關(guān)鍵程度最簡單的指標(biāo)，它通過節(jié)點度（與其相連的鄰居節(jié)點數(shù)量）的大小來判斷該節(jié)點的重要程度.在網(wǎng)絡(luò)傳播過程中，大度節(jié)點可以最大限度地傳染它的鄰居，也會以較大概率被鄰居所傳染.度中心性算法只計算了節(jié)點的鄰居數(shù)目，卻沒有考慮鄰居節(jié)點的屬性.局部中心性算法（Local Centrality）［20］考慮了節(jié)點鄰居的屬性與間接鄰居的屬性，但不適用于有向網(wǎng)絡(luò).半局部算法（Cluster Rank）［21］是針對有向網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別算法，該算法考慮了節(jié)點鄰居的屬性與聚類系數(shù)在網(wǎng)絡(luò)傳播中的影響.半局部算法的準(zhǔn)確性優(yōu)于局部中心性算法與度中心性算法.

（2） 全局屬性. 基于網(wǎng)絡(luò)全局屬性的關(guān)鍵節(jié)點識別算法考慮的是節(jié)點在整個網(wǎng)絡(luò)中的屬性.較為常用的算法有介數(shù)中心性算法（Betweenness Centrality）［21］和接近中心性算法（Closeness Centrality）［21］.在介數(shù)中心性算法中，判斷節(jié)點的關(guān)鍵性指標(biāo)是該節(jié)點在網(wǎng)絡(luò)中進(jìn)行信息傳播時的負(fù)載量.具體的判別方法是計算出任意兩個節(jié)點之間的最短路徑，若一個節(jié)點包含的最短路徑數(shù)越多，則該節(jié)點的關(guān)鍵程度越大.接近中心性算法表達(dá)節(jié)點到達(dá)網(wǎng)絡(luò)其他節(jié)點的快慢程度.基于網(wǎng)絡(luò)全局屬性的關(guān)鍵節(jié)點挖掘算法準(zhǔn)確性較高，但計算復(fù)雜度也很高.

（3） 位置屬性. 基于網(wǎng)絡(luò)位置屬性的關(guān)鍵節(jié)點識別算法是根據(jù)節(jié)點在網(wǎng)絡(luò)中所處的位置來度量該節(jié)點的關(guān)鍵程度.若一個節(jié)點在網(wǎng)絡(luò)中處于核心位置，則認(rèn)為其影響力較大.反之，則認(rèn)為該節(jié)點的影響力有限.K-殼分解算法（ K-Shell）［22］是最經(jīng)典的基于網(wǎng)絡(luò)位置屬性的關(guān)鍵節(jié)點挖掘算法. K-殼分解算法的實現(xiàn)方式是逐層去除小于等于度為K的節(jié)點，將節(jié)點歸為不同的層次，處于網(wǎng)絡(luò)內(nèi)層的節(jié)點最為關(guān)鍵.基于網(wǎng)絡(luò)位置屬性的挖掘算法對網(wǎng)絡(luò)結(jié)構(gòu)有一定的要求.例如K-殼分解算法對星型網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)不適用，并且難以確定各個指標(biāo)的最佳權(quán)重因子.

（4） 隨機(jī)游走. 基于隨機(jī)游走的關(guān)鍵節(jié)點識別算法是一種動態(tài)識別關(guān)鍵節(jié)點的過程，主要應(yīng)用領(lǐng)域是搜索引擎用來分析網(wǎng)頁間質(zhì)量的排序.該算法具體的實現(xiàn)方式是研究網(wǎng)頁之間的關(guān)聯(lián)指向，若一個網(wǎng)頁被多個高質(zhì)量網(wǎng)頁所指，則證明其本身質(zhì)量較高.常見的方法有HITS算法（Hypertext-Induced Topic Search）、谷歌搜索引擎使用的PageRank算法以及Leader Rank算法等［23］.

除了以上方法外，還有一些方法從其他角度出發(fā)，基于網(wǎng)絡(luò)的連通程度、網(wǎng)絡(luò)中邊的屬性等方面對節(jié)點的關(guān)鍵程度進(jìn)行判斷.這些方法都是從單一角度對節(jié)點進(jìn)行度量，存在著表征不全、準(zhǔn)確率低等問題.節(jié)點的關(guān)鍵性不僅由網(wǎng)絡(luò)結(jié)構(gòu)決定，還與節(jié)點自身特性以及鄰居節(jié)點的信息有關(guān).

3 基于GCN的關(guān)鍵節(jié)點識別技術(shù)

3.1 關(guān)鍵節(jié)點識別架構(gòu)

基于GCN的關(guān)鍵節(jié)點識別方法流程如圖1所示.

該方法主要分為4個步驟：數(shù)據(jù)處理、特征提取、生成關(guān)鍵節(jié)點識別模型、網(wǎng)絡(luò)關(guān)鍵節(jié)點預(yù)測.首先，在數(shù)據(jù)處理過程中我們將一些網(wǎng)絡(luò)數(shù)據(jù)中含有的極少量孤立的節(jié)點進(jìn)行移除操作，使得本方法所使用的輸入圖例均為連通圖;其次，進(jìn)行特征提取.在網(wǎng)絡(luò)中提取每個節(jié)點的二度子圖，構(gòu)建子圖網(wǎng)絡(luò)，提取子圖網(wǎng)絡(luò)的特征（詳見第3.2節(jié)），并為每個節(jié)點構(gòu)建7個特征組成的特征向量（詳見第3.3節(jié)）.將每個節(jié)點的子圖網(wǎng)絡(luò)特征和特征向量作為模型的原始輸入.為了避免實驗過度擬合，在將特征送入模型進(jìn)行學(xué)習(xí)前，對提取的特征進(jìn)行歸一化處理;接著，構(gòu)建關(guān)鍵節(jié)點識別模型.根據(jù)提取到每個節(jié)點的特征輸入到GCN層進(jìn)行學(xué)習(xí)，同時為了更好地利用節(jié)點自身屬性，該層增加了跳躍連接.然后通過三個全連接層對關(guān)鍵節(jié)點預(yù)測任務(wù)學(xué)習(xí);最后，輸入圖例數(shù)據(jù)，通過回歸損失函數(shù)MSE計算出最小損失，該模型的輸出值是預(yù)測網(wǎng)絡(luò)中每個節(jié)點的關(guān)鍵性得分情況.

3.2 構(gòu)建子圖網(wǎng)絡(luò)

本文的研究對象是無權(quán)無向網(wǎng)絡(luò)G，每個G由點集V={v1，v2，…，vn}和邊集E={e1，e2，…，en}構(gòu)成.在本文中N代表網(wǎng)絡(luò)中存在節(jié)點的數(shù)量，E代表網(wǎng)絡(luò)中存在邊的數(shù)量.網(wǎng)絡(luò)G的鄰接矩陣為A=aijN×N，定義為

aij=1， 節(jié)點i和節(jié)點j存在連邊0， 節(jié)點i和節(jié)點j不存在連邊（1）

在GCN模型中，節(jié)點的特征與其鄰居網(wǎng)絡(luò)關(guān)聯(lián)較大，節(jié)點的鄰居網(wǎng)絡(luò)對該點關(guān)鍵性起著至關(guān)重要的作用.每一層GCN的輸入是鄰接矩陣和節(jié)點的特征.根據(jù)三度影響力原則［24］，本文選取距離目標(biāo)節(jié)點不超過3的鄰居節(jié)點構(gòu)建該點的二度子圖網(wǎng)絡(luò)，計算出子圖網(wǎng)絡(luò)的對稱歸一化拉普拉斯矩陣 （Symmetric Normalized Laplacian），其中節(jié)點的搜索方式為廣度優(yōu)先搜索（BFS）.

3.3 特征提取

根據(jù)現(xiàn)存關(guān)鍵節(jié)點識別方法的諸多不足，我們對此模型的特征有了以下三方面的考慮：（1） 對目前使用廣泛的基于網(wǎng)絡(luò)的局部屬性、全局屬性、位置屬性等方法進(jìn)行綜合；（2） 增加了節(jié)點的圈比、橋接值、節(jié)點嵌入等三個更具判別能力的點的特征屬性，用于彌補(bǔ)和完善其它方法存在的缺陷；（3）根據(jù)GCN的特點，抽取圖例中節(jié)點的子圖構(gòu)建特征.

本文方法使用的7個特征具體如特征（1）～（7），這些特征對網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點信息以及鄰居節(jié)點的信息進(jìn)行匯總，從不同的角度深入剖析復(fù)雜網(wǎng)絡(luò).其中，特征（1）～（3）彌補(bǔ)和完善了現(xiàn)存方法的缺陷，特征（4）～（7）對使用廣泛的基于網(wǎng)絡(luò)結(jié)構(gòu)的方法進(jìn)行綜合.

（1） 節(jié)點的圈比（Node Cycle Ratio）.節(jié)點的圈比指一個節(jié)點參與到其他節(jié)點的最短圈（包含這個節(jié)點的長度最小的圈）的程度.定義Si表示與節(jié)點i相關(guān)聯(lián)的最短循環(huán)的集合，S=∪i∈VSi是G中所有最短圈的集合.定義圈數(shù)矩陣C=cijN×N刻畫G的圈結(jié)構(gòu)，N是節(jié)點數(shù).如果i≠j，則cij是通過節(jié)點i和j的圈數(shù).如果i=j，Cij是S中包含節(jié)點i的圈數(shù).圈比ri估計了節(jié)點i參與S中其他節(jié)點的最短圈的重要性.

ri=0， cii=0∑j，cij>0cijcjj， cii>0（2）

在此定義中，僅考慮與每個節(jié)點相關(guān)的最短圈.在節(jié)點的圈比中節(jié)點是否重要取決于它對鄰居節(jié)點的參與程度，圈上的鄰居節(jié)點越多，節(jié)點本身的圈數(shù)越多，則該節(jié)點越重要.將節(jié)點的圈比作為特征對網(wǎng)絡(luò)局部屬性的缺陷做出了完善和補(bǔ)充.

（2） 節(jié)點的橋接值.復(fù)雜網(wǎng)絡(luò)具有社團(tuán)結(jié)構(gòu)，符合社會學(xué)的“弱連接的強(qiáng)度”理論：1）弱連接（Weak Tie）各個社團(tuán)之間聯(lián)系稀疏；2）強(qiáng)連接（Strong Ties）社團(tuán)內(nèi)部節(jié)點聯(lián)系緊密，使用社區(qū)發(fā)現(xiàn)法能將網(wǎng)絡(luò)分為不同的社團(tuán).

本文采用Louvain社區(qū)發(fā)現(xiàn)算法對網(wǎng)絡(luò)進(jìn)行劃分，模塊度（Modularity）為衡量社團(tuán)劃分質(zhì)量的標(biāo)準(zhǔn).令C代表網(wǎng)絡(luò)社團(tuán)，Ci與Cj表示節(jié)點i與節(jié)點j在網(wǎng)絡(luò)中的分屬社團(tuán).若節(jié)點i與節(jié)點j同屬一個社團(tuán)，則δ的值為1，反之δ的值為0.令ev w為社團(tuán)v和w之間的連邊占整個網(wǎng)絡(luò)中邊的比例，則有以下公式：

ev w=12M∑ijaijδCi，vδCj，w（3）

av=12M∑idiδCi，v（4）

其中，αv是一邊與社團(tuán)v中節(jié)點相連的邊在整個網(wǎng)絡(luò)中的比例，di表示點i的度數(shù).

模塊度Q的表示公式是

Q=12M∑ij（aij-didj2M）∑vδCi，vδCj，v，

簡化后表示為

Q=∑ev v-a2v（5）

橋接值VC描述節(jié)點連接的社團(tuán)種類，即該節(jié)點的鄰居節(jié)點所屬的社團(tuán)情況.VCi定義為與節(jié)點i直接相連的社團(tuán)數(shù)量（包括自己所在的社團(tuán)）.

例如，在圖2網(wǎng)絡(luò)中，可以將網(wǎng)絡(luò)分為4個社團(tuán)G1、G2、G3、G4.

其中，G1=v1，v2，v3，v4，v5，v6；G2=v11，v12，v13，v14；G3=v7，v8，v9，v10；G4=v15，v16，v17，v18，v19，v20，v21.節(jié)點1的橋接值為VC（1）=2，節(jié)點2的橋接值為VC（2）=1，節(jié)點11的橋接值為VC（11）=4.

節(jié)點橋接值越大，證明該節(jié)點參與社團(tuán)越多，能夠獲得的信息種類越多.將節(jié)點的橋接值作為特征彌補(bǔ)了節(jié)點位置屬性存在的缺陷.

（3） 節(jié)點嵌入.圖的表示學(xué)習(xí)的特點是自動學(xué)習(xí)網(wǎng)絡(luò)的特征，能夠針對不同任務(wù)學(xué)習(xí)得到適合任務(wù)的嵌入表示.節(jié)點嵌入的學(xué)習(xí)方式為無監(jiān)督學(xué)習(xí).本文使用node2vec［25］進(jìn)行編譯用以保留網(wǎng)絡(luò)的結(jié)構(gòu)信息，將節(jié)點映射到嵌入空間，為節(jié)點做One-hot［26］編碼，然后用One-hot編碼乘以嵌入矩陣，得到每個節(jié)點的節(jié)點嵌入向量（Node Embedding Vector）.

（4） 度中心性.節(jié)點的度是網(wǎng)絡(luò)局部屬性中使用最廣泛的一種方法，節(jié)點i的度ki為與該節(jié)點直接相連的鄰居節(jié)點的數(shù)量.

ki=∑Nj=1aij=∑Nj=1aji（6）

節(jié)點的度屬性因計算方便快捷、時間復(fù)雜度低等優(yōu)點使之成為基于網(wǎng)絡(luò)局部屬性中最具有代表性的關(guān)鍵節(jié)點識別算法.它的適用范圍很廣，特別是在網(wǎng)絡(luò)中邊稠密、網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜的情況下，可以快速計算出網(wǎng)絡(luò)中的大度節(jié)點.除此之外，在研究網(wǎng)絡(luò)脆弱性問題中，保護(hù)網(wǎng)絡(luò)中的大度節(jié)點對維護(hù)網(wǎng)絡(luò)魯棒性起著至關(guān)重要的作用.

（5） 介數(shù)中心性.節(jié)點的介數(shù)中心性是該節(jié)點在網(wǎng)絡(luò)中進(jìn)行信息傳播時的負(fù)載量.計算出G中任意兩個節(jié)點間的最短路徑，若一個節(jié)點被最短路徑包含的次數(shù)越多，則該節(jié)點i的負(fù)載量越大，該節(jié)點越重要.節(jié)點vi的介數(shù)定義為

BCi=∑i≠s，i≠t，s≠tgis tgs t（7）

其中，gs t代表點s到點t最短路徑的數(shù)目；gis t代表點s到點t的最短路徑里經(jīng)過點i的數(shù)量.介數(shù)中心性考慮到了網(wǎng)絡(luò)的整體結(jié)構(gòu)屬性，因其表示信息在網(wǎng)絡(luò)中傳播時的忙碌程度的特性，在研究網(wǎng)絡(luò)通信問題中使用廣泛.在網(wǎng)絡(luò)中移除介數(shù)大的點可對信息傳播造成巨大影響，介數(shù)中心性的時間復(fù)雜度較高，是基于網(wǎng)絡(luò)全局屬性中經(jīng)典的關(guān)鍵節(jié)點識別算法.

（6） K-shell分解法.節(jié)點的K-shell值是對節(jié)點所處網(wǎng)絡(luò)位置的評分.節(jié)點所處于的位置越貼近網(wǎng)絡(luò)的內(nèi)部，則該節(jié)點的影響力越大.相反，若節(jié)點處于網(wǎng)絡(luò)的邊界位置，則節(jié)點關(guān)鍵程度較小.實現(xiàn)方法是將網(wǎng)絡(luò)中處于最邊緣的節(jié)點逐層刪去，留下的處于網(wǎng)絡(luò)核心位置的節(jié)點作為關(guān)鍵節(jié)點.具體的過程如圖4所示.

K-shell分解法時間復(fù)雜度低，適用于大型網(wǎng)絡(luò)中關(guān)鍵節(jié)點的識別，是基于網(wǎng)絡(luò)位置屬性中常用的關(guān)鍵節(jié)點識別算法.

（7） 緊密中心性.節(jié)點的緊密中心性是用來描述節(jié)點到達(dá)其他節(jié)點的速度快慢，體現(xiàn)了節(jié)點在網(wǎng)絡(luò)中的緊密性，表達(dá)節(jié)點i到達(dá)網(wǎng)絡(luò)中其他節(jié)點的速度快慢.緊密中心性的計算公式如下.

CC（i）=n-1∑j≠idij（8）

di=1n-1∑j≠idij（9）

式中，dij是節(jié)點i和節(jié)點j之間的距離.可以看出，節(jié)點的緊密中心性越大，該節(jié)點距離其他節(jié)點越近，則該點處于網(wǎng)絡(luò)的中心位置.在信息傳播中，接近中心性可以很好地衡量信息的流動性.節(jié)點處于網(wǎng)絡(luò)中心位置具有更好的傳播能力，它的時間復(fù)雜度較高，是基于網(wǎng)絡(luò)全局屬性中常用的關(guān)鍵節(jié)點識別算法.

3.4 基于GCN的關(guān)鍵節(jié)點識別模型

GCN是針對圖的特征提取器，其操作對象是圖數(shù)據(jù)，能夠?qū)D的空間特征進(jìn)行提取.利用這些特征可以實現(xiàn)圖分類、鏈路預(yù)測以及圖嵌入表示等功能.GCN可以分為兩類：（1） 基于空間的GCN方法，它將圖卷積核定義為來自鄰居網(wǎng)絡(luò)的特征信息，迭代地對鄰居信息進(jìn)行聚合，同時考慮了節(jié)點特征和子圖特征;（2） 基于頻譜的GCN方法，它主要涉及信號處理范圍，通過引入濾波器來定義卷積核.

本文選取的是第一類基于空間的GCN方法.本文建立的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別模型的GCN層定義如下.

Hi+1=σAHiWi+bi（10）

其中，A是二度子圖網(wǎng)絡(luò)的對稱歸一化拉普拉斯算子（Laplace Operator）；Hi表示第i個GCN層的節(jié)點；Wi和bi分別是可訓(xùn)練的權(quán)重和偏差參數(shù)；σ是非線性激活函數(shù).我們將其設(shè)置為指數(shù)線性單元（Exponential Linear Unit，ELU）函數(shù)［27］.H0是輸入層中鄰居節(jié)點的特征向量.此外，為了更好地利用節(jié)點功能，我們在GCN層添加了Skip Connection［28］.同時，為了避免過度擬合，應(yīng)用了基于退化學(xué)習(xí)率的Dropout技術(shù).

本方法中節(jié)點的特征提取過程如圖5所示.首先，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)提取出節(jié)點i的二度子圖;然后根據(jù)上文，分別提取出描述網(wǎng)絡(luò)與節(jié)點相關(guān)信息的7個特征;最后，與子圖特征一起拼接成特征向量，作為模型的輸入.

為了加速實驗擬合過程，本文使用最大最小標(biāo)準(zhǔn)化（Min-Max Normalization）方法對特征進(jìn)行歸一化處理，使每個特征值映射到［0，1］之間.

GCN層后是三個全連接層，起到分類作用.通過特征學(xué)習(xí)將網(wǎng)絡(luò)中的節(jié)點進(jìn)行統(tǒng)一評分，得分高的節(jié)點關(guān)鍵程度高，被分為關(guān)鍵節(jié)點.第一個全連接層后使用基于退化學(xué)習(xí)率的Dropout技術(shù)擬合數(shù)據(jù)集.為了避免出現(xiàn)過度擬合的現(xiàn)象，第二和第三個全連接層后使用了指數(shù)化線性單元ELU非飽和激活函數(shù)，用以縮短訓(xùn)練時間并提高準(zhǔn)確度.模型的輸出值是網(wǎng)絡(luò)中每個節(jié)點的關(guān)鍵程度得分情況，本文選取得分前0.1N的節(jié)點為網(wǎng)絡(luò)中的關(guān)鍵節(jié)點.

4 實驗評估

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

本文所用的實驗數(shù)據(jù)均為公開數(shù)據(jù)集.這些數(shù)據(jù)是來自不同領(lǐng)域的真實網(wǎng)絡(luò)，網(wǎng)絡(luò)規(guī)模與網(wǎng)絡(luò)類型多樣化［27］.包括： （1） Zebra是一個動物網(wǎng)絡(luò);（2） Email是西班牙羅維拉維爾吉利大學(xué)的電子郵件通信網(wǎng)絡(luò);（3） C.elegans是秀麗隱桿線蟲的神經(jīng)網(wǎng)絡(luò);（4） NS-GC是從事NS42的科學(xué)家合作網(wǎng)絡(luò);（5） Erdos是一個科學(xué)合作網(wǎng)絡(luò)，其中節(jié)點和鏈接代表個人和科學(xué)合作;（6） BA網(wǎng)絡(luò)是無標(biāo)度網(wǎng)絡(luò);（7） Air traffic control是美國航空運輸網(wǎng)絡(luò);（8） Friendship是一個包含網(wǎng)站Hamsterster的用戶之間友誼的網(wǎng)絡(luò).所有網(wǎng)絡(luò)的詳細(xì)參數(shù)如表1所示.

表1中，N表示的是網(wǎng)絡(luò)的節(jié)點數(shù)目；E表示的是網(wǎng)絡(luò)的連邊數(shù)目；〈k〉表示網(wǎng)絡(luò)的平均度〈k〉=1N∑Niki； 〈L〉表示平均路徑長度；〈c〉表示網(wǎng)絡(luò)的平均聚類系數(shù).

〈c〉=1n∑ni=12IiΓiΓi-1′ （11）

其中，Ii表示節(jié)點i的直接鄰居之間的邊數(shù).

本文采用流行病傳播模型與牽制控制兩種評估方式對實驗結(jié)果進(jìn)行評價.對比的五種算法有：節(jié)點度（D）、介數(shù)中心性算法（BC）、接近中心性算法（CC）、H-度中心性算法（H-index）和K-殼分解算法（K-shell）.

4.2 流行病傳播實驗

評價關(guān)鍵節(jié)點識別方法的準(zhǔn)確性時，采用較為廣泛的方法是基于傳播動力學(xué)中的SIR傳播實驗.在SIR仿真實驗中，網(wǎng)絡(luò)中的節(jié)點具有三個狀態(tài)，分別是易染態(tài)S（能夠被處于感染態(tài)的鄰節(jié)點感染）、感染態(tài)I（感染態(tài)的節(jié)點在固定時間后會變?yōu)槊庖邞B(tài)）以及免疫態(tài)R（免疫態(tài)的節(jié)點穩(wěn)定，不會被其他狀態(tài)感染）.其中處于易染態(tài)S的節(jié)點會在每個時間步長t內(nèi)以概率β被處于感染態(tài)I的節(jié)點所感染，也變?yōu)楦腥緫B(tài)I.隨后，處于感染態(tài)I的節(jié)點會以固定速率γ變?yōu)槊庖邞B(tài)R.SIR模型從傳播速度與傳播范圍兩方面對節(jié)點關(guān)鍵程度進(jìn)行考察.本文選擇排序索引中的前0.1N個節(jié)點作為初始感染源，時間步長為t，對其他節(jié)點進(jìn)行感染.按某一時間步t的累計感染節(jié)點數(shù)量作為最終的傳播范圍，通過比較t時刻累計感染節(jié)點數(shù)量來衡量初始感染源的重要程度.被感染的節(jié)點越多，表明選取的初始感染源節(jié)點的傳播能力越強(qiáng)，關(guān)鍵程度越大.

本文選取擴(kuò)散閾值β = βc和γ=1對每個網(wǎng)絡(luò)進(jìn)行SIR實驗，感染源為每種關(guān)鍵節(jié)點識別方法排序索引的前0.1N個節(jié)點.

βc=〈k〉〈k2〉-〈k〉（12）

其中，〈k〉是網(wǎng)絡(luò)的平均度數(shù)；〈k2〉是平均平方度數(shù).

圖6是在時間步長t=1，t=2，…，t=10、擴(kuò)散閾值β=βc、 γ=1的情況下，五類關(guān)鍵節(jié)點識別方法與本方法感染的關(guān)鍵節(jié)點數(shù)量.橫坐標(biāo)為時間步長t，縱坐標(biāo)為感染的節(jié)點數(shù)量，由于實驗存在隨機(jī)性，以下為500次獨立運行SIR模型的結(jié)果.

由圖6可以看出，在8個網(wǎng)絡(luò)中，將本文方法求得的節(jié)點作為感染源在SIR模型中的感染規(guī)模均大于其他5種關(guān)鍵節(jié)點識別方法.特別是在Friendship網(wǎng)絡(luò)中，在擴(kuò)散閾值β取0.08的條件下，使用本方法時每個時間步長t時的感染規(guī)模都遠(yuǎn)遠(yuǎn)高于其他五種方法.在t=10時網(wǎng)絡(luò)趨于穩(wěn)定狀態(tài)，使用本文方法網(wǎng)絡(luò)的平均感染規(guī)模為727.95，另外五種對比方法中最大平均感染規(guī)模為470.48.在NS-GC網(wǎng)絡(luò)和C.elegans網(wǎng)絡(luò)以及Air traffic-control網(wǎng)絡(luò)中，本文方法在每一個時間步長t時的感染規(guī)模都高于其他方法;在Email網(wǎng)絡(luò)中，雖然前5個時間步長內(nèi)本文方法略低于K-shell方法，但是當(dāng)SIR仿真模型在網(wǎng)絡(luò)中感染的節(jié)點最終達(dá)到平衡時，本文方法的感染規(guī)模為323.03，K-Shell方法的平均感染規(guī)模為312.42，低于本文中的方法.

圖7是進(jìn)行SIR仿真實驗中部分網(wǎng)絡(luò)在每個時間步長t時網(wǎng)絡(luò)的感染詳情.橫坐標(biāo)為時間步長t，縱坐標(biāo)為幾類關(guān)鍵節(jié)點識別方法，顏色越深代表感染節(jié)點數(shù)越多，識別出的關(guān)鍵節(jié)點越準(zhǔn)確.

由圖7可以看出，在SIR模型中本文方法的感染速率與感染規(guī)模均明顯優(yōu)于其他方法.綜上所述，在傳播動力學(xué)SIR模型中，本文方法識別出的關(guān)鍵節(jié)點在傳播速度與傳播范圍兩個方面均高于其他方法.使用本文提出的基于GCN的關(guān)鍵節(jié)點識別方法比傳統(tǒng)方法更具有優(yōu)勢.

4.3 牽制控制實驗

現(xiàn)實中網(wǎng)絡(luò)規(guī)模龐大且結(jié)構(gòu)復(fù)雜，因此想要實現(xiàn)對網(wǎng)絡(luò)的完全控制需要耗費大量成本.在現(xiàn)實場景中，為了節(jié)約控制網(wǎng)絡(luò)過程中使用的資源成本，通常會對網(wǎng)絡(luò)中的少量節(jié)點施加控制使目標(biāo)網(wǎng)絡(luò)在有限時間達(dá)到相應(yīng)狀態(tài)，這個過程被稱為網(wǎng)絡(luò)的牽制控制.在牽制控制實驗中，根據(jù)節(jié)點索引逐個固定節(jié)點，并量化網(wǎng)絡(luò)的可同步性.通過測量在同步過程中控制節(jié)點所產(chǎn)生的影響來評估節(jié)點的關(guān)鍵程度.

復(fù)雜網(wǎng)絡(luò)G由N個節(jié)點構(gòu)成，它們之間相互作用的動力學(xué)公式為

x˙i=fxi+σ∑Nj=1lijΓxj+Uixi，…，xN（13）

其中，向量xi∈Rn是節(jié)點i的狀態(tài)；函數(shù)f（·）描述節(jié)點的自動力學(xué)；正常數(shù)σ表示耦合強(qiáng)度；內(nèi)耦合矩陣Γ：Rn→Rn是半正定的；Ui（xi，…，xN）是施加在節(jié)點i上的控制器.網(wǎng)絡(luò)G的拉普拉斯矩陣的定義如下：L=lijN×N，如果（i，j）∈E，則lij=-1；如果（i，j）E and i≠j，則lij=0；如果i=j，則lii=-∑j≠1lij.

假設(shè)網(wǎng)絡(luò)在時間為t時的目標(biāo)狀態(tài)s（t）滿足：s˙（t）=f（s（t）），s（0）=s0，牽制控制實驗的目的就是通過控制網(wǎng)絡(luò)中的部分節(jié)點使網(wǎng)絡(luò)狀態(tài)趨近于目標(biāo)狀態(tài)s（t）.此時網(wǎng)絡(luò)的真實狀態(tài)與目標(biāo)狀態(tài)中存在的誤差為：ei=xi（t）-s（t）.

若對網(wǎng)絡(luò)中前l(fā)個節(jié)點施加控制，控制器Ui（xi，…，xN）的定義如下式.

Ui=-diΓei，di=hieTiΓei，1≤i≤lUi=0，l+1≤i≤N（14）

其中，hi是一個任意的正常數(shù).

在這里，提出了一個度量P，名為牽制效率，以表征受牽制控制的索引的性能.

P=1Qmax∑QmaxQ=11μ1L-Q（15）

其中，Qmax表示固定節(jié)點的最大數(shù)量；L-Q是主子矩陣，通過從原始拉普拉斯矩陣L中刪除對應(yīng)于Q個固定節(jié)點的Q個行和列而獲得；μ1L-Q是L-Q的最小非零特征值.

P隨著固定節(jié)點數(shù)量的增加而衰減.P值越小，衰減越快.更快的衰減對應(yīng)于更好的性能.本文將Qmax設(shè)置為每種關(guān)鍵節(jié)點識別方法排序索引的前0.05N～0.1N個節(jié)點.

表2和表3是數(shù)據(jù)集中的5個網(wǎng)絡(luò)在Qmax設(shè)置為0.05N和0.1N兩種情況下，不同方法下的牽制效率P.其中加粗?jǐn)?shù)據(jù)為表現(xiàn)最佳的牽制效率.

由表2和表3可知，選取前0.05N個節(jié)點與前0.1N個節(jié)點的實驗結(jié)果相似，本文方法總體占據(jù)優(yōu)勢.從牽制效率P的性能考慮，在36組實驗中本方法有34次表現(xiàn)為最佳的牽制效率.剩余2次實驗為Email網(wǎng)絡(luò)的實驗，本方法的性能略低于K-Shell方法，排名第二.但是與BC、D、H-index、CC等四類方法的結(jié)果相比明顯具備更快的衰減率和更高的性能.綜上所述，本方法識別出的節(jié)點對網(wǎng)絡(luò)控制產(chǎn)生的影響更大，節(jié)點關(guān)鍵程度更高.

5 結(jié) 論

復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點識別研究取得了一定進(jìn)展，但仍存在著方法適用范圍局限、識別準(zhǔn)確率低等缺陷.本研究根據(jù)上述缺陷提出了基于GCN的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法，優(yōu)勢如下：（1） 考慮全面.使用深度學(xué)習(xí)的方法對網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點屬性、鄰居節(jié)點間結(jié)構(gòu)進(jìn)行融合分析. （2） 算法適用范圍廣.在不同類型的真實網(wǎng)絡(luò)中實驗結(jié)果良好.（3） 識別準(zhǔn)確率高. SIR實驗證明本方法確定的關(guān)鍵節(jié)點在復(fù)雜網(wǎng)絡(luò)中的傳播速度與傳播范圍兩方面均優(yōu)于其它方法;牽制控制實驗證明本方法確定的關(guān)鍵節(jié)點對網(wǎng)絡(luò)控制產(chǎn)生的影響更大.綜上所述，本研究提出的方法與其他方法相比更具優(yōu)勢.

參考文獻(xiàn)：

［1］ Ju Y， Zhang S， Ding N， et al. Complex network clustering by a multi-objective evolutionary algorithm based on decomposition and membrane structure ［J］. Sci Rep： UK， 2016， 6： 1.

［2］ 韓忠明， 吳楊， 譚旭升， 等. 面向結(jié)構(gòu)洞的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點排序［J］. 物理學(xué)報， 2015， 64： 058902.

［3］ Malliaros F D， Rossi M E G， Vazirgiannis M. Locating influential nodes in complex networks ［J］.Sci Rep： UK， 2016， 6： 19307.

［4］ De Domenico M， Solé-Ribalta A， Omodei E， et al. Ranking in interconnected multilayer networks reveals versatile nodes ［J］. Nat Commun， 2015， 6： 1.

［5］ 任曉龍， 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點排序方法綜述［J］. 科學(xué)通報， 2014， 59： 1175.

［6］ 韓忠明， 陳炎， 李夢琪， 等. 一種有效的基于三角結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)節(jié)點影響力度量模型［J］. 物理學(xué)報， 2016， 65： 168901.

［7］ Bellingeri M， Bevacqua D， Scotognella F， et al. A comparative analysis of link removal strategies in real complex weighted networks［J］. Sci Rep： Uk， 2020， 10： 1.

［8］ Zhu C， Wang X， Zhu L. A novel method of evaluating key nodes in complex networks ［J］. Chaos Soliton Fract， 2017， 96： 43.

［9］ 朱軍芳， 陳端兵， 周濤， 等. 網(wǎng)絡(luò)科學(xué)中相對重要節(jié)點挖掘方法綜述［J］. 電子科技大學(xué)學(xué)報， 2019， 48： 595.

［10］ Lü L， Chen D， Ren X L， et al. Vital nodes identification in complex networks［J］. Phys Rep， 2016， 650： 1.

［11］ Chiang W L， Liu X， Si S， et al. Cluster-gcn： An efficient algorithm for training deep and large graph convolutional networks［C］//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Alaska：ACM， 2019： 257-266.

［12］ Fan T， Lü L， Shi D， et al. Characterizing cycle structure in complex networks［J］. Commun Phys： UK， 2021， 4： 1.

［13］ 趙之瀅， 于海， 朱志良， 等. 基于網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的節(jié)點傳播影響力分析［J］. 計算機(jī)學(xué)報， 2014， 37： 753.

［14］ 梁世嬌， 柴爭義. 基于多目標(biāo)自適應(yīng)Memetic算法的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測［J］. 江蘇大學(xué)學(xué)報： 自然科學(xué)版， 2020， 41： 262.

［15］ 張淼，梁延研，黃相杰.基于集成學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測及其形成機(jī)制分析［J］.重慶郵電大學(xué)學(xué)報： 自然科學(xué)版， 2020， 32： 759.

［16］ Cavallari S， Zheng V W， Cai H， et al. Learning community embedding with community detection and node embedding on graphs［C］// Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. Singapore. ［S.l.］： ACM， 2017： 377.

［17］ 潘侃， 尹春林， 王磊， 等. 基于特征工程的重要節(jié)點挖掘方法［J］. 電子科技大學(xué)學(xué)報， 2021， 50： 930.

［18］ Zhong L， Gao C， Zhang Z， et al. Identifying influential nodes in complex networks： A multiple attributes fusion method［C］// Proceedings of the Inte-rnational conference on active media technology. Warsaw， Polan： Springer， 2014： 11.

［19］ Kang W， Tang G， Sun Y， et al. Identifying influential nodes in complex network based on weighted semi-local centrality［C］// Proceedings of the 2016 2nd IEEE International Conference on Computer and Communications （ICCC）. Chengdu： IEEE， 2016： 2467.

［20］ Samadi N， Bouyer A. Identifying influential spreaders based on edge ratio and neighborhood diversity measures in complex networks［J］. Comb Probab Comput， 2019， 101： 1147.

［21］ Vernize G， Guedes A L P， Albini L C P. Malicious nodes identification for complex network based on local views ［J］. Comput J， 2015， 58： 2476.

［22］ 喻依， 甘若迅， 樊鎖海， 等. 基于 PageRank 算法和 HITS 算法的期刊評價研究［J］. 計算機(jī)科學(xué)， 2014（Z6）： 110.

［23］ 王名揚， 賈沖沖， 楊東輝. 基于三度影響力的社交好友推薦機(jī)制［J］. 計算機(jī)應(yīng)用， 2015， 35： 1984.

［24］ Ribeiro L F R， Saverese P H P， Figueiredo D R. struc2vec： learning node representations from structural identity［C］//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2017： 385.

［25］ Buckman J， Roy A， Raffel C， et al. Thermometer encoding： One hot way to resist adversarial examples ［C］//International Conference on Learning Representations. Vancouver： ICLR， 2018.

［26］ Clevert D A， Unterthiner T， Hochreiter S. Fast and accurate deep network learning by expon-ential linear units （elus）［ EB/OL］.（2015-11-23）［2022-08-22］.https：//doi.org/10.48550/arXiv.1511.07289.

［27］ Bae W， Yoo J， Chul Y J. Beyond deep residual learning for image restoration： Persistent homology-guided manifold simplification ［C］// Proceedings of the IEEE Conference on Computer Vision and Pattern recognition Workshops. Honolulu： CVPRW， 2017.

［28］ Rossi R， Ahmed N. The network data repository with interactive graph analytics and visualization［C］//Twenty-ninth AAAIConferen-ce on Artificial Intelligence.Austin： AAAI Press， 2014： 753.

引用本文格式：

中 文： 楊洋， 王俊峰. 基于GCN的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別研究［J］. 四川大學(xué)學(xué)報： 自然科學(xué)版， 2023， 60： 032002.

英 文：? Yang Y， Wang J F. Research on key node identification of complex network based on GCN ［J］. J Sichuan Univ： Nat Sci Ed， 2023， 60： 032002.