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

1) (北京工商大學計算機與信息工程學院，北京 100048)

2) (北京工商大學食品安全大數(shù)據(jù)技術(shù)北京市重點實驗室，北京 100048)

1 引 言

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

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

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

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

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

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

2 相關(guān)研究

2.1 鏈接預(yù)測

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

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

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

2.2 動態(tài)網(wǎng)絡(luò)表示學習

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

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

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

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

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

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

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

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

3.1 節(jié)點信息動態(tài)更新

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

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

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

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

圖3 中右半部分為標準LSTM 計算單元示意圖, 其具體計算過程如下所示:

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

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

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

3.2 節(jié)點信息擴散算法和更新

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

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

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

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

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

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

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

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

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

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

表1 信息擴散算法Table 1. Information diffusion algorithm.

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

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

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

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

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

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

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

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

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

4 實驗分析

4.1 實驗設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GraphSAGE: 將模型中的搜索深度設(shè)定為2,鄰域采樣數(shù)量設(shè)定為20, 學習率設(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, 學習率設(shè)定為0.01, 輸出的網(wǎng)絡(luò)表示維度設(shè)定為128.

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

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

4.2 結(jié)果分析

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

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

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

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

圖6 各數(shù)據(jù)集上的 Recall@k 對比圖 (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 對比圖 (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.

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

圖8 DNRLP 模型變體的Recall@k 對比圖 (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é)果對比圖 (a) DNC 數(shù)據(jù)集; (b) Enron 數(shù)據(jù)集Fig. 9. MRR results of different training rates. (a) DNC dataset; (b) Enron dataset.

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

5 結(jié) 論

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

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