動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題研究

王瑾

摘 要：由于動(dòng)態(tài)向網(wǎng)絡(luò)具有獨(dú)特的特征，在對(duì)其時(shí)序鏈路預(yù)測(cè)過程中存在許多問題，為此提出動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題研究。首先針對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)特征，采用拓?fù)浣Y(jié)構(gòu)解決其網(wǎng)絡(luò)定義問題;利用指數(shù)加權(quán)滑動(dòng)平均法對(duì)網(wǎng)絡(luò)時(shí)序進(jìn)行分析，得到T+1時(shí)刻預(yù)測(cè)值，解決時(shí)序分析問題;利用聚類算法計(jì)算出歐式距離最短的鏈路路徑，解決動(dòng)態(tài)有效網(wǎng)絡(luò)聚類傾向問題，以此完成動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題研究。針對(duì)上述3個(gè)問題提出相對(duì)應(yīng)的解決方法之后，該文中通過仿真實(shí)驗(yàn)在真實(shí)的動(dòng)態(tài)有向網(wǎng)絡(luò)中進(jìn)行了驗(yàn)證，證明通過上述方法解決了相關(guān)問題后鏈路預(yù)測(cè)效果更佳。

關(guān)鍵詞：動(dòng)態(tài)有向網(wǎng)絡(luò);時(shí)序鏈路;拓?fù)浣Y(jié)構(gòu);聚類算法

中圖分類號(hào)：TP301? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1001-5922（2021）09-0106-04

Research on the Problem of Time-series Link Prediction in Dynamic Directed Network

Wang Jin

（Shaanxi Institute of Technology， Xi an 710300， China）

Abstract：Due to the unique characteristics of dynamic directed networks， there are many problems in the process of predicting its time-series links. To this end， research on the problem of time-series links in dynamic directed networks is proposed. Firstly， according to the characteristics of the dynamic directed network， the topology is used to solve the network definition problem; the exponentially weighted moving average method is used to analyze the network time series to obtain the time prediction value to solve the time series analysis problem; the clustering algorithm is used to calculate the shortest Euclidean distance chain Road path， to solve the problem of clustering tendency of dynamic and effective networks， in order to complete the research on the problem of time-series link prediction in dynamic directed networks. After the corresponding solutions to the above three problems are proposed， the paper verifies the real dynamic directed network through simulation experiments， and proves that the link prediction effect is better after the above methods are solved.

Key words：dynamic directed network; sequential link; topology; clustering algorithm

0 引言

對(duì)于動(dòng)態(tài)有向網(wǎng)絡(luò)的時(shí)序鏈路預(yù)測(cè)方法有很多種，比如基于加權(quán)算法的時(shí)序鏈路預(yù)測(cè)方法、基于節(jié)點(diǎn)度的時(shí)序鏈路預(yù)測(cè)方法、基于有向路徑的時(shí)序鏈路預(yù)測(cè)方法等，這些方法有一個(gè)共同點(diǎn)是利用動(dòng)態(tài)有向網(wǎng)絡(luò)的拓?fù)湫畔ⅲㄟ^計(jì)算動(dòng)態(tài)有向網(wǎng)絡(luò)結(jié)構(gòu)的相似性，進(jìn)而預(yù)測(cè)出網(wǎng)絡(luò)可能的鏈路[1]。傳統(tǒng)方法雖然在實(shí)踐中取得了一定的成績(jī)，但是仍然具有一些不足之處[2-5]。傳統(tǒng)方法雖然有著良好的實(shí)用性，在大多數(shù)網(wǎng)絡(luò)中都能發(fā)揮作用，但是缺少針對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)類型的優(yōu)化，在對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)中進(jìn)行預(yù)測(cè)時(shí)，存在許多問題，因此提出動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題研究，以提高動(dòng)態(tài)有向網(wǎng)絡(luò)時(shí)序鏈路預(yù)測(cè)精度[6-7]。

1 動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題介紹

