王瑾

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

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

中圖分類號：TP301? ? ? 文獻(xiàn)標(biāo)識碼：A 文章編號：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 引言

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

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

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

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

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

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

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

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

2.1.2 解決方法

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

公式（1）中，V表示飛控頂點(diǎn)集合;E表示非空邊集合。動態(tài)網(wǎng)絡(luò)概要圖分為2種，一種是有向圖，圖中的邊都是有方向的，且兩邊頂點(diǎn)處為起點(diǎn)和終點(diǎn);另一種是無向圖，圖中的邊是沒有方向的。由于此次提出的方法是針對有向動態(tài)網(wǎng)絡(luò)的，所以此次對無向網(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（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。對于動態(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)序列，路徑的長度等于路徑上的邊的數(shù)量，第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同的路徑稱之為回路。

由上述可知，此次將動態(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會隨著時(shí)間的變化而變化，符合動態(tài)網(wǎng)絡(luò)隨時(shí)間變化的特征。

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

2.2.1 時(shí)序分析問題

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

2.2.2 解決方法

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

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

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

2.3.1 聚類傾向問題

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

2.3.2 解決方法

利用聚類算法得到動態(tài)有向網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的特征，降低預(yù)測的維度，對每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類分析，解決動態(tài)有向網(wǎng)絡(luò)聚類傾向問題，計(jì)算出T+1時(shí)刻動態(tài)有向網(wǎng)絡(luò)最短的邊，即最短路徑，實(shí)現(xiàn)時(shí)序鏈路預(yù)測[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)所屬類編號的類中心坐標(biāo)。在不同的類中，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量是不同的，為了方便了解在不同類中的網(wǎng)絡(luò)節(jié)點(diǎn)距離其各自中心的程度，需要對每個(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)。基于動態(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í)動態(tài)有向網(wǎng)絡(luò)不存在聚類傾向，動態(tài)有向網(wǎng)絡(luò)之間兩頂點(diǎn)之間的距離最短，此條路徑為最短有效路徑，將該條路徑作為結(jié)果輸出，精準(zhǔn)的預(yù)測出動態(tài)有效網(wǎng)絡(luò)時(shí)序鏈路。

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

在上述環(huán)節(jié)中對動態(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è)問題之后在動態(tài)有向網(wǎng)絡(luò)中鏈路預(yù)測效果有顯著的提升，證明了該文中提出的3種方法的有效性。

4 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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