基于信息傳播節點集的CTDN 節點分類算法

黃 鑫，李 赟，熊瑾煜

（1.中國人民解放軍戰略支援部隊信息工程大學信息系統工程學院，鄭州 450001；2.盲信號處理國家級重點實驗室，成都 610041）

0 概述

復雜網絡是對現實世界中復雜系統的抽象表示，復雜系統的各組成部分及其相互之間的關聯關系分別用節點和節點之間的邊來表示。對復雜網絡中的節點開展分類問題研究，有利于加深對復雜系統內部組成的理解。傳統網絡節點分類主要針對靜態網絡，即不考慮網絡隨時間發生演變，網絡節點和節點之間的邊始終保持不變。在實際情況中，網絡的動態特征明顯，節點和節點之間的邊可能隨時間發生變化。為使研究更貼近實際情況，在靜態網絡的基礎上充分考慮時間要素，研究人員提出動態網絡概念并進一步開展網絡相關研究。本文基于經典的網絡節點分類方法，在考慮時間要素的前提下，根據連續時間動態網絡（Continuous-Time Dynamic Network，CTDN）的信息傳播特征，結合網絡表示學習方法進行網絡節點分類研究，提出基于信息傳播節點集的連續時間動態網絡節點分類算法CTDNN-IPNS。

1 相關工作

基于網絡表示學習的節點分類方法是研究網絡節點分類問題的一類重要方法［1-3］。這類方法將網絡節點表示為低維空間向量，通過對向量的分類實現節點的分類。結合網絡表示學習方法，在分類過程中根據是否考慮節點或連邊隨時間變化的情況，形成靜態網絡節點分類和動態網絡節點分類方法。

根據網絡表示學習模型的使用情況，靜態網絡節點分類方法［4］大致可分為基于矩陣分解［5-6］、隨機游走［7-8］和深度神經網絡［9-10］三類。基于隨機游走的網絡表示學習方法將隨機游走與自然語言處理領域的Skip-Gram 詞向量生成模型相結合，形成節點采樣+Skip-Gram 的網絡表示學習框架，將網絡節點和通過在網絡節點之間隨機游走采樣獲取的節點序列分別視作自然語言中的詞和語句，對節點序列加以處理后實現網絡節點的向量表示，并利用經典分類算法實現網絡節點的最終分類。DeepWalk［7］算法是經典的基于隨機游走的網絡表示學習算法，具有網絡表示能力強和計算復雜度低的特點。在此基礎上，通過改進節點序列采樣策略，衍生出Node2 Vec［8］、Walklets［11］、Metapath2Vec［12］等 眾多網絡表示學習算法。這類算法針對靜態網絡展開研究，未能對網絡中的時間信息加以利用，即未考慮節點或連邊隨時間的變化情況對網絡表示學習結果的影響，不適用于動態網絡節點分類。

在動態網絡節點分類方面，文獻［13-14］利用LSTM、AutoEncoder 等深度學習模型對網絡快照進行處理，較好地表示出網絡節點類別隨時間的演化過程，但是如果節點在不同的快照中表現出不同的類別，則這類方法不能給出節點的全局類別屬性。文獻［15-17］以改進節點序列采樣策略為突破口，分別設計出基于隨機游走的動態網絡表示學習算法CTDNE、STWalk 和RWR-STNE，其 中，STWalk 和RWR-STNE 算法在靜態網絡的基礎上增加時間要素，在不同時刻網絡快照上構造節點時空圖，進而在其上完成隨機游走并實現節點采樣，但是上述算法存在時間粒度過大、時間信息利用不充分的問題。CTDNE 算法針對連續時間動態網絡，嚴格依照事件發生的時間順序進行節點采樣，但容易受噪聲影響，導致網絡表示學習結果與現實情況存在較大偏差，分類結果精度也會隨之降低。

2 相關定義

定義1（連續時間動態網絡）連續時間動態網絡［15，18-19］表示為 圖G=(V,ET,T)，其 中，V為節點 集，ET?V×V×R+為任意兩個節點間具有時間戳的連邊集，T：ET→R+為邊的時間戳值到正實數集的映射。ei=(u,v,t)?ET表示網絡中的邊，其中，u為源節點，v為目的節點，t為連邊發生的時間戳。在最小時間粒度情況下，每條邊可能具有互不相同的時間戳值。

