王 巖，任 浩，王 喆

吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，長春 130000

真實世界復(fù)雜系統(tǒng)實體之間的交互或者連接可以自然地表示為網(wǎng)絡(luò)或者圖，如互聯(lián)網(wǎng)和萬維網(wǎng)[1-3]、科學(xué)引用和合作系統(tǒng)[4-5]、傳染病學(xué)[6-9]和通信系統(tǒng)[10]等。網(wǎng)絡(luò)中的節(jié)點表示系統(tǒng)中的不同實體，連邊代表實體之間的關(guān)系。網(wǎng)絡(luò)結(jié)構(gòu)有助于更直觀地了解現(xiàn)實世界中實體之間的關(guān)系。例如，利用網(wǎng)絡(luò)結(jié)構(gòu)表示的社交網(wǎng)絡(luò)數(shù)據(jù)，能夠很清楚地表示社交網(wǎng)絡(luò)中用戶關(guān)注和被關(guān)注信息；在蛋白質(zhì)相互作用網(wǎng)絡(luò)里，連邊展示了蛋白質(zhì)間能否相互反應(yīng)。對網(wǎng)絡(luò)進(jìn)行分析可以進(jìn)一步了解網(wǎng)絡(luò)的深層信息，例如鏈接預(yù)測、社區(qū)發(fā)現(xiàn)、節(jié)點分類等都得益于網(wǎng)絡(luò)分析技術(shù)的發(fā)展。但是，由于網(wǎng)絡(luò)可能包含數(shù)十億個節(jié)點和連邊，在整個網(wǎng)絡(luò)上執(zhí)行復(fù)雜的推理過程很難實現(xiàn)，并且網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)不能直接作為機器學(xué)習(xí)算法的輸入，所以如何對網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)進(jìn)行表示是一個重要問題。

傳統(tǒng)的方法是在網(wǎng)絡(luò)鄰接矩陣的基礎(chǔ)上進(jìn)行分析研究。最直觀的思路就是利用one-hot向量來表示網(wǎng)絡(luò)的鄰接矩陣，one-hot向量可以直接將網(wǎng)絡(luò)中的每個節(jié)點編碼成向量，并且向量維度與網(wǎng)絡(luò)中節(jié)點的個數(shù)相同。這種方法雖然簡單，但由于網(wǎng)絡(luò)鄰接矩陣高維稀疏，因而隨著網(wǎng)絡(luò)規(guī)模的增大，會耗費大量的時間和空間，并且one-hot向量不能準(zhǔn)確表達(dá)出節(jié)點之間的相連關(guān)系。

隨著表示學(xué)習(xí)技術(shù)在自然語言處理領(lǐng)域的不斷應(yīng)用，研究者開始將網(wǎng)絡(luò)中的節(jié)點表示成低維稠密的向量。并且網(wǎng)絡(luò)結(jié)構(gòu)中相近的節(jié)點應(yīng)具有相似的向量表示。向量表示的相似性一般用向量間的余弦或者歐氏距離表示。網(wǎng)絡(luò)表示學(xué)習(xí)就是研究在盡可能保留原始網(wǎng)絡(luò)結(jié)構(gòu)信息的基礎(chǔ)上，把網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)換為低維實值向量，并將其作為已有的機器學(xué)習(xí)算法的輸入[11]。網(wǎng)絡(luò)表示學(xué)習(xí)為揭示網(wǎng)絡(luò)結(jié)構(gòu)和執(zhí)行各種網(wǎng)絡(luò)挖掘任務(wù)提供了一種有效的方法。例如，節(jié)點的向量表示可以作為特征輸入支持向量機（SVM）等分類器用于節(jié)點分類任務(wù)，同時，節(jié)點表示也可以轉(zhuǎn)化成歐式空間中的點坐標(biāo)，用于可視化任務(wù)[12-14]。網(wǎng)絡(luò)表示學(xué)習(xí)不僅避免了傳統(tǒng)方法的復(fù)雜計算，還提高了算法性能。