在動(dòng)態(tài)有向網(wǎng)絡(luò)中，節(jié)點(diǎn)之間存在固有的聚類傾向問題，導(dǎo)致預(yù)測(cè)過程中，很難將這種聚類傾向加以利用;在對(duì)時(shí)序鏈路預(yù)測(cè)過程中，由于動(dòng)態(tài)有向網(wǎng)絡(luò)不同于靜態(tài)網(wǎng)絡(luò)，需要對(duì)網(wǎng)絡(luò)進(jìn)行準(zhǔn)確定義，關(guān)系到時(shí)序鏈路預(yù)測(cè)結(jié)果的精準(zhǔn)度;面對(duì)時(shí)序會(huì)發(fā)展變化的網(wǎng)絡(luò)，其時(shí)序分析也存在一定難度。針對(duì)以上提出的動(dòng)態(tài)有向網(wǎng)絡(luò)時(shí)序鏈路預(yù)測(cè)問題，提出應(yīng)對(duì)方法，盡可能減小預(yù)測(cè)誤差，提高預(yù)測(cè)精度。圖1為動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題及方法。

通過采用拓?fù)浣Y(jié)構(gòu)對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)進(jìn)行定義;利用指數(shù)加權(quán)滑動(dòng)平均法解決時(shí)序分析問題;利用聚類算法對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類傾向進(jìn)行充分利用。下文將針對(duì)以上3方面時(shí)序鏈路預(yù)測(cè)問題進(jìn)行細(xì)致說明。

2 動(dòng)態(tài)有向網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題及對(duì)應(yīng)的 解決方法

2.1 網(wǎng)絡(luò)定義問題及其解決方法

2.1.1 網(wǎng)絡(luò)定義問題

此次研究的是動(dòng)態(tài)有向網(wǎng)絡(luò)的時(shí)序鏈路預(yù)測(cè)問題，現(xiàn)對(duì)于靜態(tài)網(wǎng)絡(luò)的鏈路預(yù)測(cè)，動(dòng)態(tài)有向網(wǎng)絡(luò)預(yù)測(cè)問題更多，首先面臨的問題就是網(wǎng)絡(luò)定義問題。動(dòng)態(tài)有向網(wǎng)絡(luò)定義與靜態(tài)網(wǎng)絡(luò)定義不同，網(wǎng)絡(luò)是會(huì)隨著時(shí)間的變化而發(fā)生變化的動(dòng)態(tài)網(wǎng)絡(luò)，即在動(dòng)態(tài)網(wǎng)絡(luò)中頂點(diǎn)的信息與網(wǎng)絡(luò)中心點(diǎn)的連接結(jié)構(gòu)是隨時(shí)會(huì)發(fā)生改變的，顯然目前的網(wǎng)絡(luò)定義不適用于動(dòng)態(tài)網(wǎng)絡(luò)。

2.1.2 解決方法

動(dòng)態(tài)網(wǎng)絡(luò)由頂點(diǎn)集合V和頂點(diǎn)之間的關(guān)系E組成。將動(dòng)態(tài)網(wǎng)絡(luò)映射到圖論中，其拓?fù)浣Y(jié)構(gòu)用公式表示如下所示：

公式（1）中，V表示飛控頂點(diǎn)集合;E表示非空邊集合。動(dòng)態(tài)網(wǎng)絡(luò)概要圖分為2種，一種是有向圖，圖中的邊都是有方向的，且兩邊頂點(diǎn)處為起點(diǎn)和終點(diǎn);另一種是無向圖，圖中的邊是沒有方向的。由于此次提出的方法是針對(duì)有向動(dòng)態(tài)網(wǎng)絡(luò)的，所以此次對(duì)無向網(wǎng)絡(luò)不做過多的說明，下文中使用到術(shù)語“圖”均指的是有向圖。有向網(wǎng)絡(luò)定義圖如圖2所示。