連續時間動態網絡的定義在傳統靜態網絡的基礎上充分考慮了動態網絡中邊的時序信息，同時克服了以網絡快照形式表示動態網絡過程中時間信息損失的問題。針對連續時間動態網絡進行節點分類的3 個主要步驟如圖1 所示。首先，按照定義1，利用實際數據構造連續時間動態網絡；其次，使用網絡表示學習方法，將連續時間動態網絡中的節點映射至低維空間，采用保有節點原始關系的向量加以表示；最后，利用分類算法，通過對低維空間節點向量的分類，實現連續時間動態網絡的節點分類。鑒于分類算法已經相對成熟，本文將網絡表示學習環節作為研究重點，開展連續時間動態網絡節點分類研究。

圖1 連續時間動態網絡節點分類流程Fig.1 Procedure of node classification for CTDN

定義2（連續時間動態網絡表示學習）在連續時間動態網絡中，學習得到的映射函數f：V→Rd，使得網絡中的節點vi?V被映射為低維向量mi?Rd，其中，d表示向量維度且滿足d<<|V|。

在通常情況下，映射函數f的目標是保留節點在原始網絡結構上的內在相似性和時間上的平滑性。

3 CTDNN-IPNS 算法

在網絡信息傳播動力學研究中，DALEY 等人［20］提出了經典的DK 謠言傳播模型。該模型將網絡內節點分為與謠言傳播無關者、傳播謠言者和知道謠言但不繼續傳播者、謠言通過傳播者之間的直接接觸進行傳播三類。在謠言傳播過程中，節點間因接觸范圍不同，形成謠言傳播群組，群組內因節點傳播能力的不同，會產生不同的傳播模式。

在實際網絡信息傳播過程中，信息通過節點間通聯在不同類型節點之間傳播。因此，在DK 謠言傳播模型的基礎上，本文結合實際通信網絡數據特點及其時間維度屬性，得出連續時間動態網絡具有以下特點：

1）信息傳播流程多數在一定時間內完成，傳播范圍在大小不等的節點集內。

2）信息傳播包括一對一、一對多和多對多等多種模式。

3）類別相同或相似節點之間存在一定的周期性關聯關系。

電話通信網絡是典型的連續時間動態網絡。表1 是某電話通信網絡的部分通話記錄，在時間戳值為316 999 s～317 344 s 的345 s 時間內，其中方括號標注的用戶171、180、186、188 共同完成一次信息傳播，而其他用戶與其沒有任何通聯。圖2 為信息傳播過程示例，其中連邊上的數字表示通聯發生的時間順序。

表1 某電話通信網絡部分通話記錄Table 1 Partial call records of a telephone communication network

圖2 用戶171、180、186 和188 之間的信息傳播過程Fig.2 Information dissemination process among users 171，180，186 and 188

由此可以推測，對于連續時間動態網絡的節點分類，若在網絡表示學習環節的節點序列采樣過程中對上述特征加以利用，其網絡表示學習結果將更好地保留節點在原始網絡結構上的內在相似性，在此基礎上得到的分類結果精度也將大幅提高。具體而言：一是將節點采樣范圍、時間范圍加以限制，提高節點集內成員共現概率；二是增加采樣過程的靈活性，從逐個節點順序采樣轉變為從節點集內成員發起的隨機采樣；三是信息傳播周期性的存在，使得同類節點共現概率會在一定范圍內隨采樣次數的提高而增加。

定義3（信息傳播節點集）給定連續時間動態網絡G，在時間范圍Δt內，在信息I從節點vi傳播至節點vj的過程中，所有參與此次信息傳播的節點記為M={vi,…,vk,…,vj}，vp?V，p?{i,…,k,…,j}，這 些節點共同組成信息I的傳播節點集。

基于上述分析，本文提出針對連續時間動態網絡節點分類的CTDNN-IPNS 算法，該算法基于信息傳播節點集的概念，對網絡表示學習環節的節點序列采樣策略進行改進，形成突顯節點之間關聯關系的節點向量表示，在此基礎上進行類別劃分，最終實現對連續時間動態網絡節點的分類。

3.1 節點序列采樣

節點序列采樣的具體步驟如下：

步驟1構造連續時間動態網絡G=(V,ET,T)，分別初始化信息傳播節點集M、備選邊集Ec和節點采樣序列L為?，設置信息傳播時間范圍Δt、節點序列長度（即隨機游走步長）l及采樣次數（即隨機游走次數）n。

