圖卷積融合計算時效網絡節點重要性評估分析

周傳華，操禮春，周家億，詹鳳

(1.安徽工業大學 管理科學與工程學院，安徽 馬鞍山 243032；2.中國科學技術大學 計算機科學與技術學院，安徽 合肥230027；3.國家電網江蘇電力營銷服務中心，江蘇 南京 210019；4.馬鞍山學院，安徽 馬鞍山 243100)

時效網絡考慮節點之間交互關聯關系的時間特征屬性，集中分析動態演化條件下網絡的拓撲結構和動力學特征，可以更加準確地解釋社交通訊信息流與人類活動模式關系、電子和生物病毒傳播機制、基因調控激活序列以及腦功能網絡時域特征等[1-4].節點重要性評價方法根據不同視角可分為2類，即分析節點在時間分層網絡結構中的局部重要性和節點在網絡演化過程中的全局綜合重要性.

Taylor等[5]通過多層耦合網絡分析法構建超鄰接矩陣（supra adjacency matrix, SAM）以表征動態時效網絡層內和層間連接關系，定義了時效網絡基于特征向量的中心性度量指標以及節點重要性的評價指標.經典的SAM時效網絡模型利用共享參數調節層間關系，忽略不同節點層間連接關系的差異性.楊劍楠等[6]引入鄰居拓撲重疊系數重新表達節點的層間連接關系，提出基于節點層間相似性的超鄰接矩陣（similarity based supra-adja cency matrix, SSAM）改進的時效網絡表達方法.胡鋼等[7]考慮到跨層網絡間的相容相似度問題，定義網絡層間逼近關系系數，通過信息集結彌補鄰居拓撲重疊系數的不足，提出改進的基于時效網絡層間同構率動態演化的超鄰接矩陣模型（isomorphism rate based supra adjacency matrix, ISAM），給出節點在各時間層的排序結果.Jiang等[8]考慮節點連接信息遞延的非馬爾可夫性特征，提出新的增強相似度指數（enhanced similarity index, ESI）來度量相鄰層和非相鄰層之間的耦合關系，并引入時間衰減因子描述不同時間層內節點間耦合強度，構建出基于衰減的SAM時效網絡模型（attenuation based SAM, ASAM）.

上述方法根據節點在時間層內和層間的連接關系，通過引入和定義相關系數并進行理論推導完善時效網絡動態演化過程的結構表達，提高網絡節點重要性判斷的準確率和有效性.將網絡的結構演化過程分解為系列靜態時間窗的集合，統籌分析層內和層間關聯關系影響因素，量化表達節點在當前時間窗內的時序特征，可以實現各時間窗口節點重要性的測度評價，但也因此存在不同時間窗內節點重要性排序評價結果不一致的情況.

Tang等[9-10]通過時序最短路徑定義時序介數中心性和時序緊密度中心性，描述網絡演化過程中的消息傳遞控制機制，提出時效網絡節點重要性綜合度量方法.Kim等[11]通過跨時間復制節點交互信息表達潛在信息流向，構建基于明顯路徑流的時效網絡模型，提出間隔時間內節點的時序度中心性、時序介數中心性和時序接近中心性指標，將靜態網絡中的度中心性[12]、介數中心性[13]、接近中心性[14]的概念拓展應用到時效網絡中，實現對節點的全局重要性綜合評價.Wang等[15]對時序度中心性概念進一步拓展，通過計算時序度中心性偏差，提出時序度偏差中心性指標.Takaguchi等[16]分析現有中心性方法存在時間間隔難以選取調整和計算效率2大瓶頸，將節點和時間戳的組合視為時序節點單元，聚焦時序路徑的局部結構，提出時序覆蓋中心性（temporal coverage centrality, TCC）和時序邊界覆蓋中心性（temporal boundary coverage centrality, TBCC），揭示節點中心性值分布的非均勻性.Ye等[17]基于k-核分解[18]在靜態網絡節點重要性評價問題中的優異表現，提出基于邊的k-核分解方法并應用于時效網絡，通過計算時間聚合圖上節點與其鄰域節點間連邊的權重和，綜合評價節點重要性.Qu等[19]提出適用于時效網絡的時序信息收集（temporal information gathering, TIG）過程，探究時序結構信息對節點重要性排序結果的影響.梁耀洲等[20]引入基于評分矩陣的聚合理論，通過計算節點在各時間層內的排序得分累加和，實現節點重要性的全局綜合評價.通過對靜態網絡節點中心性度量方法在時效網絡上的改進應用，針對全局視角下的節點重要性綜合評價問題給出初步解決方案，但方案的排序有效性在具體應用場景數據集上缺少更進一步的量化透視和模型的性能仿真驗證.