現(xiàn)有的大多數(shù)網(wǎng)絡(luò)表示學(xué)習(xí)方法[15-17]通常關(guān)注靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)，其中節(jié)點和邊是固定的，不會隨著時間而改變，并沒有考慮網(wǎng)絡(luò)的動態(tài)變化。但是現(xiàn)實世界大多是動態(tài)網(wǎng)絡(luò)，其連邊和節(jié)點都是隨著時間不斷變化的。這些時序信息是動態(tài)網(wǎng)絡(luò)的重要部分，是網(wǎng)絡(luò)演化機制的體現(xiàn)。例如，在社交媒體中，隨著時間的推移，友誼關(guān)系的發(fā)展，電子郵件和短信等交流活動不斷涌現(xiàn)。在推薦系統(tǒng)中，每天都會出現(xiàn)新產(chǎn)品、新用戶和新評分。在計算金融中，交易是流動的，供應(yīng)鏈關(guān)系是不斷發(fā)展的。而靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法不能根據(jù)時序信息更新節(jié)點表示，并且當(dāng)網(wǎng)絡(luò)發(fā)生變化時需要重新訓(xùn)練所有的節(jié)點表示。同時忽略時間信息可能會導(dǎo)致節(jié)點表示的不準(zhǔn)確性。如圖1所示，節(jié)點v1、v2、v3代表三個用戶，假設(shè)從用戶v1到用戶v2有一封電子郵件ei=(v1,v2)，從用戶v2到用戶v3有一封電子郵件ej=(v2,v3)，同時T(v1,v2)為電子郵件ei=(v1,v2)的時間。因為T(v1,v2)=1＜T(v2,v3)=3，所以電子郵件ej=(v2,v3)可能反映了電子郵件ei=(v1,v2)的信息。但是T(v2,v3)=3＞T(v3,v1)=2，因此電子郵件ek=(v3,v1)不能包含電子郵件ej=(v2,v3)的信息。同時ek=(v3,v1)只能出現(xiàn)在ej=(v2,v3)前，如果不考慮連邊產(chǎn)生的時間信息隨機進(jìn)行選擇，很可能會導(dǎo)致結(jié)果出現(xiàn)偏差，這也說明了對實際序列進(jìn)行建模的重要性。

圖1 電子郵件網(wǎng)絡(luò)Fig.1 Email network

同時現(xiàn)有的動態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法[18-23]是將靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)算法應(yīng)用于動態(tài)網(wǎng)絡(luò)中的每個快照，即記錄相隔一定時間間隔的特定時刻的網(wǎng)絡(luò)結(jié)構(gòu)，并不能捕捉每個時間間隔內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)的具體演變過程，并且訓(xùn)練的時間復(fù)雜度會隨著網(wǎng)絡(luò)中頂點數(shù)量的增加而線性增加。

本文針對動態(tài)網(wǎng)絡(luò)中節(jié)點之間建立連邊的時間信息，學(xué)習(xí)適當(dāng)?shù)木W(wǎng)絡(luò)表示問題，以提高網(wǎng)絡(luò)演化的預(yù)測準(zhǔn)確性。通過描述了一個將時間信息合并到網(wǎng)絡(luò)表示學(xué)習(xí)方法中的通用框架，能捕捉動態(tài)網(wǎng)絡(luò)在連續(xù)時間上的演變特性，得到一個描述時序信息變化的網(wǎng)絡(luò)表示。在隨機游走過程中加入時間信息，尊重連邊建立的先后順序。同時考慮歷史鄰居的活動會影響當(dāng)前節(jié)點的選擇，建立模型考慮其影響變化。將采樣得到的隨機游走序列通過Skip-gram神經(jīng)網(wǎng)絡(luò)模型[24]訓(xùn)練得到節(jié)點的向量表示。本文使用網(wǎng)絡(luò)分析任務(wù)——鏈接預(yù)測和節(jié)點分類來衡量網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能。

