基于信息傳播節(jié)點集的CTDN 節(jié)點分類算法

黃 鑫，李 赟，熊瑾煜

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

0 概述

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

1 相關(guān)工作

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

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

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

2 相關(guān)定義

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

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

圖1 連續(xù)時間動態(tài)網(wǎng)絡節(jié)點分類流程Fig.1 Procedure of node classification for CTDN

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

在通常情況下，映射函數(shù)f的目標是保留節(jié)點在原始網(wǎng)絡結(jié)構(gòu)上的內(nèi)在相似性和時間上的平滑性。

3 CTDNN-IPNS 算法

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

在實際網(wǎng)絡信息傳播過程中，信息通過節(jié)點間通聯(lián)在不同類型節(jié)點之間傳播。因此，在DK 謠言傳播模型的基礎上，本文結(jié)合實際通信網(wǎng)絡數(shù)據(jù)特點及其時間維度屬性，得出連續(xù)時間動態(tài)網(wǎng)絡具有以下特點：

1）信息傳播流程多數(shù)在一定時間內(nèi)完成，傳播范圍在大小不等的節(jié)點集內(nèi)。

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

3）類別相同或相似節(jié)點之間存在一定的周期性關(guān)聯(lián)關(guān)系。

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

表1 某電話通信網(wǎng)絡部分通話記錄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

由此可以推測，對于連續(xù)時間動態(tài)網(wǎng)絡的節(jié)點分類，若在網(wǎng)絡表示學習環(huán)節(jié)的節(jié)點序列采樣過程中對上述特征加以利用，其網(wǎng)絡表示學習結(jié)果將更好地保留節(jié)點在原始網(wǎng)絡結(jié)構(gòu)上的內(nèi)在相似性，在此基礎上得到的分類結(jié)果精度也將大幅提高。具體而言：一是將節(jié)點采樣范圍、時間范圍加以限制，提高節(jié)點集內(nèi)成員共現(xiàn)概率；二是增加采樣過程的靈活性，從逐個節(jié)點順序采樣轉(zhuǎn)變?yōu)閺墓?jié)點集內(nèi)成員發(fā)起的隨機采樣；三是信息傳播周期性的存在，使得同類節(jié)點共現(xiàn)概率會在一定范圍內(nèi)隨采樣次數(shù)的提高而增加。

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

基于上述分析，本文提出針對連續(xù)時間動態(tài)網(wǎng)絡節(jié)點分類的CTDNN-IPNS 算法，該算法基于信息傳播節(jié)點集的概念，對網(wǎng)絡表示學習環(huán)節(jié)的節(jié)點序列采樣策略進行改進，形成突顯節(jié)點之間關(guān)聯(lián)關(guān)系的節(jié)點向量表示，在此基礎上進行類別劃分，最終實現(xiàn)對連續(xù)時間動態(tài)網(wǎng)絡節(jié)點的分類。

3.1 節(jié)點序列采樣

節(jié)點序列采樣的具體步驟如下：

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

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

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

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

步驟5若Ec=?，則在時間t+Δt內(nèi)隨機調(diào)整基準時間t，重復步驟3～步驟5。

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

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

算法1CTDNN-IPNS 算法

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

3.2 網(wǎng)絡表示學習

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

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

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

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

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

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

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

3.3 節(jié)點向量分類

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

4 實驗與結(jié)果分析

4.1 實驗數(shù)據(jù)集與環(huán)境

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

表2 實驗數(shù)據(jù)集Table 2 Experimental dataset

表3 實驗環(huán)境Table 3 Experiment environment

4.2 參數(shù)設置

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

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

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

3）節(jié)點子序列截取考查范圍w：在本文實驗環(huán)境及數(shù)據(jù)集條件下設置為5。

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

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

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

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

4.3 CTDNN-IPNS 算法性能測試

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

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

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

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

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

表4 CTDNN-IPNS、STWalk 和CTDNE 算法對DBLP數(shù)據(jù)集的分類結(jié)果評價指標值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 數(shù)據(jù)集的分類結(jié)果評價指標值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 數(shù)據(jù)集的分類結(jié)果評價指標值Table 6 The evaluation index values of classification results on the Reality-Call dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

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

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

4.4 參數(shù)敏感性分析

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

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

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

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

圖9 CTDNN-IPNS 算法在DBLP 數(shù)據(jù)集上的分類性能隨參數(shù)Δ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 數(shù)據(jù)集上的分類性能隨參數(shù)Δt 的變化曲線Fig.10 The change curves of classification performance of CTDNN-IPNS algorithm on the Reality-Call dataset with parameter Δt

4.5 結(jié)果分析

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

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

5 結(jié)束語

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