步驟2從G中隨機選擇一條邊作為初始邊，其時間戳t作為本輪采樣的基準時間，而其兩端節點則作為初始節點加入信息傳播節點集M。

步驟3與M中節點相連的所有邊，若其時間戳在時間t±Δt內，則將其置入備選邊集Ec。

步驟4若Ec≠?，則從Ec中隨機選擇一條邊作為下一步采樣的起始邊，之后操作與步驟2 類似，但需合并M中的相同節點，并將新增節點添加至L。

步驟5若Ec=?，則在時間t+Δt內隨機調整基準時間t，重復步驟3～步驟5。

步驟6重復步驟2～步驟5，當|M|≥l或t±Δt超出G的時間范圍時，輸出節點采樣序列L。

步驟7重復步驟2～步驟6 共c次，輸出n個節點序列L1,L2,…,Ln。

算法1CTDNN-IPNS 算法

在算法1 中，輸入參數l控制每次節點序列采樣的最大長度，n表示最終形成的節點序列個數，Δt表示一次信息傳播的時間范圍。

3.2 網絡表示學習

定義4（節點鄰居序列）對于網絡中的節點u，在以采樣策略S進行一次采樣形成的序列中，與其同時被采集到的節點構成節點u的節點鄰居序列［7］，記為NS(v)?V。

基于節點采樣+Skip-Gram 的網絡表示學習框架，可將網絡表示學習問題轉化為使V中所有節點v?V在嵌入結果為f(v)的條件下，節點鄰居序列中的節點共同出現的對數條件概率之和最大的優化問題，計算公式為：

為簡化計算過程進行以下假設：

1）假設不同節點之間的采樣過程相互獨立，則如式（1）所示的條件概率可表示為NS(v)內各節點的條件概率之積，計算公式為：

2）假設同一條邊的兩端節點彼此作用對稱，利用softmax 函數表示式（2）中的條件概率，計算公式為：

基于上述假設，式（1）可簡化為：

由上述公式可知，網絡表示學習的目標函數求解的關鍵為構造Ns(v)，即采樣策略S的設計。利用節點采樣+Skip-Gram 的網絡表示學習框架，通過負采樣方法［21］和Skip-Gram 模型即可求解式（4）描述的目標函數，從而生成網絡節點的d維向量表示，其中d值由人為設定。需要說明的是，若要生成網絡節點d維向量表示，則需從節點序列中截取其子序列作為Skip-Gram模型輸入，而截取考察范圍w同樣由人為設定，該參數表示在截取節點序列的子序列時，針對節點vi截取的節點子序列為{vi-w,…,vi,…,vi+w}。

3.3 節點向量分類

CTDNN-IPNS 算法采 用LogicRegression 分類器對網絡表示學習環節生成的節點向量進行分類，并依據F1_macro 和F1_micro 值量化評價分類結果。F1_macro 和F1_micro 的求解過程為：設數據集中的數據共分為n類，類別集合為C={c1,c2,…,cn}。對于類別ci，i=1,2,…,n，數據分類結果中的正確分類樣本、錯誤分類樣本和非ci類錯誤分類樣本數量可分別表示為TTP、FFP、FFN，則F1_macro 可根據式（5）～式（8）進行求解，反映了分類結果在各個類別中樣本分類的綜合性能，F1_micro 可根據式（9）～式（11）進行求解，反映了分類結果在所有樣本上的綜合分類性能。

4 實驗與結果分析

4.1 實驗數據集與環境

本文選用網絡表示學習研究領域常用的DBLP和AMiner 論文合作數據集，以及根據實際電話通聯記錄自制的Reality-Call 數據集，從連續時間動態網絡的二維可視化展示效果及其節點分類結果兩方面，對CTDNN-IPNS 算法的性能進行實驗驗證，數據集信息如表2 所示。DBLP 和AMiner 數據集中的網絡節點是文章作者，若兩位作者共同發表過論文，則兩者之間存在一條連邊，邊的時間戳為論文發表年份，節點類別是論文作者的所屬研究領域。類似地，Reality-Call 數據集中的用戶號碼被視為網絡節點，若兩位用戶有過通話，則其對應的節點之間存在一條連邊，邊的時間戳為通話發起時間，節點類別為號碼所屬部門。實驗環境設置如表3 所示。

表2 實驗數據集Table 2 Experimental dataset

表3 實驗環境Table 3 Experiment environment

4.2 參數設置

CTDNN-IPNS 算法涉及參數較多，具體設置如下：