基于上述問題以及超鄰接矩陣模型建模時效網絡動態演化過程，量化表達節點交互順序和關聯關系，利用圖卷積神經網絡[21-22]（graph convolutional network, GCN）對圖結構數據的處理優勢和參數優化能力捕捉空間依賴，構建基于圖卷積融合計算的時效網絡重要節點辨識模型（identifying critical nodes in temporal networks via SAM and graph convolution, ISGC），聚合節點鄰域結構信息和時序特征，在全局維度上實現對時效網絡節點重要性的綜合評價.

1 定義與理論基礎

1.1 時效網絡符號表達

時效網絡是從時間維度抽象描述個體和個體間相互作用關系的系統表示，將個體或群體單元抽象為節點，單元間的相互作用關系視為連邊，單元間的關聯關系具有隨時間先后變化的時序特征.當網絡結構發生可描述的節點和連邊隨時間增加或減少的系統性變化時，將變化過程稱為時效網絡演化.

通常可以將一個網絡定義為二元組G=(V,E)，所有的網絡節點構成節點集合V={v1,v2,···,vn}，節點間的關聯關系構建邊集合E={e1,e2,···,en}.在時效網絡中，若不考慮節點交互關系發生的時長，則在整個網絡演化期內的邊都可以用三元組(i,j,t)來描述，表示節點i和節點j在t時刻發生一次交互事件，此時整個演化期 (t,t+N)將被劃分為T個時間窗，每個時間窗大小L=N/T，得到時間窗序列 {(t,t+n),(t+n,t+2n),···,(t+(T-1)n,t+N)}和時效網絡的離散網絡切片序列 {G1,G2,···,Gn}；若要考慮時長，則邊集元素可用四元組 (i,j,t,Δt)抽象表示節點i和節點j在t時刻產生交互并持續Δt時長.

1.2 超鄰接矩陣模型

文獻[5]將節點規模為N、層數為T的時效網絡表示為層內連接關系和層間連接關系的耦合，用維度大小為NT×NT的分塊矩陣形式進行描述，提出經典的超鄰接矩陣SAM時效網絡模型：

式中：超鄰接矩陣A為時效網絡模型；A(1),A(2),A(3)···,A(t)分別為切分的T個時間層網絡內節點間的連接關系，依次位于A的對角線上，表示有序的時間層網絡；鄰接矩陣A(t)中的元素用ai,j(t)表示，則ai,j(t)=1為在時間層網絡Gt中節點i與節點j間存在的連接關系，ai,j(t)=0 為無連接關系；ωI為相鄰時間片網絡層間耦合關系；ω為可調參數；I為N×N單位矩陣；因為經典的超鄰接矩陣僅考慮相鄰網絡層節點間的連接關系，所以矩陣其他位置元素均為0.

為了更真實地反映網絡連接變化規律，文獻[6]引入鄰居拓撲重疊系數表達層間連接關系，解決SAM模型無法利用可調參數對網絡層間連接緊密程度變化進行差異化表達的問題.節點i在相鄰時間層的鄰居拓撲重疊系數的代數表達式為

式中：c為節點i在相鄰時間層的鄰居拓撲重疊系數.ai,j(t)、ai,j(t+1)分別為相鄰時間層網絡Gt、Gt+1對 應鄰接矩陣中的元素.若在Gt中節點i與節點j之間存在連接，則ai,j(t)=1，否則ai,j(t)=0 .將ωI替換為C(t,t+1)可得SSAM時效網絡模型矩陣表達式為

