基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)*

韓忠明 李勝男 鄭晨燁 段大高 楊偉杰

1) (北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院，北京 100048)

2) (北京工商大學(xué)食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100048)

1 引 言

在現(xiàn)實(shí)世界中, 很多復(fù)雜系統(tǒng)以復(fù)雜網(wǎng)絡(luò)的形式出現(xiàn), 如社會(huì)網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和web 網(wǎng)絡(luò)等. 網(wǎng)絡(luò)提供了一種組織現(xiàn)實(shí)世界中的多樣化信息的方式, 成為人們工作生活中不可或缺的一部分, 對(duì)這些網(wǎng)絡(luò)進(jìn)行分析研究具有非常大的學(xué)術(shù)價(jià)值和潛在應(yīng)用價(jià)值[1]. 在這些網(wǎng)絡(luò)中, 節(jié)點(diǎn)之間的交互行為通常以“鏈接”的形式表示, 即使用邊將兩個(gè)節(jié)點(diǎn)連接. 以社交網(wǎng)絡(luò)為例, 網(wǎng)絡(luò)節(jié)點(diǎn)用于描述用戶, 邊用于描述用戶之間的交互行為. 鏈接預(yù)測(cè)[2]通過(guò)分析網(wǎng)絡(luò)中的信息來(lái)預(yù)測(cè)未來(lái)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間是否可能出現(xiàn)鏈接. 有效的鏈接預(yù)測(cè)對(duì)人們生活中各個(gè)方面都具有重要意義, 例如幫助人們控制信息在網(wǎng)絡(luò)上的傳播, 幫助社交平臺(tái)進(jìn)行更準(zhǔn)確的好友推薦等.

在真實(shí)世界中, 網(wǎng)絡(luò)會(huì)隨著時(shí)間的推移不斷進(jìn)行演變, 即網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊會(huì)隨時(shí)間發(fā)生變化.網(wǎng)絡(luò)演變會(huì)導(dǎo)致網(wǎng)絡(luò)信息發(fā)生變化, 進(jìn)而對(duì)鏈接預(yù)測(cè)任務(wù)產(chǎn)生影響, 因此, 捕獲這些網(wǎng)絡(luò)演化信息是很有必要的. 以社交網(wǎng)絡(luò)為例, 網(wǎng)絡(luò)中隨時(shí)會(huì)有新用戶注冊(cè), 用戶隨時(shí)會(huì)創(chuàng)建新的好友關(guān)系, 這些新信息的增加不僅改變了當(dāng)前用戶的屬性信息, 其鄰域的拓?fù)浣Y(jié)構(gòu)和屬性信息也會(huì)隨之發(fā)生改變.

圖1 展示了一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)示意圖, 假設(shè)在對(duì)網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測(cè)任務(wù)時(shí), 以節(jié)點(diǎn)共同鄰居個(gè)數(shù)度量節(jié)點(diǎn)相似性, 相似度越大的節(jié)點(diǎn)對(duì)在下一時(shí)刻發(fā)生鏈接的可能性越大. 在T1 時(shí)刻, 網(wǎng)絡(luò)中的節(jié)點(diǎn)2 和節(jié)點(diǎn)5 擁有一個(gè)共同鄰居(節(jié)點(diǎn)4), 在T2 時(shí)刻, 該網(wǎng)絡(luò)在節(jié)點(diǎn)3 和節(jié)點(diǎn)5 之間新增了一條邊,即節(jié)點(diǎn)3 變成了節(jié)點(diǎn)5 的鄰居. 此時(shí)節(jié)點(diǎn)2 和節(jié)點(diǎn)5 擁有兩個(gè)共同鄰居(節(jié)點(diǎn)4 和節(jié)點(diǎn)3), 它們?cè)谙乱粫r(shí)刻產(chǎn)生鏈接的可能性變大. 由此可見(jiàn), 雖然新增加的邊只涉及到節(jié)點(diǎn)3 和節(jié)點(diǎn)5, 但其鄰域中的節(jié)點(diǎn)2 的屬性也受到了影響. 因此, 網(wǎng)絡(luò)動(dòng)態(tài)演化對(duì)節(jié)點(diǎn)及其鄰域的特征信息有著非常重要的影響, 在鏈接預(yù)測(cè)過(guò)程中加入動(dòng)態(tài)信息將會(huì)提高鏈接預(yù)測(cè)的性能.

圖1 動(dòng)態(tài)網(wǎng)絡(luò)示意圖Fig. 1. Schematic diagram of dynamic network.

現(xiàn)有的鏈接預(yù)測(cè)方法大多針對(duì)靜態(tài)網(wǎng)絡(luò), 使用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征分析的方法進(jìn)行鏈接預(yù)測(cè), 當(dāng)網(wǎng)絡(luò)信息發(fā)生變化時(shí), 其性能將會(huì)受到很大影響. 此外, 網(wǎng)絡(luò)中的節(jié)點(diǎn)并不是每時(shí)每刻都在產(chǎn)生新的交互信息, 其發(fā)生變化的時(shí)間是不規(guī)律的, 即變化發(fā)生的時(shí)間分布不均勻. 而兩次變化之間的時(shí)間間隔會(huì)影響節(jié)點(diǎn)的偏好信息. 例如, 如果某節(jié)點(diǎn)兩次變化之間的時(shí)間間隔較長(zhǎng), 則應(yīng)該更關(guān)注新的交互信息, 因?yàn)樾碌男畔⒏荏w現(xiàn)該節(jié)點(diǎn)當(dāng)前的偏好. 為了有效地捕獲網(wǎng)絡(luò)中的動(dòng)態(tài)演化信息, 本文使用表示學(xué)習(xí)方法, 用低維稠密向量表示網(wǎng)絡(luò)節(jié)點(diǎn)的偏好信息, 通過(guò)度量網(wǎng)絡(luò)節(jié)點(diǎn)表示的相似度進(jìn)行鏈接預(yù)測(cè), 并提出了基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)模型

DNRLP(dynamic network representation based link prediction). 針對(duì)網(wǎng)絡(luò)演化產(chǎn)生的動(dòng)態(tài)信息,DNRLP 設(shè)計(jì)了基于不均勻時(shí)間間隔的信息更新機(jī)制. 同時(shí), 考慮到動(dòng)態(tài)信息對(duì)相關(guān)節(jié)點(diǎn)鄰域的影響, 設(shè)計(jì)了基于連接強(qiáng)度的隨機(jī)游走算法對(duì)鄰域信息進(jìn)行更新. 該模型可以有效地捕獲網(wǎng)絡(luò)動(dòng)態(tài)信息, 提高鏈接預(yù)測(cè)的質(zhì)量和有效性.

2 相關(guān)研究

2.1 鏈接預(yù)測(cè)

現(xiàn)有的鏈接預(yù)測(cè)研究方法主要分為兩類, 基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征分析的方法和基于機(jī)器學(xué)習(xí)的方法. 傳統(tǒng)的鏈接預(yù)測(cè)方法主要是通過(guò)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行特征分析, 計(jì)算節(jié)點(diǎn)之間的相似度, 認(rèn)為相似度高的節(jié)點(diǎn)在將來(lái)會(huì)發(fā)生鏈接. Newman 等[3]首先提出基于網(wǎng)絡(luò)共同鄰居的節(jié)點(diǎn)相似度計(jì)算方法, 即節(jié)點(diǎn)擁有的共同鄰居越多, 越可能在未來(lái)發(fā)生鏈接. Adamic 等[4]提出了一種新的網(wǎng)絡(luò)節(jié)點(diǎn)相似性度量方法, 該方法根據(jù)共同鄰居節(jié)點(diǎn)的鏈接情況為每個(gè)鄰居節(jié)點(diǎn)設(shè)置權(quán)重, 并使用其加權(quán)和作為節(jié)點(diǎn)對(duì)的相似度. Fouss 等[5]通過(guò)隨機(jī)游走算法對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰域信息進(jìn)行采樣, 得到目標(biāo)節(jié)點(diǎn)的隨機(jī)游走序列, 然后計(jì)算節(jié)點(diǎn)隨機(jī)游走序列的相似性進(jìn)行鏈接預(yù)測(cè).

