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

黃 鑫，李 赟，熊瑾煜

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

0 概述

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

1 相關(guān)工作

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

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

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

2 相關(guān)定義

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

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

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

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

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

3 CTDNN-IPNS 算法

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

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

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

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

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

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

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

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

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

3.1 節(jié)點(diǎn)序列采樣

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

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

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

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

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

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

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

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

算法1CTDNN-IPNS 算法

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

3.2 網(wǎng)絡(luò)表示學(xué)習(xí)

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

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

為簡化計算過程進(jìn)行以下假設(shè)：

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

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

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

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

3.3 節(jié)點(diǎn)向量分類

CTDNN-IPNS 算法采 用LogicRegression 分類器對網(wǎng)絡(luò)表示學(xué)習(xí)環(huán)節(jié)生成的節(jié)點(diǎn)向量進(jìn)行分類，并依據(jù)F1_macro 和F1_micro 值量化評價分類結(jié)果。F1_macro 和F1_micro 的求解過程為：設(shè)數(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）進(jìn)行求解，反映了分類結(jié)果在各個類別中樣本分類的綜合性能，F(xiàn)1_micro 可根據(jù)式（9）～式（11）進(jìn)行求解，反映了分類結(jié)果在所有樣本上的綜合分類性能。

4 實(shí)驗(yàn)與結(jié)果分析

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

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

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental dataset

表3 實(shí)驗(yàn)環(huán)境Table 3 Experiment environment

4.2 參數(shù)設(shè)置

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

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

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

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

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

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

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

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

4.3 CTDNN-IPNS 算法性能測試

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

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

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

在總游走次數(shù)下，CTDNN-IPNS、CTDNE和STWalk算法對不同數(shù)據(jù)集的分類結(jié)果評價指標(biāo)值（F1_micro和F1_macro）如表4～表6 所示。上述分類結(jié)果評價指標(biāo)值對應(yīng)的曲線如圖4～圖6 所示。根據(jù)上述分類結(jié)果的評價指標(biāo)值可知，針對DBLP、AMiner 和Reality-Call數(shù)據(jù)集，CTDNN-IPNS 算法整體上優(yōu)于STWalk 和CTDNE 算法。具體而言，在3 組實(shí)驗(yàn)中，CTDNE 算法分類結(jié)果的F1_micro 和F1_macro 值隨節(jié)點(diǎn)采樣次數(shù)的增加而呈現(xiàn)出上升趨勢，但上升速度較慢。在對DBLP數(shù)據(jù)集和Aminer數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)分類時，CTDNN-IPNS算法分類結(jié)果的F1_micro 和F1_macro 值均為最高值，且在總游走次數(shù)較少時，其優(yōu)勢更為明顯。在對Reality-Call數(shù)據(jù)集進(jìn)行分類時，3 種算法均在總游走次數(shù)達(dá)到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é)果評價指標(biāo)值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é)果評價指標(biāo)值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é)果評價指標(biāo)值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ù)敏感性分析

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

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

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

5 結(jié)束語

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