融合深度學習模型的時序網絡重要節點識別方法研究

黃 娟，郭 強，劉建國

（1.上海理工大學 管理學院，上海 200093；2.上海財經大學 金融科技研究院，上海 200433）

0 引言

相比于傳統靜態網絡，時序網絡不僅能夠表示節點間的關系，還能通過節點或連邊的增加或減少表現拓撲結構隨時間變化情況，近年來被廣泛應用于建模解決金融、醫療、交通、電子商務等領域問題［1］。關鍵節點是整個網絡中處于核心位置的節點，對整個網絡的結構和功能具有較大影響力。在時序網絡中，識別關鍵節點能夠更精準地刻畫事物間的交互關系及發展進程，如建模復雜社交系統、刻畫經濟網絡、建立合作網絡、預測重要樞紐以防止交通堵塞、預測關鍵患者以防止病毒傳播、識別核心客戶、預測流行產品等［2-5］。因此，研究并設計有效的關鍵節點識別方法具有重要的理論與實踐意義。

近年來，時序網絡中關鍵節點的識別方法大致可分為3類：基于拓撲結構的識別方法、基于動力學的識別方法，以及基于機器學習的識別方法［1］。其中，經典的時序網絡關鍵節點識別研究工作主要思路在于根據時序數據構建時序網絡模型，通過網絡的拓撲結構或動力學特征，采用節點排序算法識別網絡中的關鍵節點?；谕負浣Y構的識別方法僅考慮時序網絡每個層內的連接關系，為更好地表示時序網絡的時序特征，還需要考慮不同時間層間的連接關系［6-7］。如Taylor 等［8］在傳統動力學方法的基礎上，采用多層耦合網絡分析方法，將時序網絡按照層間關系和層內關系建立超鄰接矩陣（Supra-Adjacency Matrix，SAM），然后根據特征向量的中心性得到節點重要性排名；楊劍楠等［6］在SAM 方法的基礎上，通過鄰居拓撲重疊系數構建新的超鄰接矩陣（Super Supra-Adjacency Matrix，SSAM）。以上學者的研究結果表明，對層間關系的建模能更準確地預測節點的重要性排序。此外，機器學習結合復雜網絡的研究也得到學者們的廣泛關注，如林國強等［9］將復雜網絡分析數據作為特征輸入機器學習模型，用支持向量機方法預測P2P行業的用戶違約情況；Fang 等［10］以時間T 為界限，以在此之前的數據作為訓練數據，剩余數據作為測試數據，并以社會網絡理論為依據選取相關特征，采用決策樹模型訓練并預測社會網絡中最有力的說服者。以上學者成功將時序信息引入到機器學習方法中，從而為后續相關研究提供參考。

綜上可以看出，近年來基于動力學的研究主要在于充分運用時序網絡中的層間信息輔助關鍵節點識別?；跈C器學習方法的識別研究工作嘗試更好地將時序信息引入到模型中，但這些方法僅從單一角度進行分析，每種方法往往都優缺點并存，加上時序網絡中不同時間段的數據特征并非完全一致，很難突破現有瓶頸以及獲得更高的準確率。因此，本文結合上述兩種分析角度，提出一種基于深度學習的混合預測模型，使得兩種方法在有效發揮優勢的同時，優缺點也可以實現互補。首先，深度學習模型和SSAM 方法分別獨立地預測節點重要性排序，然后通過訓練一個線性模型對兩種方法得出的結果進行加權處理，從而確定最終的節點排序。

1 相關研究

1.1 SSAM 識別方法

時序網絡可按照一定時間間隔被切分為T個時間窗口，則其可被分為有序的時間層網絡G1,G2,G3,…GT。時序網絡可被超鄰接矩陣建模表示，SSAM 方法采用一個NT×NT的分塊矩陣建模時序網絡。具體形式如下：

其中，A(1),A(2),A(3),…,A(T)均為N×N的鄰接矩陣，用于表示各網絡層的層內連接關系，C(1,2),C(2,3),…,C(t-1,t)均為由鄰居拓撲重疊系數組成的N×N對角矩陣，用于表示各網絡時間層之間的層間連接關系。其定義為：

之后，SSAM 方法針對上文中的超鄰接矩陣A'計算主特征向量v={v1,v2,…,vNT}，其中wit=vN(t-1)+i即為時間網絡層Gt中節點i的特征向量中心性，其作為節點重要性排序的衡量指標，可得出每個時間網絡層上的節點重要性排序［6］。

1.2 長短期記憶神經網絡

長短期記憶神經網絡（Long Short-Term Memory Neural Network，LSTM）是循環神經網絡的一個變種，其在基礎循環神經網絡單元基礎上增加了記憶和遺忘單元，使之能更有效地處理與預測較長的時間序列數據［11-12］。LSTM 通過門控制結構調控先前與當前時間單元的信息，輸入門it、遺忘門ft和輸出門ot將短期記憶與長期記憶結合起來，使循環神經網絡具備長期記憶能力［10］。LSTM 工作流程可表示為：

（1）遺忘門ft對信息進行過濾，通過Sigmoid(σ)函數使有用信息的值接近1；反之，無用信息的值接近0。