1）網絡節點向量表示維度d：可根據實際需要選擇任意維度，在本文實驗中設置為128。

2）隨機游走步長l：選擇大于網絡平均路徑長度的數值，在本文實驗中設置為10。

3）節點子序列截取考查范圍w：在本文實驗環境及數據集條件下設置為5。

4）信息傳播時間范圍Δt：根據網絡信息傳播特點設置該參數。通過對實驗數據集的分析，在論文合作網絡中，作者與其合作對象的合作時間一般約為3 年，在電話通信網絡中，一次信息傳播的時間范圍約為25 min，因此在本文實驗中以3年和25 min設置該參數。

5）訓練數據使用率γ：通常按照3∶1 的比例將數據集劃分為訓練集和測試集，在本文實驗中設置為0.75。

6）總游走次數：由于CTDNN-IPNS 和CTDNE算法采用從隨機選取的節點出發且依據指定規則進行隨機游走的采樣策略，而STWalk 算法采取以網絡快照內的每個節點為起點且依次開始隨機游走的策略，為便于比較，在實驗中將總游走次數設置為網絡節點數的整數倍。

在實驗中以總游走次數為變量開展算法性能測試，其中隨機游走步長l、節點子序列截取考查范圍w和傳播時間范圍Δt的敏感性見下文分析，而網絡節點向量表示維度d和訓練數據使用率γ的取值則采用經驗值。

4.3 CTDNN-IPNS 算法性能測試

為橫向驗證CTDNN-IPNS 算法的性能，基于相同測試數據集，本文將CTDNN-IPNS 算法與STWalk［16］和CTDNE［15］算法進行比較，對比算法采用清華大學發布的OpenNE 框架內的相關函數進行實現。在測試過程中，網絡節點向量表示維度d=128，節點子序列截取考察范圍w=5，隨機游走步長l=10，隨機游走次數n=30 000，訓練數據使用率γ=0.75。

以DBLP 數據集為例，CTDNN-IPNS、STWalk 和CTDNE 算法的動態網絡表示學習結果經t-SNE 算法［22］降維后的二維可視化效果如圖3 所示。可以看出，與STWalk 和CTDNE 算法相比，基于本文提出的節點采樣策略，CTDNN-IPNS 算法生成的動態網絡表示學習結果能夠更好地保持原有網絡節點之間的內在相似性，數據集的6 個類別在二維空間中的分布更集中，數量較少的黑色類別數據的聚集效果也更明顯且各個類別的界限清晰，能夠更好地支持后續節點的分類任務。

圖3 3 種算法的二維可視化效果Fig.3 2D visualized effect of three algorithms

在總游走次數下，CTDNN-IPNS、CTDNE和STWalk算法對不同數據集的分類結果評價指標值（F1_micro和F1_macro）如表4～表6 所示。上述分類結果評價指標值對應的曲線如圖4～圖6 所示。根據上述分類結果的評價指標值可知，針對DBLP、AMiner 和Reality-Call數據集，CTDNN-IPNS 算法整體上優于STWalk 和CTDNE 算法。具體而言，在3 組實驗中，CTDNE 算法分類結果的F1_micro 和F1_macro 值隨節點采樣次數的增加而呈現出上升趨勢，但上升速度較慢。在對DBLP數據集和Aminer數據集進行節點分類時，CTDNN-IPNS算法分類結果的F1_micro 和F1_macro 值均為最高值，且在總游走次數較少時，其優勢更為明顯。在對Reality-Call數據集進行分類時，3 種算法均在總游走次數達到750 以上時獲得較好的分類效果，但CTDNN-IPNS 算法的分類效果更佳，且在總游走次數低于750 時，CTDNN-IPNS 算法具有更好的分類性能，其F1_micro和F1_macro 值更高且增速更快。

圖6 3 種算法對Reality-Call 數據集的分類結果評價曲線Fig.6 The evaluation curves of classification results on the Reality-Call dataset by three algorithms

表4 CTDNN-IPNS、STWalk 和CTDNE 算法對DBLP數據集的分類結果評價指標值Table 4 The evaluation index values of classification results on the DBLP dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

表5 CTDNN-IPNS、STWalk 和CTDNE 算法對AMiner 數據集的分類結果評價指標值Table 5 The evaluation index values of classification results on the AMiner dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

表6 CTDNN-IPNS、STWalk 和CTDNE 算法對Reality-Call 數據集的分類結果評價指標值Table 6 The evaluation index values of classification results on the Reality-Call dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