隨著人工智能和機(jī)器學(xué)習(xí)技術(shù)的快速發(fā)展, 越來(lái)越多的研究人員嘗試使用機(jī)器學(xué)習(xí)方法去解決鏈接預(yù)測(cè)問(wèn)題. 基于機(jī)器學(xué)習(xí)的鏈接預(yù)測(cè)方法首先需要從網(wǎng)絡(luò)中得到各個(gè)節(jié)點(diǎn)的特征向量, 然后將節(jié)點(diǎn)的特征向量作為機(jī)器學(xué)習(xí)算法的輸入. Hasan 等[6]將鏈接預(yù)測(cè)問(wèn)題轉(zhuǎn)化為機(jī)器學(xué)習(xí)中的二分類問(wèn)題,嘗試使用支持向量機(jī)[7], 多層感知機(jī)等機(jī)器學(xué)習(xí)方法進(jìn)行鏈接預(yù)測(cè), 若兩節(jié)點(diǎn)間未來(lái)可能產(chǎn)生鏈接則預(yù)測(cè)值為1, 否則為0. Freno 等[8]使用自然語(yǔ)言處理領(lǐng)域的詞袋模型對(duì)論文引用網(wǎng)絡(luò)中論文的摘要進(jìn)行建模, 得到論文節(jié)點(diǎn)的特征表示, 然后使用神經(jīng)網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測(cè). Hosein 等[9]針對(duì)引文網(wǎng)絡(luò)使用論文作者和論文的互聚類方法進(jìn)行鏈接預(yù)測(cè).Xu 等[10]將信息熵應(yīng)用于加權(quán)網(wǎng)絡(luò)中的鏈接預(yù)測(cè),提出基于路徑貢獻(xiàn)的加權(quán)相似度指標(biāo), 實(shí)現(xiàn)了加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測(cè). Lai 等[11]針對(duì)復(fù)雜網(wǎng)絡(luò), 用模塊化的置信度傳播算法來(lái)獲得網(wǎng)絡(luò)的底層塊結(jié)構(gòu), 并通過(guò)塊結(jié)構(gòu)信息對(duì)節(jié)點(diǎn)間產(chǎn)生鏈接的可能性進(jìn)行建模, 從而實(shí)現(xiàn)鏈接預(yù)測(cè). Kovács 等[12]針對(duì)蛋白質(zhì)相互作用網(wǎng)絡(luò), 根據(jù)蛋白質(zhì)之間的交互特性,使用長(zhǎng)度為3 的網(wǎng)絡(luò)路徑(L3)進(jìn)行鏈接預(yù)測(cè).Pech 等[13]提出了一種新的鏈接方法, 由節(jié)點(diǎn)鄰居貢獻(xiàn)率的線性和來(lái)估計(jì)鏈接的可能性, 從而將鏈接預(yù)測(cè)問(wèn)題轉(zhuǎn)化為似然矩陣的優(yōu)化問(wèn)題. Zhang 等[14]認(rèn)為現(xiàn)有的相似性度量方法往往只適用于某幾種網(wǎng)絡(luò), 為此提出了一種g-衰減理論來(lái)統(tǒng)一現(xiàn)有的相似性度量方法, 同時(shí)還提出了一種基于圖神經(jīng)網(wǎng)絡(luò)(graph neural network, GNN)[15]的鏈接預(yù)測(cè)框架SEAL, 從網(wǎng)絡(luò)中的局部子圖來(lái)學(xué)習(xí)節(jié)點(diǎn)表示以進(jìn)行鏈接預(yù)測(cè). 以上方法大多是針對(duì)特定網(wǎng)絡(luò)提出了新的相似性度量方法. 除此之外, Ostapuk 等[16]首次將深度主動(dòng)學(xué)習(xí)[17]應(yīng)用于鏈接預(yù)測(cè), 基于貝葉斯深度學(xué)習(xí)[18]提出了一種深度主動(dòng)學(xué)習(xí)框架ActiveLink, 將不確定性采樣引入到聚類算法中,并且采用基于元學(xué)習(xí)[19]的無(wú)偏增量的方法進(jìn)行訓(xùn)練, 提高了模型的訓(xùn)練速率. 相較于傳統(tǒng)的基于網(wǎng)絡(luò)結(jié)構(gòu)相似度的鏈接預(yù)測(cè)方法而言, 有監(jiān)督的機(jī)器學(xué)習(xí)模型使鏈接預(yù)測(cè)的結(jié)果有了明顯提升.

由于真實(shí)世界中的網(wǎng)絡(luò)是隨時(shí)間不斷演化的,因此雖然上述方法在大規(guī)模網(wǎng)絡(luò)的鏈接預(yù)測(cè)中取得了較好的成果, 但其大多僅考慮了網(wǎng)絡(luò)結(jié)構(gòu)且大多只適用于靜態(tài)網(wǎng)絡(luò), 而忽視了真實(shí)網(wǎng)絡(luò)中的動(dòng)態(tài)信息以及節(jié)點(diǎn)間產(chǎn)生鏈接的時(shí)間信息, 因而在網(wǎng)絡(luò)發(fā)生變化時(shí)需要進(jìn)行大量的重新計(jì)算.

2.2 動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)

由于復(fù)雜網(wǎng)絡(luò)通常包含數(shù)十億的節(jié)點(diǎn)和邊, 且數(shù)據(jù)具有稀疏性, 在網(wǎng)絡(luò)上很難直接進(jìn)行復(fù)雜的推理過(guò)程, 為了有效地進(jìn)行復(fù)雜網(wǎng)絡(luò)分析, 學(xué)者們提出了各種各樣的網(wǎng)絡(luò)表示學(xué)習(xí)[20]方法. 網(wǎng)絡(luò)表示學(xué)習(xí)作為網(wǎng)絡(luò)分析領(lǐng)域的一個(gè)重要基礎(chǔ)問(wèn)題, 其核心思想是尋找一個(gè)映射函數(shù)將網(wǎng)絡(luò)中的節(jié)點(diǎn)轉(zhuǎn)化成低維稠密的實(shí)數(shù)向量, 即網(wǎng)絡(luò)節(jié)點(diǎn)表示. 這些網(wǎng)絡(luò)節(jié)點(diǎn)表示保存了網(wǎng)絡(luò)中所包含的信息, 為網(wǎng)絡(luò)分析任務(wù)提供了良好的特征基礎(chǔ), 并可以直接用于各種網(wǎng)絡(luò)分析任務(wù)中, 如鏈接預(yù)測(cè), 社團(tuán)檢驗(yàn), 推薦系統(tǒng)等. 網(wǎng)絡(luò)表示學(xué)習(xí)的形式化定義如下:

對(duì)于給定網(wǎng)絡(luò) G=(V,E) , 使用映射函數(shù)fv→τk為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn) v∈V 學(xué)習(xí)到一個(gè)低維稠密的實(shí)數(shù)向量 Rv∈Rk作為節(jié)點(diǎn)的表示向量,該向量的維度 k 遠(yuǎn)遠(yuǎn)小于網(wǎng)絡(luò)節(jié)點(diǎn)的總個(gè)數(shù) |V| .

由于網(wǎng)絡(luò)表示在常見(jiàn)的網(wǎng)絡(luò)分析任務(wù)中展現(xiàn)出了良好的能力, 因此越來(lái)越多的學(xué)者關(guān)注于網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域, 并提出了多種網(wǎng)絡(luò)表示學(xué)習(xí)方法,如DeepWalk[21], LINE[22], node2vec[23], SDNE[24],GCN[25], GraphSAGE[26]等.