1 基于隨機游走的動態(tài)連續(xù)時間網(wǎng)絡(luò)表示學(xué)習(xí)模型

1.1 相關(guān)模型及定義

1.1.1 相關(guān)模型

（1）Word2vec[25]模型。Word2vec模型能夠通過給定文本學(xué)習(xí)詞向量表示，其基本思想是利用神經(jīng)網(wǎng)絡(luò)，通過訓(xùn)練，將文本中的單詞轉(zhuǎn)換到低維、稠密的實數(shù)向量空間中，通過向量空間中的向量運算來簡化文本內(nèi)容上的處理。例如文本的語義相似度可以通過向量空間上的相似度來衡量，可以用于自然語言處理中的很多工作，包括同義詞尋找、詞性分析等。

Word2vec包含CBOW和Skip-gram兩種語言模型。這兩種模型在借鑒自然語言處理模型的基礎(chǔ)上進(jìn)行了簡化以便于計算，是包含了輸入層（Input）、投影層（Projection）和輸出層（Output）的三層神經(jīng)網(wǎng)絡(luò)。如圖2所示。

圖2 CBOW模型和Skip-gram模型Fig.2 CBOW model and Skip-gram model

訓(xùn)練過程可以簡述為：若給定某一語料庫，使用一個固定長度為c的滑動窗口來遍歷整個語料庫，每次從整個語料庫中抽取出一段語料進(jìn)行訓(xùn)練。假設(shè)c=2，則每次的訓(xùn)練語料為wt-2、wt-1、wt+1、wt+2來預(yù)測詞wt，訓(xùn)練過程如圖2所示。輸入層為wt的上下文wt-2、wt-1、wt+1、wt+2各個詞向量，投影層是對輸入層所有詞向量進(jìn)行累加求和，輸出層通常采用層級Softmax或者負(fù)采樣算法來表征已知上下文wt-2、wt-1、wt+1、wt+2的條件下wt出現(xiàn)的概率。Skip-gram模型的基本思想與CBOW相反，是使用某一詞wt來預(yù)測上下文wt-2、wt-1、wt+1、wt+2，訓(xùn)練過程與CBOW模型類似。

（2）網(wǎng)絡(luò)表示學(xué)習(xí)模型。網(wǎng)絡(luò)表示學(xué)習(xí)是一種網(wǎng)絡(luò)數(shù)據(jù)表示方法，將原始高維、稀疏的網(wǎng)絡(luò)映射到低維稠密的空間中，并保留原始網(wǎng)絡(luò)中的結(jié)構(gòu)特性。通常關(guān)注節(jié)點向量化，即對于圖G=(V,E)，學(xué)習(xí)一種映射f:Vi→Zi∈RD。其中Zi是一個將網(wǎng)絡(luò)中節(jié)點映射后輸出的表示向量，Zi的維度遠(yuǎn)遠(yuǎn)小于節(jié)點個數(shù)，即D＜＜|V|。圖3表明了網(wǎng)絡(luò)表示學(xué)習(xí)是所有基于復(fù)雜信息網(wǎng)絡(luò)的分析任務(wù)的基礎(chǔ)。

圖3 網(wǎng)絡(luò)表示學(xué)習(xí)過程示意圖Fig.3 Network representation of learning process diagram