網(wǎng)絡(luò)結(jié)構(gòu)中存在5個(gè)頂點(diǎn)，如果∈E，那么頂點(diǎn)i和頂點(diǎn) j是相鄰的。頂點(diǎn)i的所有相鄰頂點(diǎn)集合記為L(zhǎng)（i）。圖中頂點(diǎn)i的相鄰頂點(diǎn)有頂點(diǎn)g和頂點(diǎn) j，則它的相鄰頂點(diǎn)集合L（i）={g，j}。頂點(diǎn)的degree，指的是網(wǎng)絡(luò)頂點(diǎn)關(guān)聯(lián)的邊的數(shù)量，在圖中，頂點(diǎn)i是有向網(wǎng)絡(luò)中的一個(gè)頂點(diǎn)，和頂點(diǎn)i關(guān)聯(lián)的邊的數(shù)量就是頂點(diǎn)i的degree，記為d（i）。圖中頂點(diǎn)i的degree為2，記為d（i）=2。對(duì)于動(dòng)態(tài)有向網(wǎng)絡(luò)，圖中每個(gè)頂點(diǎn)的degree由out degree和in degree組成。頂點(diǎn)i做始點(diǎn)的次數(shù)，稱為頂點(diǎn)i的out degree，頂點(diǎn)i做終點(diǎn)的次數(shù)，稱為頂點(diǎn)i的in degree，用數(shù)學(xué)公式表示如下：

公式（2）中，表示頂點(diǎn)i做始點(diǎn)的次數(shù);din（i）表示頂點(diǎn)做終點(diǎn)的次數(shù)。圖中頂點(diǎn)i到頂點(diǎn) j的路徑是一個(gè)時(shí)序頂點(diǎn)序列，路徑的長(zhǎng)度等于路徑上的邊的數(shù)量，第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同的路徑稱之為回路。

由上述可知，此次將動(dòng)態(tài)有向網(wǎng)絡(luò)定義為一個(gè)時(shí)間上的有序圖集，其拓?fù)浣Y(jié)構(gòu)為G=（E，V ），E和V分別為網(wǎng)絡(luò)某時(shí)刻的頂點(diǎn)集和變集，E和V會(huì)隨著時(shí)間的變化而變化，符合動(dòng)態(tài)網(wǎng)絡(luò)隨時(shí)間變化的特征。

2.2 時(shí)序分析問題及其解決方法

2.2.1 時(shí)序分析問題

時(shí)序分析問題是此次研究的關(guān)鍵問題，鏈路預(yù)測(cè)是網(wǎng)絡(luò)分析中的一個(gè)任務(wù)，其可以通過觀察到的網(wǎng)絡(luò)中的鏈路來預(yù)測(cè)出網(wǎng)絡(luò)下一時(shí)刻鏈路，目前在該領(lǐng)域的預(yù)測(cè)方法只是根據(jù)網(wǎng)絡(luò)特定時(shí)刻的狀態(tài)來預(yù)測(cè)網(wǎng)絡(luò)新的鏈路，其并不適用于動(dòng)態(tài)有效網(wǎng)絡(luò)，導(dǎo)致網(wǎng)絡(luò)的時(shí)序分析成為鏈路預(yù)測(cè)過程中的重要問題。常用的時(shí)序分析方法有滑動(dòng)平均法（Moving Average）、平均分析法（Average）、隨機(jī)時(shí)序分析法（Random Walk）、線性回歸分析法（Linear Regression）、指數(shù)加權(quán)滑動(dòng)平均法（exponentially weighted moving average）等。

2.2.2 解決方法

由于動(dòng)態(tài)有向網(wǎng)絡(luò)中的鏈路預(yù)測(cè)主要是結(jié)合網(wǎng)絡(luò)前T個(gè)時(shí)刻的信息，預(yù)測(cè)出網(wǎng)絡(luò)第T+1時(shí)刻的邊，針對(duì)上文定義的動(dòng)態(tài)有向網(wǎng)絡(luò)，需要利用時(shí)序分析方法對(duì)網(wǎng)絡(luò)所蘊(yùn)含的時(shí)序信息進(jìn)行分析，針對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)的鏈路預(yù)測(cè)具有一定的隨機(jī)性，考慮到時(shí)間間隔對(duì)網(wǎng)絡(luò)鏈路預(yù)測(cè)的影響，此次選擇指數(shù)加權(quán)滑動(dòng)平均法對(duì)網(wǎng)絡(luò)進(jìn)行時(shí)序分析。對(duì)于一個(gè)時(shí)間序列 ，T+1時(shí)刻的預(yù)測(cè)值可以按照以下公式計(jì)算：