近年來(lái), 針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)研究逐漸受到了研究人員的關(guān)注. 如Michael 等[27]基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)以及多元微分方程定義節(jié)點(diǎn)在不同時(shí)刻的表示, 提出了一種復(fù)雜網(wǎng)絡(luò)的多尺度動(dòng)態(tài)嵌入技術(shù). Kumar 等[28]基于遞歸神經(jīng)網(wǎng)絡(luò)提出了JODIE模型, 對(duì)網(wǎng)絡(luò)中的用戶和項(xiàng)目分別進(jìn)行動(dòng)態(tài)表示學(xué)習(xí), 并提出了一種并行批處理算法t-Batch. 李志宇等[29]通過(guò)對(duì)不同階層的網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系進(jìn)行正負(fù)阻尼采樣, 構(gòu)建針對(duì)新增節(jié)點(diǎn)的動(dòng)態(tài)特征學(xué)習(xí)方法, 使得模型可以提取大規(guī)模社會(huì)網(wǎng)絡(luò)在動(dòng)態(tài)變化過(guò)程中的結(jié)構(gòu)特征. Palash 等[30]基于深度自編碼器提出DynGEM 模型, 該模型可以動(dòng)態(tài)學(xué)習(xí)網(wǎng)絡(luò)中高度非線性的表示. 同時(shí)很多學(xué)者針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)中的鏈接預(yù)測(cè)任務(wù)進(jìn)行了相關(guān)研究.Chen 等[31]將長(zhǎng)短期記憶網(wǎng)絡(luò)[32](LSTM)與編碼器-解碼器體系結(jié)構(gòu)相結(jié)合, 提出了一種新穎的encoder-LSTM-decoder(E-LSTM-D)深度學(xué)習(xí)模型來(lái)預(yù)測(cè)動(dòng)態(tài)鏈接. Li 等[33]基于SDNE 算法提出了DDNE 模型, 使用門控循環(huán)單元[34](GRU)作為編碼器來(lái)捕獲動(dòng)態(tài)網(wǎng)絡(luò)中的時(shí)間信息, 從而在動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測(cè). Lei 等[35]結(jié)合了圖卷積網(wǎng)絡(luò)(graph convolutional network, GCN)、長(zhǎng)短期記憶網(wǎng)絡(luò)(long short-term memory, LSTM)以及生成對(duì)抗網(wǎng)絡(luò)[36](generative adversarial networks,GAN)的優(yōu)勢(shì), 用深度神經(jīng)網(wǎng)絡(luò)(即GCN 和LSTM)來(lái)探索網(wǎng)絡(luò)中隱藏的拓?fù)浣Y(jié)構(gòu)和演化模式的非線性特征, 用GAN 來(lái)解決動(dòng)態(tài)網(wǎng)絡(luò)中鏈接的稀疏性問(wèn)題, 同時(shí)通過(guò)對(duì)抗的方式在動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測(cè). 這些研究方法大多只考慮了發(fā)生變化的節(jié)點(diǎn)本身的信息變化情況, 而沒(méi)有關(guān)注節(jié)點(diǎn)鄰域所受到的影響. 并且現(xiàn)有方法大多僅考慮了均勻間隔的時(shí)間間隔, 而忽視了不同時(shí)間間隔對(duì)節(jié)點(diǎn)偏好信息的影響. 由于網(wǎng)絡(luò)表示學(xué)習(xí)是網(wǎng)絡(luò)分析的基礎(chǔ)任務(wù), 如何設(shè)計(jì)具有動(dòng)態(tài)適應(yīng)性的網(wǎng)絡(luò)表示學(xué)習(xí)模型, 學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)及其鄰域的信息變化并對(duì)它們的表示進(jìn)行快速更新, 對(duì)現(xiàn)實(shí)世界中的網(wǎng)絡(luò)分析任務(wù)有著至關(guān)重要的作用.

3 基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)模型

本文針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的鏈接預(yù)測(cè)問(wèn)題提出了基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)模型DNRLP. 該模型對(duì)LSTM 進(jìn)行了改進(jìn), 考慮了網(wǎng)絡(luò)演化過(guò)程中產(chǎn)生新信息的非平均時(shí)間間隔問(wèn)題以及新信息的擴(kuò)散問(wèn)題, 有效地捕獲和學(xué)習(xí)了網(wǎng)絡(luò)中的動(dòng)態(tài)信息,并得到了含有節(jié)點(diǎn)偏好信息的節(jié)點(diǎn)表示. 然后通過(guò)計(jì)算習(xí)得節(jié)點(diǎn)表示之間的相似度, 最終得到鏈接預(yù)測(cè)的結(jié)果.

圖2 基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)模型結(jié)構(gòu)Fig. 2. The architecture of link prediction model based on dynamic network representation.

圖2 給出DNRLP 模型的結(jié)構(gòu)示意圖, DNRLP模型主要分為兩個(gè)模塊: 動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)模塊和鏈接預(yù)測(cè)模塊, 其中動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)模塊由節(jié)點(diǎn)信息動(dòng)態(tài)更新單元和節(jié)點(diǎn)鄰域更新單元組成.DNRLP 模型根據(jù) Ti時(shí)刻網(wǎng)絡(luò)中出現(xiàn)的新增信息,得到與其直接關(guān)聯(lián)的節(jié)點(diǎn)集合, 使用節(jié)點(diǎn)信息動(dòng)態(tài)更新單元對(duì)該集合內(nèi)的節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)表示更新. 然后對(duì)該集合內(nèi)的節(jié)點(diǎn)進(jìn)行鄰域采樣, 得到與新增信息間接關(guān)聯(lián)的節(jié)點(diǎn)集合, 使用節(jié)點(diǎn)鄰域更新單元對(duì)鄰域節(jié)點(diǎn)進(jìn)行更新, 最終得到當(dāng)前時(shí)刻更新后的網(wǎng)絡(luò)節(jié)點(diǎn)表示. 基于這些節(jié)點(diǎn)表示使用鏈接預(yù)測(cè)模塊計(jì)算節(jié)點(diǎn)間的相似度并進(jìn)行排序, 最終得到鏈接預(yù)測(cè)的結(jié)果.

3.1 節(jié)點(diǎn)信息動(dòng)態(tài)更新

隨時(shí)間動(dòng)態(tài)演化的網(wǎng)絡(luò)可以看作不同時(shí)刻下的靜態(tài)網(wǎng)絡(luò), 使用 G(Vt,Et,t)表示 t 時(shí)刻的網(wǎng)絡(luò),其中 Vt為該時(shí)刻的節(jié)點(diǎn)集合, Et為該時(shí)刻的邊集合, t 為對(duì)應(yīng)的時(shí)間戳. 隨著時(shí)間的推移, 網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)不斷地與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)建立新鏈接, 這些新鏈接會(huì)改變當(dāng)前節(jié)點(diǎn)的屬性信息. 例如在社交網(wǎng)絡(luò)中, 如果兩個(gè)用戶有聯(lián)系, 他們會(huì)逐漸分享共同的興趣愛(ài)好. 新鏈接的建立順序以及它們建立的時(shí)間間隔對(duì)節(jié)點(diǎn)屬性特征的變化也有著非常重要的影響. 按照時(shí)間戳對(duì)節(jié)點(diǎn) v 新產(chǎn)生的鏈接進(jìn)行排序得到鏈接序列 Sv={(v,vi,t0),(v,vi,t1),...,(v,vi,tn)}, 其中 (v,vi,t)表示 t時(shí)刻節(jié)點(diǎn) v與節(jié)點(diǎn) vi之間新建立的鏈接, vi∈Nv表示節(jié)點(diǎn) v 的一階鄰域節(jié)點(diǎn), Nv表示節(jié)點(diǎn) v的一階鄰域節(jié)點(diǎn)集合; t 表示鏈接建立的時(shí)間戳, t0

綜上所述, 針對(duì)網(wǎng)絡(luò)中的任一節(jié)點(diǎn), 當(dāng)產(chǎn)生新鏈接時(shí), 應(yīng)該根據(jù)鏈接產(chǎn)生的時(shí)間間隔決定需要更新哪些新信息, 以及需要遺忘哪些歷史信息.DNRLP 模型基于LSTM 模型對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)表示學(xué)習(xí). LSTM 模型通過(guò)遺忘門、輸入門和輸出門解決了對(duì)歷史信息的長(zhǎng)期依賴問(wèn)題. 但是現(xiàn)有的LSTM 中沒(méi)有考慮不同的時(shí)間間隔對(duì)歷史信息丟棄策略所產(chǎn)生的影響, 因此我們根據(jù)動(dòng)態(tài)網(wǎng)絡(luò)信息傳播規(guī)律, 在LSTM 的計(jì)算過(guò)程中增加了一個(gè)基于時(shí)間間隔的信息過(guò)濾單元(time interval based filter unit, TIFU), 從而達(dá)到了根據(jù)時(shí)間間隔的大小決定下一時(shí)刻節(jié)點(diǎn)對(duì)歷史信息的丟棄程度的目的, 使模型更關(guān)注節(jié)點(diǎn)的新增信息, 其計(jì)算單元如圖3 所示.

圖3 基于時(shí)間間隔的LSTM 單元Fig. 3. Time interval based LSTM unit.

圖3 左半部分描述了TIFU 的示意圖. TIFU的工作原理是根據(jù)時(shí)間間隔 ?t的大小, 決定當(dāng)前細(xì)胞狀態(tài)信息Ct?1傳遞到下一時(shí)刻t的信息的具體計(jì)算過(guò)程如下所示:上述公式中, TIFU 將上一時(shí)刻t ?1 標(biāo)準(zhǔn)LSTM計(jì)算單元輸出的細(xì)胞狀態(tài)Ct?1分成了兩個(gè)部分:短期記憶和長(zhǎng)期記憶. 我們認(rèn)為細(xì)胞狀態(tài)Ct?1是由長(zhǎng)期記憶和短期記憶兩個(gè)部分構(gòu)成的,短期記憶對(duì)信息的存儲(chǔ)時(shí)間較短, 容易被遺忘, 而長(zhǎng)期記憶對(duì)信息的存儲(chǔ)時(shí)間較長(zhǎng), 不容易被遺忘.同時(shí)短期記憶與長(zhǎng)期記憶并不是完全割裂的, 通過(guò)重復(fù)、鞏固短期記憶可以轉(zhuǎn)化為長(zhǎng)期記憶, 即隨著時(shí)間的流逝, 部分短期記憶可以演變?yōu)殚L(zhǎng)期記憶.(1)式使用神經(jīng)網(wǎng)絡(luò)和tanh 激活函數(shù)自動(dòng)選擇歷史信息中較為短暫的歷史信息, 即單元的短期記憶, 其中為根據(jù)t ?1 時(shí)刻的細(xì)胞狀態(tài)生成的短期記憶. (2)式中為相應(yīng)的需要傳遞給下一時(shí)刻t的長(zhǎng)期記憶. TIFU 根據(jù)時(shí)間間隔 ?t對(duì)單元短期記憶的部分信息進(jìn)行丟棄, 如(3)式所示, 其中為保留下來(lái)的短期記憶信息, ?t越大丟棄的短期記憶信息越多. 經(jīng)過(guò)上述計(jì)算, 完成對(duì)節(jié)點(diǎn)歷史信息保留的決策, 并得到需要傳遞給下一時(shí)刻t的歷史信息, 如(4)式所示,將和進(jìn)行組合, 并作為下一時(shí)刻t標(biāo)準(zhǔn)LSTM 單元的輸入, 即最終傳遞給下一時(shí)刻t的節(jié)點(diǎn)歷史信息是由節(jié)點(diǎn)的部分短期記憶與全部長(zhǎng)期記憶所組成的.