（3）基于隨機游走的網(wǎng)絡(luò)表示學(xué)習(xí)。Perozzi等人提出DeepWalk[15]算法第一次把深度學(xué)習(xí)領(lǐng)域的研究成果應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)中。首先證明了網(wǎng)絡(luò)中節(jié)點隨機游走的分布規(guī)律與自然語言處理問題中句子序列在其所用語料庫中出現(xiàn)的規(guī)律服從類似的冪律分布。也就是說，如果在整個網(wǎng)絡(luò)中的點遵循冪律分布，那么在某個隨機游走的點上也遵循冪律分布。因此可以認(rèn)為在網(wǎng)絡(luò)上進(jìn)行隨機游走生成的序列的特性與NLP處理問題的對象很類似，從而將NLP中的詞向量模型，用于網(wǎng)絡(luò)節(jié)點中學(xué)習(xí)其向量表示。其整體思路是，在網(wǎng)絡(luò)中進(jìn)行長度一定的隨機游走并且得到一系列等長度的隨機游走序列，其中采樣得到的每一個隨機游走序列可以看作自然語言處理中的句子，通過Skip-gram模型中訓(xùn)練，得到節(jié)點的向量表示，并在網(wǎng)絡(luò)分析上獲得了很好的表示效果。由此得出，當(dāng)對網(wǎng)絡(luò)中的節(jié)點進(jìn)行隨機游走時，相比矩陣分解等方法，隨機游走只需要依賴節(jié)點的局部信息而不需要將網(wǎng)絡(luò)中所有節(jié)點的拓?fù)浣Y(jié)構(gòu)信息都存入內(nèi)存，從而大大節(jié)省內(nèi)存空間，并且可以有效降低鄰接矩陣的方差和不確定性。同時隨機游走可以記錄網(wǎng)絡(luò)的變化，即對網(wǎng)絡(luò)中變化的節(jié)點和連邊進(jìn)行隨機游走，而不需要重新計算網(wǎng)絡(luò)中的所有節(jié)點表示。算法的整體框架如圖4所示。

圖4 基于Skip-gram的網(wǎng)絡(luò)表示學(xué)習(xí)框架圖Fig.4 Network representation learning framework based on Skip-gram

1.1.2 相關(guān)定義

定義1動態(tài)離散時序網(wǎng)絡(luò)（dynamic discrete temporal network，DDTN）。在時序上對動態(tài)網(wǎng)絡(luò)等間隔取快照，從而得到網(wǎng)絡(luò)演化的離散序列，定義為DDTN={G1,G2,…,GT}其中Gt={Vt,Et}。如圖5所示。這種表示方法相當(dāng)于將動態(tài)網(wǎng)絡(luò)拆解成單個靜態(tài)網(wǎng)絡(luò)序列，并不能捕捉所取間隔內(nèi)網(wǎng)絡(luò)的變化。

圖5 網(wǎng)絡(luò)演化過程中的兩個快照Fig.5 Two snapshots of evolution of network

定義2動態(tài)連續(xù)時間網(wǎng)絡(luò)（dynamic continuous temporal network，DCTN）。給定一個網(wǎng)絡(luò)G=(V,ET,Φ)，V為節(jié)點集合，用ΕT?V*V*R+表示頂點關(guān)于時間信息的邊的集合。用映射函數(shù)Φ:E→R+將邊映射到時間戳上。例：圖6中，Φ(v2,v5)=8。

圖6 動態(tài)連續(xù)時間網(wǎng)絡(luò)Fig.6 Dynamic continuous temporal network

定義3時序鄰居（temporal neighbor）。節(jié)點v在時間點t的時序鄰居表示為Nt(v)，在傳統(tǒng)網(wǎng)絡(luò)的鄰居節(jié)點集合的基礎(chǔ)上，集合中的每個鄰居節(jié)點w都對應(yīng)一個時間戳t＇組成（節(jié)點，時間點）對。含義是節(jié)點v和鄰居節(jié)點w在時間戳t＇連接。要求鄰居節(jié)點所對應(yīng)的時間戳t＇要大于此時時間點t。即：

如圖6所示，v3在t=3的時序鄰居是{v2,v4,v5,v6}，在t=13的時序鄰居是{v5,v6}。

定義4時序游走（temporal walk）。一個時序游走就是一個節(jié)點序列，要求其滿足時間順序：即節(jié)點是按照時間先后進(jìn)行游走。也就是時序游走序列(v1,…,vi,vi+1,vi+2,…,vk)中Φ(vi,vi+1)≤Φ(vi+1,vi+2)如圖6所示，當(dāng)前時刻t=16時，v6到v3沒有合法的游走序列，因為v6和v3建立連接的時間在t=16前；當(dāng)前時刻t=13時，v3到v6有合法的序列，因為v3在t=13的時序鄰居為{v5,v6}。