（2）輸入門根據當前輸入信息和遺忘門的結果更新狀態信息：

輸入信息：

記憶細胞：

長期記憶細胞：

（3）輸出門輸出信息：

其中，σ代表Sigmoid函數，W、b分別代表各個門單元中的權重和偏置，ht-1、ht分別為前序和當前時間單元的輸出信息，xt為當前時間單元的輸入信息?；谘h神經網絡結構的LSTM 能有效利用前序時間單元上的信息，已被廣泛應用于時序數據預測任務，因此本文采用LSTM 模型結構對時序網絡數據進行處理與預測。

2 基于深度學習的混合預測模型

2.1 混合模型結構

本文從模型融合角度出發，結合SSAM 方法與LSTM 模型優勢，使二者的優劣勢互補，從而提高時序網絡中節點重要性排序的預測準確率。本文提出的混合模型可分為3部分：SSAM 模型、LSTM 模型和線性加權模型。

在第1 部分中，本文在SSAM 模型部分主要參考并復現楊劍楠等［6］的研究工作，首先通過超鄰接矩陣建模時序網絡，之后根據節點的特征向量中心性得出每個時間層網絡上的節點重要性排序。

第2 部分為基于LSTM 的時序預測模型，由循環神經網絡LSTM 與一個全連接網絡層（Fully Connected Layer）組成。首先，LSTM 方法根據先前與當前信息輸出節點的向量化表示；其次，將這些向量作為特征輸入分類器，分類器根據節點特征將其分類為對應排序區間。

以上兩部分在混合模型中可并行化地執行，其結果互不干擾，兩者分別獨立預測節點在每個時間層網絡上的排序，但往往由于數據特征以及方法本身的限制，單一方法難以取得更好的預測效果。因此，本文在混合模型的第3部分采用融合的方式，使用一個線性模型加權兩種方法得出節點排序，最終的排序結果無需人為干涉，線性模型能夠自動學習不同時間層上的加權權重。圖1 描述了混合模型基本組織架構。

Fig.1 Basic architecture of hybrid model integrating deep learning model圖1 融合深度學習模型的混合模型基本組織架構

混合模型的基本訓練流程如下：

算法：模型訓練流程描述

2.2 模型訓練策略

為了驗證模型預測的準確率及參數設置的合理性，并避免因數據隨機切分等帶來的干擾，本文在模型訓練與驗證過程中采用K折交叉驗證法，即將數據劃分為K份，訓練總共進行K輪次，每次使用其中1 份用于驗證模型效果，剩余K-1 份用于訓練模型，并以K次實驗結果的均值作為最終結論。根據時序網絡數據特征，本文分別按照基于時間與基于節點的切分方式劃分數據集，用于適應不同的數據集及進行實驗對比。則上述兩種數據切分方法可被描述為：

（1）基于時間的數據切分。時序網絡按照時間窗口劃分。假設時間總周期為10，K值取5，則每輪次訓練時選取連續的2 個時間窗口作為驗證數據，剩余8 個連續時間窗口作為訓練數據。

（2）基于節點的數據切分。時序網絡首先按照時間窗口劃分，之后訓練和驗證數據再按照節點劃分。假設K值取5，則每輪次訓練時選取20%的節點作為驗證數據，其余80%的節點作為訓練數據。

3 實驗及結果分析

3.1 數據描述

本文使用Workspace 數據集進行模型訓練與測試，該數據集包括法國某公司通過移動射頻技術采集的員工之間面對面交互產生的交互數據，持續時間為2013 年6 月24日-2013 年7 月3 日，并按照天為單位進行切分。表1 描述了該數據集的基本統計特征，其中N為網絡中的節點總數，C為總交互次數，E為連邊數目，T為時間窗口數量。

Table 1 Workspace dataset statistics description表1 Workspace 數據集統計描述

3.2 標簽及評價指標

節點在網絡中的重要性排序可根據刪除該節點前后網絡的連通性變化進行度量，如果節點刪除后網絡的連通性變化較大，則證明被刪除的節點對于網絡較為關鍵，反之則重要性較低［1，6-7］。網絡的連通性可由網絡的時序全局效率來表示，其定義形式如下：

其中，N為網絡中的節點數量，dij表示網絡中各節點間的時序距離。定義eit為時間層網絡Gt在刪除了節點i 之后的時序全局效率，則該節點的重要性排序依據可表示為：

Eit值越大，則該節點在網絡Gt中的排序越靠前。本文將通過節點刪除法得到的節點重要性排序作為模型訓練中的標簽值。此外，為降低分類模型的復雜度，本文將節點排名作近似處理，如將12、18 分別轉變為10 和20，該處理方式使得模型由92 分類問題降為10 分類問題。

為了檢驗實驗得出的節點重要性排序效果，本文采用肯德爾系數（Kendall's τ）作為評價指標。Kendall's τ是度量兩個有序序列之間相關程度的常用方法，其取值范圍為[-1,1]。該值越大，證明兩個序列相關性越強。兩個序列越相似，當其數值大于0 時，可作為關鍵節點的識別準確率［6-8］。對于序列{a1,a2,…,an} 和序列{b1,b2,…,bn}，Kendall'sτ可定義為：