圖3 中右半部分為標(biāo)準(zhǔn)LSTM 計(jì)算單元示意圖, 其具體計(jì)算過(guò)程如下所示:

其中xt為當(dāng)前時(shí)刻t的輸入向量, 表示網(wǎng)絡(luò)的新增信息. 由于新增信息由節(jié)點(diǎn)vi,vj之間的新增鏈接產(chǎn)生, 因此可以通過(guò)計(jì)算兩節(jié)點(diǎn)當(dāng)前表示的加權(quán)和來(lái)得到xt, 計(jì)算方式如(5)式所示. 接下來(lái)分別對(duì)標(biāo)準(zhǔn)LSTM 單元的輸入門、遺忘門及輸出門進(jìn)行計(jì)算, 其中σ表示sigmoid 激活函數(shù),⊙表示矩陣乘積運(yùn)算,it,ft,ot分別代表t時(shí)刻LSTM 單元輸入門、遺忘門以及輸出門的系數(shù).{Wi,Ui,bi},{Wf,Uf,bf}和{Wo,Uo,bo}分為上述三種門的網(wǎng)絡(luò)參數(shù).表示用于更新細(xì)胞狀態(tài)ct的候選狀態(tài).{Wc,Uc,bc}是網(wǎng)絡(luò)產(chǎn)生候選記憶的參數(shù).ht是在時(shí)刻t時(shí)經(jīng)過(guò)上述三種門的過(guò)濾后的隱藏狀態(tài), 該狀態(tài)記錄了t時(shí)刻之前習(xí)得的所有有用信息.ct經(jīng)過(guò)輸出門舍棄掉部分信息后形成當(dāng)前時(shí)刻t的輸出向量ht. 根據(jù)上述TIFU 和標(biāo)準(zhǔn)LSTM 計(jì)算單元的計(jì)算過(guò)程, 可將上述過(guò)程進(jìn)行如下表示:

當(dāng)網(wǎng)絡(luò)中有新信息產(chǎn)生時(shí), 使用f對(duì)關(guān)系兩端的節(jié)點(diǎn)信息(節(jié)點(diǎn)表示)進(jìn)行更新, 其中Ct?1,ht?1為上一時(shí)刻f計(jì)算得到的細(xì)胞狀態(tài)和隱藏狀態(tài),xt=W1uvi+W2uvj+b是網(wǎng)絡(luò)新增關(guān)系為涉及到的兩個(gè)節(jié)點(diǎn)vi和vj帶來(lái)的新信息,W1,W2,b是生成新信息的表示向量的模型參數(shù).ht即為目標(biāo)節(jié)點(diǎn)更新后的表示向量.

針對(duì)模型冷啟動(dòng)問(wèn)題, 在初始時(shí)刻, DNRLP模型使用網(wǎng)絡(luò)的鄰接矩陣作為網(wǎng)絡(luò)節(jié)點(diǎn)的表示向量, 并對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)進(jìn)行固定大小的鄰域采樣, 然后使用聚合函數(shù)對(duì)節(jié)點(diǎn)鄰域內(nèi)的節(jié)點(diǎn)表示進(jìn)行聚合, 最終得到節(jié)點(diǎn)初始化表示向量, 并使用上述表示向量作為f的初始化的節(jié)點(diǎn)表示.

3.2 節(jié)點(diǎn)信息擴(kuò)散算法和更新

網(wǎng)絡(luò)中兩節(jié)點(diǎn)vi,vj之間的新增鏈接不僅會(huì)對(duì)鏈接兩端的節(jié)點(diǎn)產(chǎn)生影響, 同時(shí)也會(huì)影響與vi,vj距離較近的節(jié)點(diǎn). 因此當(dāng)網(wǎng)絡(luò)產(chǎn)生新鏈接時(shí), 涉及到的兩個(gè)節(jié)點(diǎn)vi,vj的鄰域節(jié)點(diǎn)也應(yīng)該進(jìn)行信息更新. 為此, DNRLP 模型通過(guò)對(duì)產(chǎn)生新鏈接的節(jié)點(diǎn)進(jìn)行鄰域采樣來(lái)模擬新信息在網(wǎng)絡(luò)中的擴(kuò)散過(guò)程,然后對(duì)采樣到的鄰域節(jié)點(diǎn)進(jìn)行信息更新. 這么做的原因主要有三個(gè)方面: 第一, 文獻(xiàn)[37]表明新鏈接對(duì)整個(gè)網(wǎng)絡(luò)的影響往往是局部的. 第二, 由于網(wǎng)絡(luò)的復(fù)雜性, 與新鏈接直接關(guān)聯(lián)的節(jié)點(diǎn)不一定會(huì)將收集到的新信息傳播給其所有的鄰居, 同時(shí)新信息很有可能會(huì)被傳播到與其較近但不直接相鄰的節(jié)點(diǎn).第三, 通過(guò)實(shí)驗(yàn)發(fā)現(xiàn), 當(dāng)對(duì)目標(biāo)節(jié)點(diǎn)的局部鄰域進(jìn)行信息更新時(shí), 模型的性能會(huì)更好.

在節(jié)點(diǎn)鄰域采樣的過(guò)程中, DNRLP 模型采用基于連接強(qiáng)度的隨機(jī)游走算法. 把節(jié)點(diǎn)間的連接強(qiáng)度作為隨機(jī)游走中的邊權(quán)重, 對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行加權(quán)隨機(jī)游走采樣從而得到節(jié)點(diǎn)vi,vj的局部鄰域. 其中邊權(quán)重的計(jì)算過(guò)程如下:

其中,uv為節(jié)點(diǎn)v的表示向量,Nv表示節(jié)點(diǎn)v的一階鄰居節(jié)點(diǎn)集合,fs(uvi,uv)表示節(jié)點(diǎn)v和其鄰域節(jié)點(diǎn)vi間的連接強(qiáng)度, 可以將該連接強(qiáng)度看作一個(gè)歸一化后的概率值, 根據(jù)該概率值來(lái)選擇目標(biāo)節(jié)點(diǎn)信息在下一時(shí)刻要擴(kuò)散到的節(jié)點(diǎn). 圖4 給出一個(gè)簡(jiǎn)單網(wǎng)絡(luò)實(shí)例, 圖中實(shí)線代表歷史鏈接, 虛線代表當(dāng)前時(shí)刻新產(chǎn)生的鏈接. 分別對(duì)網(wǎng)絡(luò)中新鏈接兩端的節(jié)點(diǎn)v4,v5進(jìn)行隨機(jī)游走. 以節(jié)點(diǎn)v5的隨機(jī)游走鄰域采樣為例, 其具體的隨機(jī)游走采樣策略如下:

圖4 節(jié)點(diǎn)鄰域采樣示意圖Fig. 4. Schematic diagram of node neighborhood sampling.

(1)建立隨機(jī)游走結(jié)果集合Rv5={}.

(2)根據(jù)邊權(quán)重概率分布隨機(jī)選擇下一節(jié)點(diǎn)v1,并將該節(jié)點(diǎn)加入Rv5中.

(3)判斷所選節(jié)點(diǎn)v1是否有一階鄰居, 或者其一階鄰居是否全部在Rv5中, 是則退回到上一時(shí)刻的節(jié)點(diǎn)重復(fù)此步驟, 否則進(jìn)入下一步.

(4)重復(fù)步驟(2)和(3)直到隨機(jī)游走的結(jié)果集合達(dá)到期望的長(zhǎng)度.