1.2 動態(tài)連續(xù)時間網(wǎng)絡(luò)表示學(xué)習(xí)模型

1.2.1 問題定義

給定一個動態(tài)連續(xù)時間網(wǎng)絡(luò)G=(V ,ET,Φ)，目標(biāo)是學(xué)習(xí)一個函數(shù)f:V→RD，將節(jié)點映射到D維的空間中。D維的表示向量是基于時間信息得到的網(wǎng)絡(luò)演化相關(guān)的網(wǎng)絡(luò)表示，并且適用于下游的機器學(xué)習(xí)算法。

1.2.2 連續(xù)時間隨機游走

給定源節(jié)點u，模擬長度為l的連續(xù)時間隨機游走過程。ci為游走的第i個節(jié)點，起始節(jié)點c0=u。當(dāng)前節(jié)點v在時間t時，c 服從以下分布：

其中，πvw是節(jié)點v和w之間的非正則化轉(zhuǎn)移概率，Z是正則化常數(shù)。

1.2.3 采樣策略

有偏隨機游走是根據(jù)權(quán)重Wvw來選擇下一個采樣節(jié)點，即πvw=Wvw?？紤]到不同歷史鄰居對當(dāng)前節(jié)點選擇下一個時序鄰居節(jié)點的影響不同，且影響會隨著時間的增長而逐漸衰弱，定義在t時刻，當(dāng)前節(jié)點v和歷史鄰居節(jié)點h之間的權(quán)重：

其中，Ts( v ,h)是在( t -Δt,t)時間內(nèi)，節(jié)點v和歷史鄰居節(jié)點h建立連接的次數(shù)。因此在t時刻，當(dāng)前節(jié)點v與時序鄰居節(jié)點w之間的權(quán)重可以定義為：

式中，Nh(v)是在( t -Δt,t)時間內(nèi)，與節(jié)點v建立連接的歷史鄰居節(jié)點的集合。

1.2.4 時序窗口大小

由于時序游走會保留時間，遍歷時可能會耗盡時間有效的邊。因此，本文沒有對采樣的時序游走長度施加嚴(yán)格的限制，只需要每個時序游走最小長度為ω（ω相當(dāng)于skip-gram的窗口大小），最大長度為L，以適應(yīng)較長的游走序列長度。

1.3 學(xué)習(xí)DCTN節(jié)點嵌入

給定一個時序游走St，將學(xué)習(xí)節(jié)點嵌入的任務(wù)表示為最大似然優(yōu)化問題，使用Skip-gram架構(gòu)，需要優(yōu)化的目標(biāo)函數(shù)為：

式中，Ns()u?V表示源節(jié)點u通過采樣策略S所得到的網(wǎng)絡(luò)節(jié)點序列。

算法流程如下：

算法1DCTNE算法

輸入：G=(V ,ET,Φ)，向量維度D，每個節(jié)點生成節(jié)點序列的次數(shù)γ，生成節(jié)點序列最大長度L，窗口大小ω，時間間隔Δt。

輸出：節(jié)點的向量表示矩陣H∈RD。

算法2時序有偏隨機游走tiwalk

輸入：G＇=(V ,ET,Φ,π)，起始節(jié)點u，序列長度L。

輸出：節(jié)點采樣序列walk。

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

2.1 數(shù)據(jù)集和參數(shù)設(shè)置

（1）emails數(shù)據(jù)集

該網(wǎng)絡(luò)是利用歐洲一家大型研究機構(gòu)的電子郵件數(shù)據(jù)生成的。邊代表機構(gòu)成員之間的電子郵件溝通。有向邊( )

u,v,t是指機構(gòu)成員u在t時刻發(fā)送電子郵件給成員v，該網(wǎng)絡(luò)包含986位成員，時序邊332 334條，根據(jù)成員所屬部門的不同將所有成員進(jìn)行分類。