1.3 圖卷積神經網絡

卷積神經網絡(convolutional neural network,CNN)[23-24]模型可以利用離散卷積在輸入數據空間定義全局共享的卷積核，通過計算中心像素點、相鄰像素點的加權和構成特征圖，提取局部的空間特征，這只適用于在歐幾里德空間，處理圖像和規則網格等類型的數據.對于普遍表達應用的圖結構數據，每個節點的局部拓撲結構都存在差異，導致其不再滿足平移不變性，無法利用相同尺寸的卷積核執行卷積運算，提取數據拓撲空間特征.Bruna等[25]基于圖譜理論利用卷積定理先對譜空間的特征信號做乘法，再通過傅里葉逆變換將信號轉換到原空間，對譜域上的圖卷積算子進行定義，構建出第一個圖卷積神經網絡，有效克服圖結構數據上不滿足平移不變性的局限性.構造的譜卷積神經網絡并不滿足局部連接特征，并且計算時空復雜度較高.Kipf等[21]利用一階Chebyshev多項式作為卷積核，通過參數化設計，有效實現網絡局部性，同時大大降低算法時空復雜度，提出圖卷積神經網絡的空間方法.

2 模型與方法

2.1 圖卷積融合計算時效網絡重要節點辨識模型

基于圖卷積融合計算的節點重要性評估方法建立在時效網絡數據的時空依賴關系之上.其中，時間依賴關系表示時效網絡中的時序特征表達，空間依賴則表示空間信息提取.將時效網絡節點重要性綜合評價和排序問題分解為節點時序特征表達和空間信息提取2個階段.

在時序特征表達階段中，通過超鄰接矩陣對時效網絡進行動態演化建模，表征節點層內和層間連接的時間依賴關系，并計算節點在不同時間層的時序特征屬性，構造時序特征矩陣作為下一階段的輸入；在空間信息提取階段中，根據時效網絡數據構建靜態聚合網絡，通過鄰接矩陣描述時效網絡的靜態聚合拓撲結構以表征空間依賴，并將經過數據預處理后的節點時序特征作為模塊共同輸入，利用圖卷積提取網絡空間信息和節點特征，輸出節點最終特征序列表示.針對模型訓練過程中存在的梯度消失和節點信息丟失問題，設計添加跳躍連接機制（skip connection, SC）[26]，以提升網絡表征能力.ISGC模型結構如圖1 所示，主要包含3個部分，即輸入層、圖卷積層和輸出層.

圖1 ISGC 模型結構示意圖Fig.1 Structure diagram of ISGC model

2.1.1 輸入層 ISGC模型的輸入數據集都是動態圖數據，將數據按照給定時間間隔劃分時間窗，得到不同時刻的無權圖Gt=(Vt,E) .其 中，Vt為t時刻節點集.輸入層主要任務包括時效網絡超鄰接矩陣模型構建和節點時序特征矩陣構造2部分.

創建空矩陣A用于存儲超鄰接矩陣結構，利用鄰接矩陣(A(1),A(2),···,A(T))分別刻畫離散時間窗圖 (G1,G2,···,GT)中的節點關聯關系，并將鄰接矩陣依次插入空矩陣A的對角線上，構建時效網絡演化建模超鄰接矩陣模型.特征向量中心性[12]能夠綜合表達節點自身及鄰域節點重要性，因此利用特征向量中心性作為節點重要性基本度量指標，即求解超鄰接矩陣A的主特征向量（最大特征值對應的特征向量）m={m1,m2,···,mNT}T.將向量m記作維度為N×T的 特征矩陣則有：

式中：矩陣的第i行第t列元素wi,t為向量m的第N(t-1)+i項元素，表示第t個時間層上節點i的 特征向量中心性.最后基于特征向量中心性矩陣W，構造節點時序特征矩陣作為圖卷積層輸入特征.