(5)若隨機(jī)游走過(guò)程中選擇的節(jié)點(diǎn)與結(jié)果集合中的節(jié)點(diǎn)重復(fù), 則退回到上一時(shí)刻的節(jié)點(diǎn)重新進(jìn)行選擇. 如圖中節(jié)點(diǎn)v2下一刻游走選擇節(jié)點(diǎn)v5, 則退回到節(jié)點(diǎn)v2重新進(jìn)行決策.

表1 給出了擴(kuò)散算法的偽代碼. 在表1 中,Enew代表新增鏈接的集合;v代表與新增鏈接相關(guān)聯(lián)的一個(gè)節(jié)點(diǎn);m代表隨機(jī)游走了的長(zhǎng)度;L是給定的隨機(jī)游走序列的最大長(zhǎng)度;P表示邊權(quán)重概率分布;u代表節(jié)點(diǎn)v的一階鄰居;Rv代表節(jié)點(diǎn)v的隨機(jī)游走結(jié)果集合;R代表所有節(jié)點(diǎn)的隨機(jī)游走結(jié)果集合. 步驟6—8 實(shí)現(xiàn)節(jié)點(diǎn)間邊權(quán)重的計(jì)算. 步驟9 實(shí)現(xiàn)相關(guān)節(jié)點(diǎn)的鄰域采樣. 步驟4—12 實(shí)現(xiàn)基于連接強(qiáng)度的隨機(jī)游走算法, 找到了相關(guān)節(jié)點(diǎn)的局部鄰域Rv, 其中Rv是一個(gè)有序的隨機(jī)游走序列,越靠前的節(jié)點(diǎn)越容易從相關(guān)節(jié)點(diǎn)到達(dá), 即相關(guān)節(jié)點(diǎn)的信息更容易擴(kuò)散到序列中排位靠前的節(jié)點(diǎn)上去,刻畫(huà)出了相關(guān)節(jié)點(diǎn)信息的擴(kuò)散過(guò)程. 整個(gè)算法得到了與新增信息直接相關(guān)的節(jié)點(diǎn)的隨機(jī)游走序列Rv的集合R, 描繪出了整個(gè)網(wǎng)絡(luò)中新增信息的擴(kuò)散過(guò)程.

表1 信息擴(kuò)散算法Table 1. Information diffusion algorithm.

由于新增鏈接并沒(méi)有對(duì)隨機(jī)游走序列中的節(jié)點(diǎn)產(chǎn)生直接影響, 因此新增鏈接的信息并沒(méi)有影響這些節(jié)點(diǎn)的歷史信息, 只帶來(lái)了新信息, 并且對(duì)于相關(guān)節(jié)點(diǎn)局部鄰域中較老、較遠(yuǎn)的節(jié)點(diǎn)(較老的節(jié)點(diǎn): 相關(guān)節(jié)點(diǎn)與其的交互發(fā)生在比較早先的時(shí)候或者其與隨機(jī)游走序列中的上一個(gè)節(jié)點(diǎn)之間的交互發(fā)生在比較早先的時(shí)候; 較遠(yuǎn)的節(jié)點(diǎn): 相關(guān)節(jié)點(diǎn)與其的距離比較遠(yuǎn))而言, 新信息對(duì)其影響較小. 綜上, DNRLP 模型根據(jù)相關(guān)節(jié)點(diǎn)與其隨機(jī)游走序列中的節(jié)點(diǎn)之間的鏈接存在的時(shí)間長(zhǎng)短, 或者根據(jù)隨機(jī)游走序列中相鄰兩節(jié)點(diǎn)之間鏈接存在的時(shí)間長(zhǎng)短, 對(duì)新信息進(jìn)行處理. 建立鏈接的時(shí)間越長(zhǎng), 需要丟棄的新增信息越多. 同時(shí)還使用相關(guān)節(jié)點(diǎn)與其隨機(jī)游走序列中節(jié)點(diǎn)之間的距離對(duì)新信息進(jìn)行進(jìn)一步的處理.

DNRLP 模型設(shè)計(jì)了節(jié)點(diǎn)鄰域更新單元對(duì)新信息涉及到的相關(guān)節(jié)點(diǎn)vi的隨機(jī)游走序列進(jìn)行信息更新, 更新過(guò)程如下:

式 中,v ∈Rv,indv為 節(jié) 點(diǎn)v在Rv中 的 索 引 號(hào),為節(jié)點(diǎn)v上一時(shí)刻的細(xì)胞狀態(tài),xt=W1uvi+W2uvj+b為節(jié)點(diǎn)vi和vj之間新增關(guān)系產(chǎn)生的新信息. 更新后節(jié)點(diǎn)v的表示向量為. 上述相關(guān)節(jié)點(diǎn)鄰域信息更新單元的結(jié)構(gòu)如圖5 所示.

3.3 參數(shù)訓(xùn)練

圖5 節(jié)點(diǎn)鄰域更新單元Fig. 5. Node neighborhood update unit.

為了在無(wú)監(jiān)督方式下進(jìn)行參數(shù)學(xué)習(xí), DNRLP模型將輸出的節(jié)點(diǎn)表示向量hv,v ∈V應(yīng)用于基于圖的損失函數(shù), 并使用梯度下降法對(duì)模型參數(shù)進(jìn)行更新. 基于圖的損失函數(shù)假設(shè)相互連接的節(jié)點(diǎn)有著相似的網(wǎng)絡(luò)表示向量, 損失函數(shù)如下:

3.4 基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)

在網(wǎng)絡(luò)中相似節(jié)點(diǎn)在未來(lái)發(fā)生鏈接的可能性更大, 因此, 本文通過(guò)度量網(wǎng)絡(luò)節(jié)點(diǎn)之間的相似度來(lái)進(jìn)行網(wǎng)絡(luò)鏈接預(yù)測(cè). 通過(guò)上述動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)過(guò)程, 我們可以得到每次網(wǎng)絡(luò)演化后的新節(jié)點(diǎn)偏好表示, 這些節(jié)點(diǎn)表示保存了節(jié)點(diǎn)的偏好信息, 可以直接進(jìn)行節(jié)點(diǎn)間的相似度計(jì)算, 計(jì)算過(guò)程如下:

其中,hv和hu表示兩個(gè)節(jié)點(diǎn)在當(dāng)前時(shí)刻的表示向量,i和j表示節(jié)點(diǎn)偏好表示向量的分量. 相似度越大, 則節(jié)點(diǎn)間發(fā)生鏈接的可能性越大, 因此對(duì)網(wǎng)絡(luò)目標(biāo)節(jié)點(diǎn)進(jìn)行鏈接預(yù)測(cè)時(shí), DNRLP 模型首先會(huì)計(jì)算該節(jié)點(diǎn)與網(wǎng)絡(luò)中的其余節(jié)點(diǎn)之間的相似度并對(duì)其進(jìn)行排序, 選擇top-k 的節(jié)點(diǎn)作為最終鏈接預(yù)測(cè)的結(jié)果.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證DNRLP 模型在網(wǎng)絡(luò)鏈接預(yù)測(cè)任務(wù)下的性能和有效性, 本文在具有代表性的四個(gè)公開(kāi)動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn). 這四個(gè)數(shù)據(jù)集的數(shù)據(jù)統(tǒng)計(jì)信息如表2 所示.

表2 動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)詳細(xì)信息Table 2. Dynamic network data details.

其中, UCI[38]是由加利福尼亞大學(xué)歐文分校的在線學(xué)生社區(qū)的用戶之間的消息通信而組成的網(wǎng)絡(luò). 網(wǎng)絡(luò)中的節(jié)點(diǎn)表示社區(qū)用戶, 如果用戶之間有消息通信, 那么用戶之間就會(huì)有邊連接, 與每條邊相關(guān)聯(lián)的時(shí)間表示用戶之間的通信時(shí)間. DNC 是2016 年民主黨全國(guó)委員會(huì)電子郵件泄漏的電子郵件通信網(wǎng)絡(luò). 網(wǎng)絡(luò)中的節(jié)點(diǎn)代表人員, 邊代表人員之間的郵件交互. Wikipedia talk, Chinese(Wikipedia)[39]是中文維基百科的通訊網(wǎng)絡(luò), 節(jié)點(diǎn)表示中文維基百科的用戶, 邊表示在某一時(shí)刻某一用戶在另一用戶的對(duì)話頁(yè)上發(fā)送了一條消息.Enron[40]是由Enron 員工之間發(fā)送的電子郵件所組成的電子郵件網(wǎng)絡(luò). 和DNC 一樣, 網(wǎng)絡(luò)中的節(jié)點(diǎn)代表員工, 邊代表電子郵件. 這些數(shù)據(jù)集涵蓋了多種情況, 例如: UCI 和DNC 的節(jié)點(diǎn)數(shù)和邊數(shù)較少, 而聚類程度較高, 形成較為密集的小網(wǎng)絡(luò). 但是它們?cè)诔掷m(xù)時(shí)間上又有所不同, UCI 的持續(xù)時(shí)間短, 而DNC 的持續(xù)時(shí)間較長(zhǎng). Enron 是節(jié)點(diǎn)數(shù)和邊數(shù)較多, 聚類程度也較高的數(shù)據(jù)集, 形成較為密集的大網(wǎng)絡(luò). 而Wikipedia 是節(jié)點(diǎn)數(shù)和邊數(shù)很多,持續(xù)時(shí)間很長(zhǎng), 但聚類程度卻極低的數(shù)據(jù)集, 形成稀疏的大網(wǎng)絡(luò). 使用這些數(shù)據(jù)集, 我們可以對(duì)模型的魯棒性進(jìn)行測(cè)試.