（2）CollegeMsg數(shù)據(jù)集

該數(shù)據(jù)集是由加利福尼亞大學(xué)在線社交網(wǎng)絡(luò)上發(fā)送的信息組成。用戶可以在網(wǎng)絡(luò)上搜索其他人，然后根據(jù)個人信息發(fā)送消息。邊( )u,v,t指用戶u在t時刻給用戶v發(fā)送了一條消息。該數(shù)據(jù)集中有1 899個用戶，時序邊59835條，根據(jù)用戶研究學(xué)科不同進(jìn)行分類。

（3）friends數(shù)據(jù)集

該數(shù)據(jù)集是Facebook朋友關(guān)系圖，其中節(jié)點是用戶，用戶之間的邊代表朋友關(guān)系。該網(wǎng)絡(luò)包含來自不同工作領(lǐng)域中的63 731個用戶，時序邊1 269 502條。

（4）DCTNE參數(shù)設(shè)置

節(jié)點的特征向量維度D=128，節(jié)點生成節(jié)點序列的次數(shù)γ=10，生成節(jié)點序列最大長度L=40，窗口大小ω=5。

2.2 基準(zhǔn)算法

（1）DeepWalk

受到word2vec的啟發(fā)，DeepWalk使用網(wǎng)絡(luò)中節(jié)點與節(jié)點之間的共現(xiàn)關(guān)系來學(xué)習(xí)節(jié)點的向量表示。DeepWalk在網(wǎng)絡(luò)中使用均勻隨機游走得到若干序列，這些序列相當(dāng)于自然語言中的句子，然后對序列中的節(jié)點對用層級softmax和Skip-gram模型進(jìn)行概率建模，使序列似然概率最大，并且通過隨機梯度下降來學(xué)習(xí)參數(shù)。實驗中，使用默認(rèn)參數(shù)設(shè)置：窗口大小ω=5，每個節(jié)點進(jìn)行10次隨機游走，隨機游走的序列長度為40，節(jié)點的特征向量維度D=128。

（2）Node2vec

Node2vec由兩個超參數(shù)p、q來控制隨機游走的廣度和深度，使其在深度和廣度中達(dá)到一個平衡，能夠保留節(jié)點局部和宏觀的信息。實驗中使用參數(shù)：p=0.25,q=4，節(jié)點的特征向量維度D=128。

（3）LINE

LINE是一種基于鄰域相似假設(shè)的方法。該方法將學(xué)習(xí)到的D維特征表示為兩部分：第一部分在直接鄰居節(jié)點上模擬廣度隨機游走來學(xué)習(xí)D/2維的特征；第二部分從距離源節(jié)點2-hop的節(jié)點中采樣學(xué)習(xí)剩下的D/2維特征，其中節(jié)點的特征向量維度D=128。

2.3 評價指標(biāo)

通過構(gòu)建混淆矩陣給出各評價指標(biāo)的定義，如表1。其中，TP（True Positive），真正例，把正例預(yù)測為正類；FN（False Negative）假正例，把正例預(yù)測為負(fù)類；FP（False Positive）假正例，把負(fù)例預(yù)測為正類；TN（True Negative），真反例，把負(fù)例預(yù)測為負(fù)類。

表1 二分類混淆矩陣Table 1 Two-class confusion matrix

根據(jù)表1四種評價指標(biāo)，得到更科學(xué)的評價指標(biāo)：

（1）精確率（precision），又叫查準(zhǔn)率，指的是預(yù)測值為1且實際值也為1的樣本在預(yù)測值為1的所有樣本中所占的比例：

（2）召回率（Recall），又叫查全率，指的是預(yù)測值為1且實際值也為1的樣本在實際值為1的所有樣本中所占的比例：

（3）準(zhǔn)確率（Accuracy），預(yù)測正確的樣本數(shù)占總樣本數(shù)的比例：

（4）F1分?jǐn)?shù)（F1-score），又稱平衡F分?jǐn)?shù)，是精確率和召回率的調(diào)和平均數(shù)：