2.1.2 圖卷積層 節點的重要性程度不僅取決于節點自身的重要性，同時也由它的鄰域節點決定.如何充分考慮節點鄰域信息是時效網絡節點重要性評估過程中需要解決的一個關鍵問題.針對節點在物理空間呈現出的非歐幾里德式空間位置關系，ISGC模型融合圖卷積張量計算框架，通過在傅里葉域構造濾波器，作用于圖中節點及一階鄰域，轉換聚合鄰域結構信息和時序特征.對聚合后的結果進行非線性變換得到新的節點特征，最終實現節點重要性綜合排序.通過多層疊加可以從更遠的鄰居接收信息，實現節點鄰域信息的有效聚合.圖卷積網絡結構如圖2所示，其中X為節點的時序特征矩陣，zi為節點i對應的矩陣行向量.GCN圖卷積機制如圖3所示，σ (x)為圖卷積層的激活函數，H為隱含層特征矩陣，Y為輸出層特征矩陣.

圖2 譜域圖卷積網絡結構圖Fig.2 Spectral convolutional network structure diagram

圖3 譜域圖卷積算子Fig.3 Spectral graph convolution operator

通過構建2層GCN圖卷積神經網絡模型捕捉網絡空間依賴，聚合鄰域節點時序特征.圖卷積代數表達式為

式中：γ為一個超參數，決定x≤0時的飽和曲線.

2.1.3 輸出層 為了避免不必要的節點特征信息流失，通過學習函數f獲得節點重要性的綜合測度，在特征提取過程中不進行圖池化操作，而是直接采用全連接層輸出圖級別的分值向量記為O：

式中：sn為節點排序輸出分值.在實驗訓練階段中，計算節點對網絡性能的影響力作為重要性基準評價結果.模型輸出目標是節點重要性順序結構接近基準結果，選擇均方誤差（mean squared loss，MSE）作為損失函數最小化兩者之間的誤差.

2.2 基線方法

研究采用“5+1+2”模式，選取5種基于拓撲結構的時效網絡節點重要性度量方法、基于動力學隨機游走的識別方法、基于排名聚合及引力模型的節點綜合重要性度量方法進行性能對比.

2.2.1 時序度中心性[11]節點中心性最直接有效的度量指標就是度中心性，節點度值越大表明節點重要性越強.時序度中心性（temporal degree,TD）將節點度的概念推廣到時間維度，得到時效網絡中心性度量基準指標：

式中：Dt(v) 為 節 點v在 時 間 窗Gt(i≤t＜j)內 的 度值 ，|V|為節點 數量.

2.2.2 時序度中心性偏差值[15]基于時間窗圖模型通過計算各時間窗內的度中心性標準差，時序度中心性偏差值（temporal degree deviation centrality, TDDC）刻畫每個節點的時序度值與均值的偏離程度.偏差值越大，該節點屬于網絡核心關鍵節點的可能性越大.時序度中心性偏差計算為

2.2.3 時序接近中心性[11]接近中心性算法通過計算靜態物理路徑評估節點重要性，（temporal closeness, TC）則通過引入時序最短路徑，拓展應用于時效網絡節點重要性評估，時序接近中心性定義的計算式為

式中：Δt,j(v,u) 為在時間間隔i≤t＜j內節點v與其他節點間的時序距離.

2.2.4 時序介數中心性[11]時序介數中心性（temporal betweeness, TB）通過統計任意兩點間的時序最短路徑數目，計算經過目標節點的最短路徑比例，評估節點重要性程度，具體代數式為

式中：σt,j(s,d) 為 時間間隔內節點s到 節 點d的最短路徑總數，σt,j(s,d,v) 為 通過 節點v的最 短路 徑數量.

2.2.5 時序k-核分解[17]時序k-核分解（temporalkshell decomposition, TK）通過連邊權值計算聚合目標節點和鄰居節點時序k-核特征，實現時效網絡節點重要性度量，聚合權值越大節點越重要.節點時序k-核計算式為

2.2.6 排名聚合[20]基于排名聚合（ranking aggregation, RA）的方法通過制定評分機制，建立各時間窗口內節點的重要性評分矩陣并進行加和計算，根據加和得分獲得節點重要性綜合排序：