根據(jù)表1 中所述的時(shí)序網(wǎng)絡(luò)數(shù)據(jù)得到t時(shí)刻的網(wǎng)絡(luò)拓?fù)鋱D以及時(shí)間信息, 使用平均交互排序(mean reciprocal rank, MRR)指標(biāo)評(píng)估鏈接預(yù)測(cè)任務(wù)的質(zhì)量. MRR 計(jì)算了測(cè)試集中真實(shí)節(jié)點(diǎn)的排名倒數(shù)的平均值, 其計(jì)算過(guò)程如下所示:

其中,H為測(cè)試集中的節(jié)點(diǎn)個(gè)數(shù), 將目標(biāo)節(jié)點(diǎn)與和其有真實(shí)連接的節(jié)點(diǎn)之間的余弦相似度進(jìn)行降序排序,ranki則表示了它們的余弦相似度在降序序列中所處的位置. 當(dāng)測(cè)試集中的節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間有真實(shí)連接時(shí), 其相似度排名應(yīng)盡可能靠前, 因此MRR值越大, 說(shuō)明鏈接預(yù)測(cè)的質(zhì)量越高, 即網(wǎng)絡(luò)表示越精準(zhǔn)有效. 實(shí)驗(yàn)按照時(shí)間順序選取前80%的數(shù)據(jù)作為模型的訓(xùn)練數(shù)據(jù), 后10%的數(shù)據(jù)作為驗(yàn)證數(shù)據(jù), 其余10%的數(shù)據(jù)作為測(cè)試數(shù)據(jù). 實(shí)驗(yàn)不但與現(xiàn)有的鏈接預(yù)測(cè)模型進(jìn)行了對(duì)比, 還與使用了不同信息擴(kuò)散策略的DNRLP 模型的變體進(jìn)行了比較. 并且, 為了驗(yàn)證DNRLP 模型的準(zhǔn)確性,我們還選取了不同數(shù)量的訓(xùn)練數(shù)據(jù)來(lái)與對(duì)比模型進(jìn)行對(duì)比. 對(duì)于測(cè)試集中的每個(gè)鏈接節(jié)點(diǎn)對(duì), 我們固定鏈接一端的節(jié)點(diǎn), 將其看作目標(biāo)節(jié)點(diǎn), 計(jì)算網(wǎng)絡(luò)中其余節(jié)點(diǎn)與該目標(biāo)節(jié)點(diǎn)的余弦相似度, 并進(jìn)行降序排列.

本文還使用Recall@k指標(biāo)來(lái)計(jì)算在測(cè)試數(shù)據(jù)集中真實(shí)鏈接占預(yù)測(cè)結(jié)果集中Top-k 的百分比,其計(jì)算過(guò)程如下所示:

其中σ{ranki?k}=1 表示在預(yù)測(cè)結(jié)果集中真實(shí)鏈接節(jié)點(diǎn)的排名ranki小于設(shè)定閾值k.Recall@k的值越大, 說(shuō)明鏈接預(yù)測(cè)任務(wù)的效果越好.

此外, 本文還使用Precision@k指標(biāo)來(lái)計(jì)算在測(cè)試數(shù)據(jù)集中預(yù)測(cè)結(jié)果占真實(shí)鏈接集中Top-k 的百分比, 其計(jì)算過(guò)程如下所示:

其中,σ{ranki?k}=1 表示在預(yù)測(cè)結(jié)果集中真實(shí)鏈接節(jié)點(diǎn)的排名ranki小于設(shè)定閾值k.Precision@k的值越大, 說(shuō)明鏈接預(yù)測(cè)任務(wù)的效果越好.

鑒于機(jī)器學(xué)習(xí)模型在鏈接預(yù)測(cè)任務(wù)中的優(yōu)異表現(xiàn), 以及網(wǎng)絡(luò)表示在常見(jiàn)的網(wǎng)絡(luò)分析任務(wù)中展現(xiàn)出的優(yōu)異能力, 本文分別使用基于機(jī)器學(xué)習(xí)的鏈接預(yù)測(cè)方法和基于網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)方法作為對(duì)比方法. 在基于機(jī)器學(xué)習(xí)的方法中, 我們選擇兩個(gè)經(jīng)典的機(jī)器學(xué)習(xí)模型, 支持向量機(jī)(SVM)模型和邏輯回歸(LR)模型. 在鏈接預(yù)測(cè)任務(wù)中, 將節(jié)點(diǎn)的特征向量作為SVM 和LR 模型的輸入, 通過(guò)節(jié)點(diǎn)的特征向量得到節(jié)點(diǎn)對(duì)的特征向量, 將節(jié)點(diǎn)對(duì)的特征向量分為有鏈接和無(wú)鏈接兩類, 從而將鏈接預(yù)測(cè)問(wèn)題轉(zhuǎn)變?yōu)闄C(jī)器學(xué)習(xí)中的二分類問(wèn)題. 在基于網(wǎng)絡(luò)表示的方法中, 主要通過(guò)計(jì)算節(jié)點(diǎn)表示之間的相似性來(lái)進(jìn)行鏈接預(yù)測(cè), 因此得到更為合適的節(jié)點(diǎn)表示是該類方法的主要目的. 為此我們分別選取了具有代表性的三個(gè)靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法和三個(gè)動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法來(lái)進(jìn)行對(duì)比, 靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法包括node2vec、GCN 和GraphSAGE, 動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法包括DynGEM、GCN-GAN和DDNE. Node2vec 是一種優(yōu)異的圖表示學(xué)習(xí)方法, 它利用隨機(jī)游走來(lái)捕獲網(wǎng)絡(luò)中的鄰近性, 并將所有節(jié)點(diǎn)映射到一個(gè)保持鄰近性的低維表示空間中. GCN 構(gòu)建了一個(gè)半監(jiān)督的節(jié)點(diǎn)嵌入模型, 通過(guò)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)節(jié)點(diǎn)特征進(jìn)行編碼, 從而得到了含有豐富信息的節(jié)點(diǎn)表示. GraphSAGE 通過(guò)訓(xùn)練聚合函數(shù)將GCN 擴(kuò)展到歸納學(xué)習(xí)任務(wù)中,使其可以直接泛化到未知節(jié)點(diǎn)上去. DynGEM 是一種針對(duì)時(shí)間間隔固定的動(dòng)態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)模型, 它學(xué)習(xí)到了含有時(shí)間信息的節(jié)點(diǎn)表示. GCNGAN 將GCN、LSTM 和GAN 相結(jié)合, 用GCN和來(lái)捕獲空間結(jié)構(gòu)信息, 用LSTM 來(lái)挖掘時(shí)間信息, 最后通過(guò)對(duì)抗的方式在動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測(cè). DDNE 用GRU 作為編碼器來(lái)捕獲動(dòng)態(tài)網(wǎng)絡(luò)中的時(shí)間信息, 從而在動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測(cè). 在上 述 模 型 中, SVM、 LR、 node2vec、 GCN 和GraphSAGE 是適用于靜態(tài)網(wǎng)絡(luò)的模型, 因此需要將動(dòng)態(tài)網(wǎng)絡(luò)轉(zhuǎn)化為靜態(tài)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn), 即將所有時(shí)刻的網(wǎng)絡(luò)信息拼接到一個(gè)網(wǎng)絡(luò)中. 而DynGEM、GCN-GAN、DDNE 以及我們提出的DNRLP 都是適用于動(dòng)態(tài)網(wǎng)絡(luò)的模型, 但DynGEM、GCNGAN 和DDNE 中的新鏈接建立的時(shí)間間隔是固定的, 因此在實(shí)驗(yàn)中我們忽略動(dòng)態(tài)網(wǎng)絡(luò)中不同大小的時(shí)間間隔. 實(shí)驗(yàn)使用網(wǎng)絡(luò)的鄰接矩陣作為模型的輸入特征, 將鄰接矩陣的行向量作為節(jié)點(diǎn)的特征向量. 本文中所有模型的統(tǒng)一實(shí)驗(yàn)環(huán)境如表3 所示.