（5）Macro-F1和Micro-F1：針對多標(biāo)簽分類。

Macro-F1：計算出所有類別總的precision和recall，然后計算F1分?jǐn)?shù)。

Micro-F1：計算出每一個類的precision和recall后計算F1分?jǐn)?shù)，最后將F1分?jǐn)?shù)平均。

（6）AUC（Area Under Curve）：被定義為ROC曲線下的面積。ROC曲線的橫坐標(biāo)為FP，縱坐標(biāo)是TP，表示正例排在負(fù)例前面的概率。

2.4 實驗效果與分析

2.4.1 鏈接預(yù)測

本文將鏈接預(yù)測作為二分類問題。在學(xué)習(xí)網(wǎng)絡(luò)中節(jié)點向量表示V的基礎(chǔ)上，通過Hadamard矩陣得到網(wǎng)絡(luò)中邊edge(u,v)的特征向量，即edge(u,v)=v?u，其中v?u=V*U，并預(yù)測在t時刻之后建立的邊。將t時刻之后生成的邊作為正樣本，隨機抽取t時刻之前的相同數(shù)量的邊作為負(fù)樣本。并且，在數(shù)據(jù)集上訓(xùn)練了一個邏輯回歸分類器。鏈接預(yù)測的結(jié)果使用AUC值作為算法評價指標(biāo)。實驗結(jié)果如表2所示。

表2 鏈接預(yù)測的AUC值Table 2 AUC of link prediction results

在節(jié)點表示維度相同的條件下，將算法DeepWalk，Node2vec、LINE和DCTNE學(xué)習(xí)到的節(jié)點表示應(yīng)用到鏈接預(yù)測任務(wù)效果中。實驗中，DCTNE在emails數(shù)據(jù)集中的時間間隔Δt=2 000，在CollegeMsg數(shù)據(jù)集中的時間間隔Δt=2 000，在friends數(shù)據(jù)集中的時間間隔Δt=4 000。參數(shù)取值結(jié)果如圖7所示。實驗結(jié)果表明：DCTNE算法相較于算法DeepWalk、Node2vec、LINE將學(xué)習(xí)到的節(jié)點表示用于鏈接預(yù)測任務(wù)中效果較其他算法表現(xiàn)更好。在emails數(shù)據(jù)集上分別提高了13.7%、22.5%、10.6%，在CollegeMsg數(shù)據(jù)集上分別提高了7.86%、8.15%、1.41%，在friends數(shù)據(jù)集上分別提高了25.7%、50.1%、17.7%。DCTNE方法尊重了邊緣形成的時間過程，將時間信息嵌入到節(jié)點表示中，從而在鏈接預(yù)測任務(wù)中優(yōu)于其他算法。

圖7 不同Δt下鏈接預(yù)測的AUC值Fig.7 AUC of link prediction results under differentΔt

2.4.2 節(jié)點分類

節(jié)點分類是網(wǎng)絡(luò)分析的重要組成部分，節(jié)點一般在網(wǎng)絡(luò)中扮演著不同的角色。為驗證DCTNE在節(jié)點分類任務(wù)上的有效性，在數(shù)據(jù)集emails、CollegeMsg和friends上執(zhí)行多分類實驗。對每個數(shù)據(jù)集分別使用DeepWalk、Node2vec、LINE、DCTNE學(xué)習(xí)表示向量，出于公平起見，上述方法均使用默認(rèn)參數(shù)，表示向量維度為128。隨機地將數(shù)據(jù)集劃分為訓(xùn)練集和測試集，訓(xùn)練集比例為10%～90%，當(dāng)訓(xùn)練集比例為10%時，測試集比例為90%，以此類推。使用XGBoost分類器對數(shù)據(jù)進(jìn)行分類，并通過貝葉斯優(yōu)化對分類器進(jìn)行參數(shù)優(yōu)化。由于這三個數(shù)據(jù)集的標(biāo)簽不是完全平衡的，使用Macro-F1分?jǐn)?shù)作為性能度量，每個分類實驗被重復(fù)10次得到平均分?jǐn)?shù)，以減少分類器引入的噪聲。實驗中，DCTNE在emails數(shù)據(jù)集中的時間間隔Δt=3 000，在CollegeMsg數(shù)據(jù)集中的時間間隔Δt=2 000，在friends數(shù)據(jù)集中的時間間隔Δt=2 000。參數(shù)取值結(jié)果如圖8所示。實驗結(jié)果如表3～5所示。

