黃 鑫，李 赟，熊瑾煜

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

0 概述

復(fù)雜網(wǎng)絡(luò)是對(duì)現(xiàn)實(shí)世界中復(fù)雜系統(tǒng)的抽象表示，復(fù)雜系統(tǒng)的各組成部分及其相互之間的關(guān)聯(lián)關(guān)系分別用節(jié)點(diǎn)和節(jié)點(diǎn)之間的邊來(lái)表示。對(duì)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)開(kāi)展分類問(wèn)題研究，有利于加深對(duì)復(fù)雜系統(tǒng)內(nèi)部組成的理解。傳統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)分類主要針對(duì)靜態(tài)網(wǎng)絡(luò)，即不考慮網(wǎng)絡(luò)隨時(shí)間發(fā)生演變，網(wǎng)絡(luò)節(jié)點(diǎn)和節(jié)點(diǎn)之間的邊始終保持不變。在實(shí)際情況中，網(wǎng)絡(luò)的動(dòng)態(tài)特征明顯，節(jié)點(diǎn)和節(jié)點(diǎn)之間的邊可能隨時(shí)間發(fā)生變化。為使研究更貼近實(shí)際情況，在靜態(tài)網(wǎng)絡(luò)的基礎(chǔ)上充分考慮時(shí)間要素，研究人員提出動(dòng)態(tài)網(wǎng)絡(luò)概念并進(jìn)一步開(kāi)展網(wǎng)絡(luò)相關(guān)研究。本文基于經(jīng)典的網(wǎng)絡(luò)節(jié)點(diǎn)分類方法，在考慮時(shí)間要素的前提下，根據(jù)連續(xù)時(shí)間動(dòng)態(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ù)時(shí)間動(dòng)態(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)分類問(wèn)題的一類重要方法［1-3］。這類方法將網(wǎng)絡(luò)節(jié)點(diǎn)表示為低維空間向量，通過(guò)對(duì)向量的分類實(shí)現(xiàn)節(jié)點(diǎn)的分類。結(jié)合網(wǎng)絡(luò)表示學(xué)習(xí)方法，在分類過(guò)程中根據(jù)是否考慮節(jié)點(diǎn)或連邊隨時(shí)間變化的情況，形成靜態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)分類和動(dòng)態(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ī)游走與自然語(yǔ)言處理領(lǐng)域的Skip-Gram 詞向量生成模型相結(jié)合，形成節(jié)點(diǎn)采樣+Skip-Gram 的網(wǎng)絡(luò)表示學(xué)習(xí)框架，將網(wǎng)絡(luò)節(jié)點(diǎn)和通過(guò)在網(wǎng)絡(luò)節(jié)點(diǎn)之間隨機(jī)游走采樣獲取的節(jié)點(diǎn)序列分別視作自然語(yǔ)言中的詞和語(yǔ)句，對(duì)節(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)和計(jì)算復(fù)雜度低的特點(diǎn)。在此基礎(chǔ)上，通過(guò)改進(jìn)節(jié)點(diǎn)序列采樣策略，衍生出Node2 Vec［8］、Walklets［11］、Metapath2Vec［12］等 眾多網(wǎng)絡(luò)表示學(xué)習(xí)算法。這類算法針對(duì)靜態(tài)網(wǎng)絡(luò)展開(kāi)研究，未能對(duì)網(wǎng)絡(luò)中的時(shí)間信息加以利用，即未考慮節(jié)點(diǎn)或連邊隨時(shí)間的變化情況對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)結(jié)果的影響，不適用于動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)分類。

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

2 相關(guān)定義

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

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

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

定義2（連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)）在連續(xù)時(shí)間動(dòng)態(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)在相似性和時(shí)間上的平滑性。

3 CTDNN-IPNS 算法

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

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

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

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

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

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

表1 某電話通信網(wǎng)絡(luò)部分通話記錄Table 1 Partial call records of a telephone communication network

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

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

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

基于上述分析，本文提出針對(duì)連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)分類的CTDNN-IPNS 算法，該算法基于信息傳播節(jié)點(diǎn)集的概念，對(duì)網(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)對(duì)連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)的分類。

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

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

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

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

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

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

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

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

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

算法1CTDNN-IPNS 算法

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

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