式中：g(v,u)為節點v相對于節點u的綜 合得 分，g(v) 為v相對于網絡其他所有節點的最終評分.

2.2.7 時序網頁排名[27]（temporal page rank, TPR） 將時效網絡表示為系列靜態圖集合，基于網絡上的隨機游走策略，結合時序信息和動力學提出適用于時效網絡的時序PageRank方法來評估節點重要性程度：

式中：α為阻尼因子，P r′[z|t]為 特定隨機游走序列發生的概率，z為游走路徑，W為所有游走路徑的集合.

式中：c(z|t)為在時間t之前從節點v出發到達u的游走序列集合，c(z′|t)為所有從節點v出發且與游走z的路徑長度相等的游走數目.

2.2.8 時序引力模型[28]（temporal gravity model,TGM） 假設節點的中心性取決于對鄰居節點的引力大小，必須滿足鄰居節點在結構和時序距離上都接近目標節點.將經典靜態中心性度量指標及時序擴展視為質量，結合節點之間的時序距離，定義時序引力中心性，實現對節點重要性的綜合度量：

式中：T G(i) 為節點i相對于鄰域節點的引力中心性，Mi和Mj分別為節點i和j的屬性值，di,j為節點間的時序距離，R為截斷半徑.

3 仿真與實驗結果分析

3.1 實驗網絡數據

為了驗證ISGC模型在時效網絡節點重要性評價過程中的有效性，選用3個公開實證網絡數據集Workspace[29]、Enrons[30]和SFHH[31]進行實驗.Workspace是一家法國公司通過移動射頻設備獲得的公司員工每天面對面的交互數據，時間是2013-6-24—2013-7-3；Enrons是網絡科學研究領域最常用的實證網絡數據之一，主要包含美國安然公司員工之間的往來郵件數據，時間是1999—2002年，本研究截取其中2001年交互數據子集作為實驗數據，SFHH是2009年法國尼斯會議中與會者之間的交互網絡.數據集的基本統計特征信息描述如表1所示，其中Num為網絡節點規模，Win為切分的時間窗口數量，Inter為節點間的交互次數，Static為聚合靜態網絡節點間的連邊數量，During為數據集時間跨度.

表1 實證網絡數據集的特征描述Tab.1 Empirical network data set feature description

3.2 評價方法

時效網絡中的節點重要性可以從2個方面進行評價：1）從網絡結構性能角度出發，考察節點移除如何影響網絡連通性；2）從網絡功能性角度出發，考察節點對網絡傳播效果的影響[6].通過計算網絡中所有節點之間的距離倒數之和的均值獲得網絡效率[32]，可表示靜態網絡中信息流通的難易程度，并評判網絡連通性.時效網絡通過替換距離變量，定義時序全局效率[5]指標來衡量信息傳播效率，表征網絡時序性能：

式中：e為時序全局效率，di,j為時效網絡中各節點之間的時序距離[10].時序距離指的是時序最短路徑，與靜態網絡中的最短路徑不同的是其需要遵循節點連接發生的時間先后順序.例如信息從節點i經 過節點j到達節點k時，需要在時間維度上滿足節點i和節點j之間先發生有效連接，節點j和 節點k之間后發生有效連接的條件，否則信息無法順利傳達.

為了檢驗ISGC方法對節點重要性的排序效果，研究采用節點刪除法[33]計算節點刪除后時序全局效率與原時序效率的差值Ev，量化表達網絡時序性能波動，驗證節點重要性.刪除節點后網絡性能指標波動幅度越大，說明節點越重要，計算式為

式中：ev和e分別為刪除節點后的時效網絡全局效率和原時效網絡全局效率.通過肯德爾系數[34-35](Kendall’s τ )評估模型輸出序列和時效全局效率差值序列排序的一致性程度.一致性程度越高，則模型輸出序列排序精準度越高.

Kendall’s τ 在用于評估相關序列一致性程度時取值為 - 1～1.0，取值越大表明2序列一致性程度越強；反之，則表明2序列一致性程度越弱.對于2個數值序列和τ值計算式為

3.3 實驗結果分析