3.3 實驗結果比較

為了使LSTM 方法能夠更好地在當前時間層網絡表示節點屬性，本文參考網絡拓撲結構中的主要特性，采用Pearson 相關系數過濾法過濾掉與節點排名相關性過低的特征（絕對值小于0.2）。將所選取的特征作為輸入，通過LSTM 方法構建每個節點的向量化表示。

最終，本文按照上述特征選取方法選取如下節點拓撲屬性作為輸入特征：節點入度、節點出度、節點度、接近中心性、介數中心性、特征向量中心性以及連邊介數中心性共7 個特征。所選取的特征間的相關性如圖2 所示（彩圖掃OSID 碼可見，下同）。

由圖中可以看出，節點度數、接近中心性及介數中心性3 個拓撲特征與節點重要性排名有較高相關度，說明這些特征將在預測中起關鍵作用。以上特征數值高的節點，在排序中的位置相對更加靠前，在網絡中也相對更為重要。

本文在SSAM 方法部分參考楊劍楠等［6］研究工作中的實驗設置。在LSTM 方法模塊通過調節LSTM 中的隱藏層數目（L）、大?。℉）以及訓練迭代輪數（M）尋找最佳的模型設置。在線性加權部分通過不同線性模型對比預測效果。本文首先固定LSTM 中的超參數L、H、M分別為8、1、10，采用線性回歸模型作加權處理，交叉驗證中的K值取5。表2為不同訓練策略的實驗結果比較。

Fig.2 Correlation comparison of each feature and node ranking圖2 各特征及節點排名相關性比較

Table 2 Comparison of experimental results of different training strategies表2 不同訓練策略實驗結果比較

其中，τmean、τstd分別表示10 個時間網絡層上對應方法得到的節點重要性排序，以及采用節點刪除法得到節點排序的Kendall's τ均值和標準差。根據實驗結果對比，基于時間窗口的切分方法訓練結果優于單獨使用SSAM 方法以及基于網絡節點的切分方法。基于節點的切分方法沒有取得較好效果的原因在于，在本文使用的Workspace 數據集中，當20%的節點被用于驗證模型時，一部分重要節點在訓練中可能沒有被充分利用，導致LSTM 方法未能學習到足夠有價值的信息。

本文通過實驗不同的超參數組合尋找模型的最佳性能。本文主要調節的超參數有隱藏層數目、隱藏層大小、迭代輪數及回歸模型等，其中優化器采用Adam 優化算法，最大迭代輪數均為10 輪，實驗結果如表3 所示。其中，LR表示線性回歸模型（Linear Regression），RT 與XGB 分別表示回歸樹（Regression Tree）和梯度提升樹（XGBoost）。

實驗結果表明，當隱藏層數為1，大小為8，線性模型選擇XGB 時，模型的預測準確率最高，每個時間層網絡上的準確率相對較為穩定。固定加權模型為XBG，在不同的參數設置下，每個時間層網絡上的Kendall's τ值如圖3 所示；固定模型參數設置，選取不同加權模型時各時間層網絡上的Kendall's τ值如圖4 所示。

Table 3 Experimental results of different parameter settings表3 不同參數設置實驗結果

Fig.3 Comparison of model parameter settings and experimental results圖3 模型參數設置實驗結果比較

Fig.4 Comparison of experimental results of different weighting models圖4 不同加權模型選取實驗結果比較

以上結果表明，本文提出融合LSTM 方法的混合模型使時序網絡各時間層上關鍵節點的識別準確率平均值比單一的層間相似度方法提高了1.44%，能更準確地在時序網絡中預測出節點的重要性排序。此外，融合了LSTM 方法的混合模型雖然在時序數據前期（t≤4），由于沒有得到足夠的前序數據用于擬合模型，其識別準確率略低于單一SSAM 方法的結果，但在時序網絡中后期（t≥5），混合模型得到的結果更優。LSTM 模型的加入在一定程度上可以解決SSAM 方法在時序網絡中后期準確率降幅過大的問題。

4 結語

本文基于Workspace 數據集，通過融合深度學習方法與基于層間相似度的SSAM 方法，構建混合模型挖掘時序網絡中的關鍵節點，獲取節點的重要性排序。實驗結果表明，融合深度學習模型的方法預測出的節點重要性排序不僅準確率均值與標準差優于單一的SSAM 方法，而且能夠有效提升SSAM 方法在時間層網絡中靠后序列上的識別準確率。本文通過實驗證明融合深度模型能夠在一定程度上彌補傳統基于層間相似度方法的缺陷，并輔助其提高預測準確率，該實驗結果對時序網絡中重要節點的挖掘與識別研究工作具有積極意義。同時，本文研究還存在一些不足，如特征選取和數據預處理可能會對結果造成一定影響，另外模型的選取、優化及訓練方式的調整都是可以繼續深入探索的方向。未來工作可以考慮融合更復雜的模型，選取更多數據和特征進行挖掘與分析。