實(shí)驗(yàn)中各模型的參數(shù)設(shè)置如下:

SVM, LR: 根據(jù)節(jié)點(diǎn)的特征向量得到節(jié)點(diǎn)對(duì)的特征向量, 將節(jié)點(diǎn)對(duì)的特征向量分為兩類: 有鏈接的標(biāo)為0, 無(wú)鏈接的標(biāo)為1. SVM 模型的核函數(shù)選用sigmoid 函數(shù), LR 模型則使用sag 優(yōu)化算法來(lái)進(jìn)行求解, 迭代次數(shù)設(shè)定為100.

表3 實(shí)驗(yàn)環(huán)境設(shè)置信息Table 3. Experimental environment setup information.

node2vec: 將模型中隨機(jī)游走的數(shù)量定為20,隨機(jī)游走的步長(zhǎng)定為40, 語(yǔ)言模型Skip-Gram 的窗口大小設(shè)定為10, 最終輸出的網(wǎng)絡(luò)表示維度為128.

GCN: 將模型中的圖卷積網(wǎng)絡(luò)層數(shù)設(shè)定為2,訓(xùn)練過(guò)程迭代次數(shù)設(shè)定為500, 學(xué)習(xí)率設(shè)定為0.01,輸出網(wǎng)絡(luò)表示的維度設(shè)定為128.

GraphSAGE: 將模型中的搜索深度設(shè)定為2,鄰域采樣數(shù)量設(shè)定為20, 學(xué)習(xí)率設(shè)定為0.01, 輸出網(wǎng)絡(luò)表示的維度設(shè)定為128.

DynGEM: 將模型中深度編碼器的隱藏層層數(shù)設(shè)定為2, 隱藏層單元數(shù)分別設(shè)定為[256, 128],輸出的網(wǎng)絡(luò)表示維度設(shè)定為128.

GCN-GAN: 將模型中的圖卷積網(wǎng)絡(luò)層數(shù)設(shè)定為2, LSTM 隱藏層層數(shù)設(shè)定為2, 學(xué)習(xí)率設(shè)定為0.01, 輸出的網(wǎng)絡(luò)表示維度設(shè)定為128.

DDNE: 將模型中深度編碼器的隱藏層層數(shù)設(shè)定為2, 歷史窗口的大小設(shè)定為2, 學(xué)習(xí)率設(shè)定為0.01, 輸出的網(wǎng)絡(luò)表示維度設(shè)定為128.

DNRLP: 將模型中LSTM 中的隱藏單元數(shù)設(shè)定為128, 新信息擴(kuò)散過(guò)程中的隨機(jī)游走步長(zhǎng)設(shè)定為40, 輸出的網(wǎng)絡(luò)表示的維度設(shè)定為128.

4.2 結(jié)果分析

實(shí)驗(yàn)結(jié)果如表4 所示. 通過(guò)觀察對(duì)比結(jié)果可以看出基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈接預(yù)測(cè)方法比基于機(jī)器學(xué)習(xí)的鏈接預(yù)測(cè)方法更加有效. 這是因?yàn)榫W(wǎng)絡(luò)表示學(xué)習(xí)方法可以對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)間的關(guān)系進(jìn)行深入挖掘, 從而得到更加豐富的特征信息. 在基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈接預(yù)測(cè)方法中, node2vec 在四個(gè)數(shù)據(jù)集上均表現(xiàn)一般, 主要因?yàn)閚ode2vec 僅通過(guò)隨機(jī)游走來(lái)捕獲節(jié)點(diǎn)的鄰域結(jié)構(gòu), 沒(méi)有重視直接相連節(jié)點(diǎn)間的信息交互. 且其主要適用于靜態(tài)網(wǎng)絡(luò), 忽略了網(wǎng)絡(luò)中的動(dòng)態(tài)信息. DynGEM、GCN-GAN 和DDNE 模型是針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)模型, 它們引入了網(wǎng)絡(luò)中的動(dòng)態(tài)信息, 因而預(yù)測(cè)效果優(yōu)于node2vec, 這說(shuō)明了動(dòng)態(tài)信息在網(wǎng)絡(luò)演化中的重要性. 但是DynGEM 和DDNE 模型的預(yù)測(cè)效果不如或者與GCN 和GraphSAGE 的效果相似, 這是因?yàn)樗鼈儍H對(duì)網(wǎng)絡(luò)拓?fù)鋱D的鄰接矩陣進(jìn)行學(xué)習(xí), 只得到了網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)信息, 而忽略了網(wǎng)絡(luò)中的局部信息, 因而學(xué)習(xí)到的網(wǎng)絡(luò)特征并沒(méi)有GCN 和GraphSAGE 豐富. 而GCN 和GraphSAGE通過(guò)聚合鄰居節(jié)點(diǎn)的信息來(lái)模擬信息在節(jié)點(diǎn)間的擴(kuò)散過(guò)程, 既學(xué)習(xí)到了網(wǎng)絡(luò)中全局信息也學(xué)習(xí)到了局部信息, 這表明了局部特征在網(wǎng)絡(luò)中的重要性,同時(shí)也體現(xiàn)出GCN 和GraphSAGE 模型適用于聚類系數(shù)較高的鄰域信息豐富的網(wǎng)絡(luò). 但是GCN 和GraphSAGE 忽視了信息傳播隨時(shí)間的衰減, 沒(méi)有對(duì)信息進(jìn)行遺忘, 而GCN-GAN 既考慮到了網(wǎng)絡(luò)中的全局特征和局部特征, 又考慮到了網(wǎng)絡(luò)演化過(guò)程中的動(dòng)態(tài)信息, 因而效果優(yōu)于GCN 和GraphSAGE. 但是GCN-GAN 模型忽視了時(shí)間間隔對(duì)信息更新的影響, 而DNRLP 模型通過(guò)信息動(dòng)態(tài)更新模塊和信息擴(kuò)散模塊不僅學(xué)習(xí)到了網(wǎng)絡(luò)的動(dòng)態(tài)信息, 考慮到了節(jié)點(diǎn)鄰域所受的影響, 同時(shí)還考慮了時(shí)間間隔對(duì)信息更新的影響, 因此, 該模型在鏈接預(yù)測(cè)任務(wù)中較其他模型有明顯優(yōu)勢(shì). 此外,我們可以看到, 在Wikipedia 數(shù)據(jù)集上所有方法的表現(xiàn)均不佳, 這是因?yàn)樗木垲愊禂?shù)太低, 持續(xù)時(shí)間又太長(zhǎng), 給鏈接預(yù)測(cè)任務(wù)帶來(lái)了極大的挑戰(zhàn). 同時(shí)對(duì)比于其他數(shù)據(jù)集我們可以看出在聚類系數(shù)稍高的情況下, 我們的模型效果要遠(yuǎn)優(yōu)于其他所有模型.

表4 鏈接預(yù)測(cè)MRR 結(jié)果對(duì)比Table 4. Link prediction MRR results comparison.

本文還在四個(gè)數(shù)據(jù)集上對(duì)基于表示學(xué)習(xí)的鏈接預(yù)測(cè)方法中效果較好的幾個(gè)模型計(jì)算了其在不同k值下的Recall@k指標(biāo), 實(shí)驗(yàn)結(jié)果如圖6 所示.本文所提出的DNRLP 模型在不同k值下的鏈接預(yù)測(cè)效果均優(yōu)于對(duì)比模型. 同時(shí)隨著k值的不斷增大,Recall@k的值也在不斷增大. 我們可以看出,DynGEM 的預(yù)測(cè)效果與GraphSAGE 的效果相似, 并且在DCN 數(shù)據(jù)集中它的表現(xiàn)較差, 表明了學(xué)習(xí)局部信息的重要性. 而GraphSAGE 在DCN數(shù)據(jù)集中的表現(xiàn)優(yōu)異, 表明了GraphSAGE 強(qiáng)大的學(xué)習(xí)鄰域信息的能力, 也表明了GraphSAGE 適用于聚類系數(shù)較高的網(wǎng)絡(luò). 在不同k值下, GCNGAN 模型的預(yù)測(cè)效果基本位列第二, 表明了同時(shí)考慮空間信息與時(shí)間信息的重要性, 而GCNGAN 的預(yù)測(cè)效果要次于DNRLP, 表明了時(shí)間間隔在網(wǎng)絡(luò)演化過(guò)程中的重要性. 上述實(shí)驗(yàn)結(jié)果表明, DNRLP 模型可以更好的學(xué)習(xí)網(wǎng)絡(luò)中的節(jié)點(diǎn)信息, 得到含有全局信息、局部信息以及節(jié)點(diǎn)偏好信息的節(jié)點(diǎn)表示.