定義4（節(jié)點(diǎn)鄰居序列）對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)u，在以采樣策略S進(jìn)行一次采樣形成的序列中，與其同時(shí)被采集到的節(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í)問(wèn)題轉(zhuǎn)化為使V中所有節(jié)點(diǎn)v?V在嵌入結(jié)果為f(v)的條件下，節(jié)點(diǎn)鄰居序列中的節(jié)點(diǎn)共同出現(xiàn)的對(duì)數(shù)條件概率之和最大的優(yōu)化問(wèn)題，計(jì)算公式為：

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

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

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

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

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

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

CTDNN-IPNS 算法采 用LogicRegression 分類器對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)環(huán)節(jié)生成的節(jié)點(diǎn)向量進(jìn)行分類，并依據(jù)F1_macro 和F1_micro 值量化評(píng)價(jià)分類結(jié)果。F1_macro 和F1_micro 的求解過(guò)程為：設(shè)數(shù)據(jù)集中的數(shù)據(jù)共分為n類，類別集合為C={c1,c2,…,cn}。對(duì)于類別ci，i=1,2,…,n，數(shù)據(jù)分類結(jié)果中的正確分類樣本、錯(cuò)誤分類樣本和非ci類錯(cuò)誤分類樣本數(shù)量可分別表示為TTP、FFP、FFN，則F1_macro 可根據(jù)式（5）～式（8）進(jìn)行求解，反映了分類結(jié)果在各個(gè)類別中樣本分類的綜合性能，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ù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)的二維可視化展示效果及其節(jié)點(diǎn)分類結(jié)果兩方面，對(duì)CTDNN-IPNS 算法的性能進(jìn)行實(shí)驗(yàn)驗(yàn)證，數(shù)據(jù)集信息如表2 所示。DBLP 和AMiner 數(shù)據(jù)集中的網(wǎng)絡(luò)節(jié)點(diǎn)是文章作者，若兩位作者共同發(fā)表過(guò)論文，則兩者之間存在一條連邊，邊的時(shí)間戳為論文發(fā)表年份，節(jié)點(diǎn)類別是論文作者的所屬研究領(lǐng)域。類似地，Reality-Call 數(shù)據(jù)集中的用戶號(hào)碼被視為網(wǎng)絡(luò)節(jié)點(diǎn)，若兩位用戶有過(guò)通話，則其對(duì)應(yīng)的節(jié)點(diǎn)之間存在一條連邊，邊的時(shí)間戳為通話發(fā)起時(shí)間，節(jié)點(diǎn)類別為號(hào)碼所屬部門。實(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ī)游走步長(zhǎng)l：選擇大于網(wǎng)絡(luò)平均路徑長(zhǎng)度的數(shù)值，在本文實(shí)驗(yàn)中設(shè)置為10。

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

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

5）訓(xùn)練數(shù)據(jù)使用率γ：通常按照3∶1 的比例將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集，在本文實(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)的每個(gè)節(jié)點(diǎn)為起點(diǎn)且依次開(kāi)始隨機(jī)游走的策略，為便于比較，在實(shí)驗(yàn)中將總游走次數(shù)設(shè)置為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的整數(shù)倍。

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

4.3 CTDNN-IPNS 算法性能測(cè)試

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

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

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

在總游走次數(shù)下，CTDNN-IPNS、CTDNE和STWalk算法對(duì)不同數(shù)據(jù)集的分類結(jié)果評(píng)價(jià)指標(biāo)值（F1_micro和F1_macro）如表4～表6 所示。上述分類結(jié)果評(píng)價(jià)指標(biāo)值對(duì)應(yīng)的曲線如圖4～圖6 所示。根據(jù)上述分類結(jié)果的評(píng)價(jià)指標(biāo)值可知，針對(duì)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)出上升趨勢(shì)，但上升速度較慢。在對(duì)DBLP數(shù)據(jù)集和Aminer數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)分類時(shí)，CTDNN-IPNS算法分類結(jié)果的F1_micro 和F1_macro 值均為最高值，且在總游走次數(shù)較少時(shí)，其優(yōu)勢(shì)更為明顯。在對(duì)Reality-Call數(shù)據(jù)集進(jìn)行分類時(shí)，3 種算法均在總游走次數(shù)達(dá)到750 以上時(shí)獲得較好的分類效果，但CTDNN-IPNS 算法的分類效果更佳，且在總游走次數(shù)低于750 時(shí)，CTDNN-IPNS 算法具有更好的分類性能，其F1_micro和F1_macro 值更高且增速更快。

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