公式（3）中，表示動(dòng)態(tài)有向網(wǎng)絡(luò)T+1時(shí)刻預(yù)測(cè)值;xT表示時(shí)刻的觀測(cè)值;α為平滑系數(shù)。對(duì)于公式（3）的求解，只需要將迭代的從網(wǎng)絡(luò)初始時(shí)刻計(jì)算，就可以得到動(dòng)態(tài)有向網(wǎng)絡(luò)T+1時(shí)刻的預(yù)測(cè)值。由于動(dòng)態(tài)有向網(wǎng)絡(luò)初始時(shí)刻并沒有對(duì)應(yīng)的預(yù)測(cè)值，所以要實(shí)現(xiàn)上述方法對(duì)網(wǎng)絡(luò)時(shí)序分析，還需要對(duì)網(wǎng)絡(luò)初始時(shí)刻預(yù)測(cè)值進(jìn)行取值[2]。如果動(dòng)態(tài)有向網(wǎng)絡(luò)存在較少的時(shí)間序列，則可以取T0時(shí)刻的觀測(cè)值作為T0時(shí)刻的預(yù)測(cè)值，如果動(dòng)態(tài)有向網(wǎng)絡(luò)存在較多的時(shí)間序列，則可以取序列xT0，xT1，xT2的平均值作為初始時(shí)刻的預(yù)測(cè)值，以此解決對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)時(shí)序分析問題。

2.3 聚類傾向問題及其解決方法

2.3.1 聚類傾向問題

由于動(dòng)態(tài)有向網(wǎng)絡(luò)中數(shù)據(jù)節(jié)點(diǎn)存在聚類傾向特征，導(dǎo)致在時(shí)序鏈路預(yù)測(cè)過程中，動(dòng)態(tài)有向網(wǎng)絡(luò)存在聚類傾向。

2.3.2 解決方法

利用聚類算法得到動(dòng)態(tài)有向網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的特征，降低預(yù)測(cè)的維度，對(duì)每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類分析，解決動(dòng)態(tài)有向網(wǎng)絡(luò)聚類傾向問題，計(jì)算出T+1時(shí)刻動(dòng)態(tài)有向網(wǎng)絡(luò)最短的邊，即最短路徑，實(shí)現(xiàn)時(shí)序鏈路預(yù)測(cè)[3]。計(jì)算每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)到所屬類中心的歐式距離，其計(jì)算公式如下：

公式（4）中，表示每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)到所屬類中心的歐式距離;表示網(wǎng)絡(luò)節(jié)點(diǎn)在頂點(diǎn)集合中的坐標(biāo);表示節(jié)點(diǎn)所屬類編號(hào)的類中心坐標(biāo)。在不同的類中，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量是不同的，為了方便了解在不同類中的網(wǎng)絡(luò)節(jié)點(diǎn)距離其各自中心的程度，需要對(duì)每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的歐式距離指標(biāo)進(jìn)行規(guī)范化，使節(jié)點(diǎn)所屬類具有相同的權(quán)重。為了保留原始網(wǎng)絡(luò)節(jié)點(diǎn)的比例特征，此次采用最大規(guī)范化方法來統(tǒng)一網(wǎng)絡(luò)節(jié)點(diǎn)，其公式表示如下：

公式（5）中，表示規(guī)范化后的網(wǎng)絡(luò)節(jié)點(diǎn)間歐式距離;表示類指標(biāo)的均值;表示類指標(biāo)的標(biāo)準(zhǔn)差。該規(guī)范化將每個(gè)類中的網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)范到[0，1]區(qū)間內(nèi)。基于動(dòng)態(tài)有向網(wǎng)絡(luò)中的物理現(xiàn)象，此處給出聚類系數(shù)計(jì)算公式：

D的取值如圖3所示。