此外, 本文還對(duì)上述幾個(gè)模型計(jì)算了其在不同k值下的Precision@k指標(biāo), 實(shí)驗(yàn)結(jié)果如圖7 所示.我 們 可 以 看 出,Precision@k指 標(biāo) 與 Recall@k指標(biāo)的實(shí)驗(yàn)結(jié)果相似. 在DCN 數(shù)據(jù)集中, 所有方法的表現(xiàn)都比較好, 且當(dāng)k值較小時(shí), DNRLP 與GraphSAGE、GCN-GAN 的差別不大, 這是因?yàn)镈CN 數(shù)據(jù)的聚類系數(shù)較大, 網(wǎng)絡(luò)中的局部信息相對(duì)重要, 而這三個(gè)模型均可以通過(guò)聚合鄰居節(jié)點(diǎn)的信息來(lái)更新節(jié)點(diǎn)表示, 體現(xiàn)了學(xué)習(xí)網(wǎng)絡(luò)中局部信息的重要性. 相反在Wikipedia 數(shù)據(jù)集上所有方法的表現(xiàn)均不佳, 這是因?yàn)樗木垲愊禂?shù)太低, 持續(xù)時(shí)間又太長(zhǎng), 對(duì)進(jìn)行準(zhǔn)確的鏈接預(yù)測(cè)有很大的挑戰(zhàn).在四個(gè)數(shù)據(jù)集上, 本文所提出的DNRLP 模型在不同k值下的Precision@k指標(biāo)均優(yōu)于對(duì)比模型, 并且隨著k值的不斷增大,Precision@k的值也在不斷增大, 當(dāng)k值較大時(shí), 所提DNRLP 模型的優(yōu)勢(shì)更為明顯. 實(shí)驗(yàn)結(jié)果表明, 在動(dòng)態(tài)網(wǎng)絡(luò)中DNRLP模型可以更為準(zhǔn)確地進(jìn)行鏈接預(yù)測(cè).

圖6 各數(shù)據(jù)集上的 Recall@k 對(duì)比圖 (a) UCI 數(shù)據(jù)集; (b) DNC 數(shù)據(jù)集; (b) Wikipedia 數(shù)據(jù)集; (d) Enron 數(shù)據(jù)集Fig. 6. Recall@k comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset.

圖7 各數(shù)據(jù)集上的 Precision@k 對(duì)比圖 (a) UCI 數(shù)據(jù)集; (b) DNC 數(shù)據(jù)集; (b) Wikipedia 數(shù)據(jù)集; (d) Enron 數(shù)據(jù)集Fig. 7. Precision@k comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset.

為了驗(yàn)證DNRLP 模型中用基于連接強(qiáng)度的隨機(jī)游走算法模擬信息擴(kuò)散過(guò)程的有效性, 我們對(duì)模型的三個(gè)變體進(jìn)行了對(duì)比實(shí)驗(yàn). DNRLPprop 模型是加入了基于連接強(qiáng)度的隨機(jī)游走算法的鏈接預(yù)測(cè)模型. DNRLP-1 st 模型是使用節(jié)點(diǎn)在網(wǎng)絡(luò)中的一階鄰域模擬信息傳播過(guò)程的鏈接預(yù)測(cè)模型. DNRLP-org 模型為不考慮新信息在網(wǎng)絡(luò)中的傳播的鏈接預(yù)測(cè)模型. 對(duì)比實(shí)驗(yàn)結(jié)果如圖8 所示, 可以看出在四個(gè)數(shù)據(jù)集上, DNRLP-prop 模型的預(yù)測(cè)效果均優(yōu)于其他兩個(gè)變體模型, 且k值越大,Recall@k的值也越大, 而DNRLP-org 模型的預(yù)測(cè)效果最差. DNRLP-org 模型的低預(yù)測(cè)效果主要是因?yàn)樗雎粤诵畔⒃诰W(wǎng)絡(luò)中的擴(kuò)散過(guò)程, 沒(méi)有將新信息傳播到節(jié)點(diǎn)鄰域中去, 這表明了信息傳播在網(wǎng)絡(luò)中的重要性. DNRLP-prop 模型的預(yù)測(cè)效果優(yōu)于DNRLP-1st 模型的預(yù)測(cè)效果, 這主要是因?yàn)樾滦畔⒌臄U(kuò)散往往是局部性的, 不僅會(huì)對(duì)相關(guān)節(jié)點(diǎn)的一跳鄰居產(chǎn)生影響, 也會(huì)對(duì)與其距離較近的多跳鄰居產(chǎn)生影響. 實(shí)驗(yàn)結(jié)果表明, 動(dòng)態(tài)信息對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)有著至關(guān)重要的作用, 不僅對(duì)直接相關(guān)的節(jié)點(diǎn)有影響, 對(duì)其周圍一定范圍內(nèi)的節(jié)點(diǎn)也有影響. 使用基于連接強(qiáng)度的隨機(jī)游走算法可以有效地將網(wǎng)絡(luò)中的動(dòng)態(tài)信息更新到受影響的節(jié)點(diǎn)中去.

圖8 DNRLP 模型變體的Recall@k 對(duì)比圖 (a) UCI 數(shù)據(jù)集; (b) DNC 數(shù)據(jù)集; (c) Wikipedia 數(shù)據(jù)集; (d) Enron 數(shù)據(jù)集Fig. 8. Recall@k comparison diagram of the variants of DNRLP. (a) UCI dataset; (b) DNC dataset; (c) Wikipedia dataset;(d) Enron dataset.

圖9 不同訓(xùn)練率的MRR 結(jié)果對(duì)比圖 (a) DNC 數(shù)據(jù)集; (b) Enron 數(shù)據(jù)集Fig. 9. MRR results of different training rates. (a) DNC dataset; (b) Enron dataset.

此外, 為了驗(yàn)證DNRLP 模型的準(zhǔn)確性, 本文還選取了三個(gè)表現(xiàn)較好的模型計(jì)算了其在不同比率的訓(xùn)練樣本下的MRR 指標(biāo). 我們?cè)趦蓚€(gè)典型的數(shù)據(jù)集上, 按照時(shí)間順序分別選取前60%, 70%,80%, 90%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù), 其余的選擇10%作為測(cè)試數(shù)據(jù). 實(shí)驗(yàn)結(jié)果如圖9 所示, 可以看出在兩個(gè)數(shù)據(jù)集上, 隨著訓(xùn)練數(shù)據(jù)比率的增大,MRR 的值也在增大. 并且在任意比率下, DNRLP的訓(xùn)練效果均優(yōu)于對(duì)比模型, 表現(xiàn)了我們所提模型在鏈接預(yù)測(cè)任務(wù)中優(yōu)異的性能.

5 結(jié) 論

本文針對(duì)現(xiàn)實(shí)世界中動(dòng)態(tài)演化的網(wǎng)絡(luò)提出了一種基于動(dòng)態(tài)網(wǎng)絡(luò)表示的鏈接預(yù)測(cè)模型DNRLP.該模型根據(jù)動(dòng)態(tài)網(wǎng)絡(luò)的特性, 在標(biāo)準(zhǔn)LSTM 單元的基礎(chǔ)上引入了基于時(shí)間間隔的信息過(guò)濾單元, 來(lái)決策節(jié)點(diǎn)新、舊信息的去留. 此外, DNRLP 模型還考慮了新信息在直接相關(guān)節(jié)點(diǎn)鄰域內(nèi)的信息傳播問(wèn)題. 本文在四個(gè)動(dòng)態(tài)網(wǎng)絡(luò)公開(kāi)數(shù)據(jù)集上對(duì)模型的有效性進(jìn)行了驗(yàn)證, 實(shí)驗(yàn)結(jié)果表明網(wǎng)絡(luò)中的全局信息和局部信息對(duì)學(xué)習(xí)良好的網(wǎng)絡(luò)表示有非常重要的作用, 同時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中的時(shí)間信息以及動(dòng)態(tài)信息在網(wǎng)絡(luò)中的傳播對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)表示的更新有著極其重要的影響. DNRLP 模型可以學(xué)習(xí)到動(dòng)態(tài)網(wǎng)絡(luò)中豐富的信息, 能夠有效地對(duì)新信息進(jìn)行快速準(zhǔn)確地學(xué)習(xí), 在鏈接預(yù)測(cè)任務(wù)中表現(xiàn)出了明顯的優(yōu)勢(shì).

由于現(xiàn)實(shí)世界中的網(wǎng)絡(luò)通常含有多類異構(gòu)信息, 如社交網(wǎng)絡(luò)中, 除了含有用戶交互產(chǎn)生的網(wǎng)絡(luò)結(jié)構(gòu)信息以外, 每個(gè)用戶還具有不同的屬性信息,包括用戶的性別、年齡、愛(ài)好等. 如何將這些信息加入到鏈接預(yù)測(cè)中, 將是一個(gè)重要的研究方向.