表4 CTDNN-IPNS、STWalk 和CTDNE 算法對(duì)DBLP數(shù)據(jù)集的分類結(jié)果評(píng)價(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 算法對(duì)AMiner 數(shù)據(jù)集的分類結(jié)果評(píng)價(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 算法對(duì)Reality-Call 數(shù)據(jù)集的分類結(jié)果評(píng)價(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 種算法對(duì)DBLP 數(shù)據(jù)集的分類結(jié)果評(píng)價(jià)曲線Fig.4 The evaluation curves of classification results on the DBLP dataset by three algorithms

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

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

隨機(jī)游走步長(zhǎng)l和節(jié)點(diǎn)子序列截取考查范圍w及信息傳播時(shí)間范圍Δt是CTDNN-IPNS 算法中的重要參數(shù)，本節(jié)通過(guò)在DBLP 數(shù)據(jù)集上設(shè)定其他參數(shù)，分別改變l、w和Δt的取值大小來(lái)觀察節(jié)點(diǎn)分類指標(biāo)值（F1_micro 和F1_macro）的變化情況，對(duì)算法的參數(shù)敏感性進(jìn)行分析。如圖7 所示，隨著l值的增加，F(xiàn)1_micro 和F1_macro 值先快速上升，再逐漸趨于平緩，曲線拐點(diǎn)在l=7 附近，接近于DBLP 數(shù)據(jù)集的平均路徑長(zhǎng)度值，且當(dāng)l取值大于網(wǎng)絡(luò)平均路徑長(zhǎng)度時(shí)，算法性能趨于平穩(wěn)。這表明基于信息節(jié)點(diǎn)集的隨機(jī)游走節(jié)點(diǎn)采樣方式，能夠較好地反映出網(wǎng)絡(luò)的通聯(lián)規(guī)律及其內(nèi)在的結(jié)構(gòu)屬性。在本文實(shí)驗(yàn)中，為便于算法性能比較，將隨機(jī)游走步長(zhǎng)設(shè)定為3 個(gè)數(shù)據(jù)集的網(wǎng)絡(luò)平均路徑最大值，故取l=10。在圖8中，隨著w值的增加，F(xiàn)1_micro 和F1_macro 值逐步提高，當(dāng)w≥5 時(shí)逐漸趨于平穩(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í)，算法分類性能較其他取值有小幅增長(zhǎng)，這表明該參數(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ù)較少時(shí)，CTDNE 算法因采用嚴(yán)格依照時(shí)間先后順序的游走策略，在網(wǎng)絡(luò)學(xué)習(xí)表示過(guò)程中受噪聲影響較大，不能較好地捕捉到節(jié)點(diǎn)與同類別其他節(jié)點(diǎn)之間的關(guān)系，隨著游走次數(shù)的增加，同類別節(jié)點(diǎn)的共現(xiàn)次數(shù)逐漸增加，其分類精度也隨之提高。由于STWalk 算法和CTDNN-IPNS 算法在隨機(jī)游走過(guò)程中，分別以節(jié)點(diǎn)歷史鄰居和信息傳播集內(nèi)節(jié)點(diǎn)為采樣對(duì)象，因此在隨機(jī)游走次數(shù)較少時(shí)表現(xiàn)出較好的分類性能，隨著游走次數(shù)的增加，采集節(jié)點(diǎn)數(shù)逐漸增多，采樣序列反而可能受到不同類別節(jié)點(diǎn)的干擾，導(dǎo)致分類性能略有下降，但總體表現(xiàn)基本平穩(wěn)。

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

5 結(jié)束語(yǔ)

本文提出一種新的連續(xù)時(shí)間動(dòng)態(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)對(duì)連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)分類。實(shí)驗(yàn)結(jié)果表明，針對(duì)論文合作網(wǎng)絡(luò)的作者分類和電話通信網(wǎng)絡(luò)的用戶分類問(wèn)題，相比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)重等信息，研究針對(duì)連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)的分類算法，進(jìn)一步提升其分類效果和適用范圍。