圖4 3 種算法對DBLP 數據集的分類結果評價曲線Fig.4 The evaluation curves of classification results on the DBLP dataset by three algorithms

圖5 3 種算法對AMiner 數據集的分類結果評價曲線Fig.5 The evaluation curves of classification results on the AMiner dataset by three algorithms

4.4 參數敏感性分析

隨機游走步長l和節點子序列截取考查范圍w及信息傳播時間范圍Δt是CTDNN-IPNS 算法中的重要參數，本節通過在DBLP 數據集上設定其他參數，分別改變l、w和Δt的取值大小來觀察節點分類指標值（F1_micro 和F1_macro）的變化情況，對算法的參數敏感性進行分析。如圖7 所示，隨著l值的增加，F1_micro 和F1_macro 值先快速上升，再逐漸趨于平緩，曲線拐點在l=7 附近，接近于DBLP 數據集的平均路徑長度值，且當l取值大于網絡平均路徑長度時，算法性能趨于平穩。這表明基于信息節點集的隨機游走節點采樣方式，能夠較好地反映出網絡的通聯規律及其內在的結構屬性。在本文實驗中，為便于算法性能比較，將隨機游走步長設定為3 個數據集的網絡平均路徑最大值，故取l=10。在圖8中，隨著w值的增加，F1_micro 和F1_macro 值逐步提高，當w≥5 時逐漸趨于平穩，因此在本文實驗環境及數據集條件下取w=5。

圖7 CTDNN-IPNS 算法分類性能隨參數l 的變化曲線Fig.7 The change curves of classification performance of CTDNN-IPNS algorithm with parameter l

圖8 CTDNN-IPNS 算法分類性能隨參數w 的變化曲線Fig.8 The change curves of classification performance of CTDNN-IPNS algorithm with parameter w

如圖9、圖10 所示，在DBLP 數據集和Reality-Call數據集的節點分類實驗中，當Δt分別取3 年和25 min時，算法分類性能較其他取值有小幅增長，這表明該參數的合理設置將直接影響算法的分類效果。

圖9 CTDNN-IPNS 算法在DBLP 數據集上的分類性能隨參數Δt 的變化曲線Fig.9 The change curves of classification performance of CTDNN-IPNS algorithm on the DBLP dataset with parameter Δt

圖10 CTDNN-IPNS 算法在Reality-Call 數據集上的分類性能隨參數Δt 的變化曲線Fig.10 The change curves of classification performance of CTDNN-IPNS algorithm on the Reality-Call dataset with parameter Δt

4.5 結果分析

實驗結果表明，在隨機游走次數較少時，CTDNE 算法因采用嚴格依照時間先后順序的游走策略，在網絡學習表示過程中受噪聲影響較大，不能較好地捕捉到節點與同類別其他節點之間的關系，隨著游走次數的增加，同類別節點的共現次數逐漸增加，其分類精度也隨之提高。由于STWalk 算法和CTDNN-IPNS 算法在隨機游走過程中，分別以節點歷史鄰居和信息傳播集內節點為采樣對象，因此在隨機游走次數較少時表現出較好的分類性能，隨著游走次數的增加，采集節點數逐漸增多，采樣序列反而可能受到不同類別節點的干擾，導致分類性能略有下降，但總體表現基本平穩。

隨著總游走次數的增加，CTDNE 和CTDNNIPNS 算法的性能曲線逐漸趨同，這表明在總游走次數足夠大的情況下，不同的隨機游走策略最終反映出的圖信息基本趨于一致，且對網絡的整體表示學習能力相近，而STWalk 算法側重于關注單個網絡快照上的節點，因此相比其他算法，整體分類性能相對較差。

5 結束語

本文提出一種新的連續時間動態網絡節點分類算法，定義信息傳播節點集，改進網絡表示學習方法的節點序列采樣策略，利用其生成的節點低維向量和LogicRegression 分類器實現對連續時間動態網絡的節點分類。實驗結果表明，針對論文合作網絡的作者分類和電話通信網絡的用戶分類問題，相比CTDNE 和STWalk 算法，該算法的網絡表示學習結果能夠更好地保留節點在原始網絡結構上的內在相似性，且最終分類結果也更優。后續將結合節點屬性、連邊權重等信息，研究針對連續時間動態網絡的分類算法，進一步提升其分類效果和適用范圍。