由于sdist值被規(guī)范化到[0，1]區(qū)間內(nèi)，節(jié)點(diǎn)x和節(jié)點(diǎn)y之和取值為[0，2]區(qū)間內(nèi)，從而聚類系數(shù)取值為正弦函數(shù)的[0，π]區(qū)間內(nèi)。當(dāng)兩節(jié)點(diǎn)之和接近零，此時(shí)聚類系數(shù)值較低，表明此時(shí)動(dòng)態(tài)有向網(wǎng)絡(luò)不存在聚類傾向，動(dòng)態(tài)有向網(wǎng)絡(luò)之間兩頂點(diǎn)之間的距離最短，此條路徑為最短有效路徑，將該條路徑作為結(jié)果輸出，精準(zhǔn)的預(yù)測(cè)出動(dòng)態(tài)有效網(wǎng)絡(luò)時(shí)序鏈路。

3 實(shí)驗(yàn)驗(yàn)證

在上述環(huán)節(jié)中對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)中的網(wǎng)絡(luò)定義問題、時(shí)序分析問題、聚類傾向問題提出相應(yīng)的解決方法之后，本部分內(nèi)容通過仿真實(shí)驗(yàn)在Facebook-wall中進(jìn)行了驗(yàn)證，結(jié)果如圖4所示。

由圖4結(jié)果可知，在相同的時(shí)間窗口下，該文中在解決上述3個(gè)問題之后在動(dòng)態(tài)有向網(wǎng)絡(luò)中鏈路預(yù)測(cè)效果有顯著的提升，證明了該文中提出的3種方法的有效性。

4 結(jié)語

此次針對(duì)動(dòng)態(tài)有向網(wǎng)絡(luò)時(shí)序鏈路預(yù)測(cè)過程中出現(xiàn)的網(wǎng)絡(luò)定義問題、時(shí)序分析問題、聚類傾向問題進(jìn)行了研究，并對(duì)其提出了相應(yīng)的解決方法，將研究重點(diǎn)落腳在動(dòng)態(tài)有向網(wǎng)絡(luò)預(yù)測(cè)有關(guān)問題，有效提高了預(yù)測(cè)精度。此次研究仍存在優(yōu)化改進(jìn)的地方，比如提出的聚類系數(shù)存在較強(qiáng)的針對(duì)性，不具有較強(qiáng)的普適性，今后還需在該方面進(jìn)行深入研究，為時(shí)序鏈路預(yù)測(cè)研究提供理論依據(jù)。

參考文獻(xiàn)

[1]岳增慧，許海云，王倩飛.基于局部信息相似性的學(xué)科引證知識(shí)擴(kuò)散動(dòng)態(tài)鏈路預(yù)測(cè)研究[J].情報(bào)理論與實(shí)踐，2020，43（02）：84-91+99.

[2]吳晨程，周銀座.基于圖嵌入法的時(shí)序網(wǎng)絡(luò)鏈路預(yù)測(cè)研究[J].杭州師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，19（05）：472-480.

[3]符漢杰，熊赟，朱揚(yáng)勇.TLP：一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)算法[J].計(jì)算機(jī)工程，2020，46（01）：67-73.

[4]杜凡，劉群.有向動(dòng)態(tài)網(wǎng)絡(luò)中基于模體演化的鏈路預(yù)測(cè)方法[J].計(jì)算機(jī)應(yīng)用研究，2019，36（05）：1441-1445+1453.

[5]楊瑞琪，張?jiān)孪?一種時(shí)序有向社會(huì)網(wǎng)絡(luò)中的鏈路預(yù)測(cè)算法[J].計(jì)算機(jī)工程，2019，45（03）：197-201.

[6]潘嘉琪，鄒俊韜.一種基于深度RTRBM的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2020，30（03）：1-6.

[7]馮譯萱，張?jiān)孪?一種時(shí)序有向網(wǎng)絡(luò)中的鏈路預(yù)測(cè)方法[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（21）：151-157.

[8]劉書新，劉群，杜凡.基于模體演化與社區(qū)一致性的時(shí)序鏈路預(yù)測(cè)方法[J].計(jì)算機(jī)應(yīng)用研究，2019，36（12）：3674-3678+3684.

[9]劉留，王煜堯，倪琦瑄，曹杰，卜湛.一種基于博弈論的時(shí)序網(wǎng)絡(luò)鏈路預(yù)測(cè)方法[J].計(jì)算機(jī)研究與發(fā)展，2019，56（09）：1953-1964.