表3 不同算法在emails數(shù)據(jù)集上的Macro-F1分?jǐn)?shù)Table 3 Macro-F1 scores of different algorithms on emails dataset

圖8 不同Δt下Macro-F1分?jǐn)?shù)Fig.8 Macro-F1 scores under differentΔt

從表中可以看出，DCTNE算法得到的節(jié)點向量表示的分類效果總體而言比DeepWalk、Node2vec、LINE算法得到的節(jié)點表示的分類效果好。實驗結(jié)果證明，DCTNE算法學(xué)習(xí)到了網(wǎng)絡(luò)的演化，有利于網(wǎng)絡(luò)節(jié)點分類任務(wù)。

由于歷史鄰居會影響所捕獲的鄰居結(jié)構(gòu)，且影響會隨著時間t的增長而減弱。討論時間間隔Δt在emails、CollegeMsg、friends三個數(shù)據(jù)集上的參數(shù)敏感性。實驗結(jié)果如圖7、8所示。從圖中可以看出，DCTNE算法在三個數(shù)據(jù)集上的AUC值和Macro-F1分?jǐn)?shù)在Δt的不同設(shè)置下結(jié)果不同，總體呈現(xiàn)先上升后下降的趨勢。實驗結(jié)果表明：當(dāng)Δt取值較小時，游走序列會缺失部分信息，從而使實驗結(jié)果準(zhǔn)確率降低；當(dāng)Δt取值較大時，游走序列會忽略近期歷史鄰居對當(dāng)前鄰居結(jié)構(gòu)產(chǎn)生的較大影響，使得所有歷史鄰居對當(dāng)前鄰居結(jié)構(gòu)的影響基本一致，忽略了由于時間而造成歷史鄰居對當(dāng)前鄰居結(jié)構(gòu)的影響會隨著時間增長而逐漸減弱的關(guān)系，從而使實驗結(jié)果的準(zhǔn)確率下降。

表4 不同算法在CollegeMsg數(shù)據(jù)集上的Macro-F1分?jǐn)?shù)Table 4 Macro-F1 scores of different algorithms on CollegeMsg dataset

表5 不同算法在friends數(shù)據(jù)集上的Macro-F1分?jǐn)?shù)Table 5 Macro-F1 scores of different algorithms on friends dataset

2.5 參數(shù)敏感性

3 結(jié)語

本文介紹了一種基于隨機游走的動態(tài)連續(xù)時間網(wǎng)絡(luò)表示學(xué)習(xí)算法，通過尊重邊建立的時間信息來約束節(jié)點的隨機游走序列。對于采樣得到的節(jié)點序列通過Skip-gram模型得到網(wǎng)絡(luò)的節(jié)點向量表示。實驗結(jié)果證明：提出的算法DCTNE相比DeepWalk、Node2vec、LINE算法，能夠考慮網(wǎng)絡(luò)邊緣建立連接的時間信息，從而很好地學(xué)習(xí)動態(tài)網(wǎng)絡(luò)中的節(jié)點向量表示。同時適用于大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集，且具有較強魯棒性，即使在訓(xùn)練集比例較低時，仍優(yōu)于其他對比算法。在未來的工作中，將進(jìn)一步挖掘網(wǎng)絡(luò)中節(jié)點之間的相互影響，結(jié)合節(jié)點標(biāo)簽信息和文本信息進(jìn)行更準(zhǔn)確的網(wǎng)絡(luò)表示。