針對實證網絡公開數據集，通過本研究ISGC方法和現有方法計算得到網絡節點重要性綜合排序結果，并計算各方法所得排序序列與時序全局效率差值基準序列的Kendall’s τ 值，表征一致性程度，實驗對比結果如表2所示.

由表2 結果可以得出：1）本研究ISGC方法在Workspace和Enrons數據集上所得節點重要性排序序列與基準序列的Kendall’s τ 相關性結果分別為0.7096和0.7644，相較于現有方法綜合性能平均提高16.74%（Workspace）和22.45%（Enrons），說明在數據預處理階段超鄰接矩陣能夠有效構建時序特征輸入，通過圖卷積融合計算機制能夠有效聚合鄰域節點時序特征，最終實現排序量化表達輸出，實現方法有效性和精準性的提升.在SFHH數據集上，ISGC方法排序一致性低于TD和TGM，但是一致性值接近0.7，并且優于其他方法，說明該方法具有相對優勢.2）RA方法在Workspace數據集上表現效果優于TD、TC和TK，而在Enrons數據集上弱于TD和TC，接近TK；TB方法在Workspace數據集上表現優于TC，而在Enrons數據集上弱于TC；TD和TC在實驗數據集上表現效果差異較大，而在TDDC上則是均表現最差.TGM在數據集上均表現優良且優于TPR算法，而在Workspace和Enrons上弱于ISGC方法.ISGC輸出序列與基準序列的排序一致性均高于或接近0.7，由于ISGC相比于現有方法具有反饋機制作用優勢，能夠自適應調整優化模型參數，在不同數據集上都具有良好的應用泛化性和魯棒性.

表2 ISGC和現有方法排序與基準排序的相關性對比結果Tab.2 Correlation comparison results of ISGC and existing methods with the benchmark sort

根據圖4實驗結果可以發現：當層間關系可調參數 ω取值不同時，ISGC模型輸出序列與全局時序效率差值序列排序一致性也會隨之波動.在Workspace數據集上，當 ω=0.2時，一致性比較結果Kendall’s τ呈現谷值；在Enrons數據集上，當 ω=0.8時，出現一致性結果谷值.考慮通過參數 ω對輸入時序特征的優化機制與模型的反饋調優機制聯合作用，尋求最優 ω表達層間連接關系，使得模型序列輸出逼近全局時序效率基準序列，獲得排序一 致性滿意解.

圖4 相鄰層間耦合關系可調參數 ω 對ISGC與基準排序的相關性影響Fig.4 Influence of tunable parameters ω of coupling relation between adjacent layers on correlation between ISGC and benchmark sort

3.4 算法復雜性

TD算法的時間復雜度為O(|V|+|E|)，TK算法和TDDC算法的復雜度均為O(R)，R=j-i.TC算法 復 雜 度 為O(R|V|2) ，TB算 法 復 雜 度 為O(R3|V|3).TPR算法每次交互更新的時間開銷為O(1)以及TGM算法復雜度為O(R|V|2).綜上所述，本研究ISGC算法計算時間復雜度相對較低，有利于在大規模網絡上的泛化應用.

4 結語

針對動態時效網絡演化節點重要性辨識進行系統建模分析，提出基于時效網絡結構超鄰接矩陣和圖卷積神經網絡數值計算系統模型.模型具體應用超鄰接矩陣特征向量中心性指標辨識網絡節點重要性.基于深度學習框架張量，計算節點最終特征序列表示和排序結果，分析評估時序全局效率差值，評價節點對網絡連通性影響力，綜合評測網絡全局節點重要性序結構.實驗結果表明基于圖卷積融合計算的時效網絡節點重要性評估和排序分析是科學有效的.

基于圖卷積融合計算的時效網絡節點重要性評價方法，等間距劃分時間窗，依據節點在相鄰時層的交互關聯關系提取初始時序特征.現實時效網絡受網絡內外環境及其他因素影響，節點重要性結構演變并非按照時間均勻分布，更多表現為非線性、隨機性，下一步研究計劃圍繞柔性時間窗口提取與劃分和跨層交互關聯邏輯演化表征作為核心工作.