基于非負(fù)張量分解的動態(tài)社交網(wǎng)絡(luò)鏈路預(yù)測

楊兆鵬，袁華強(qiáng)

（東莞理工學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院，廣東東莞 523000）

近年來信息技術(shù)發(fā)展與日俱進(jìn)，社交網(wǎng)絡(luò)作為一個大規(guī)模的交流媒介，龐大的用戶關(guān)系得到了廣泛關(guān)注，如何對其進(jìn)行數(shù)據(jù)分析和鏈路預(yù)測是社交網(wǎng)絡(luò)領(lǐng)域中的熱門課題。鏈路預(yù)測可以挖掘用戶間的隱特征，從而為用戶推薦新朋友[1-2]。通過動態(tài)社交網(wǎng)絡(luò)在時間1 到t的鏈路結(jié)構(gòu)，預(yù)測出該網(wǎng)絡(luò)在t+1時的鏈路結(jié)構(gòu)。

當(dāng)前眾多的鏈路預(yù)測方法已經(jīng)被提出，用于解決這個問題，Ahmed 等[3]通過非負(fù)矩陣分解(Non-Negative Matrix Factorization,NMF)從網(wǎng)絡(luò)的時間和拓?fù)浣Y(jié)構(gòu)中學(xué)習(xí)隱特征，通過時間和結(jié)構(gòu)信息融合預(yù)測動態(tài)網(wǎng)絡(luò)。Mutinda 等[4]結(jié)合了NMF 和HW方法，NMF 提取隱特征，HW 方法提取時間動態(tài)特征，預(yù)測未來鏈路的隱藏鏈路。Muro 等[5]通過短隨機(jī)游動收集更高階的結(jié)構(gòu)作為拓?fù)渚仃嚕缓蠡谕負(fù)渚仃嚨腘MF 優(yōu)化全局矩陣和臨時矩陣來計算未來相似矩陣。但上述方法只是通過將動態(tài)網(wǎng)絡(luò)圖轉(zhuǎn)化為靜態(tài)網(wǎng)絡(luò)圖或僅考慮部分信息，容易丟失動態(tài)網(wǎng)絡(luò)中的時序特征，對預(yù)測精度有一定影響。

通過相關(guān)文獻(xiàn)來看，隱特征分析(Latent Factor Analysis,LFA)的方法被廣泛應(yīng)用于數(shù)據(jù)分析中[6-8]。基于此綜合考慮動態(tài)社交網(wǎng)絡(luò)的特點和影響因素，采用NFT 方法對歷史鏈路圖進(jìn)行建模，并保留了數(shù)據(jù)的時序特征，加入線性偏差對模型進(jìn)行優(yōu)化，結(jié)合HW 方法來提高動態(tài)網(wǎng)絡(luò)鏈路預(yù)測效果。

1 社交網(wǎng)絡(luò)鏈路預(yù)測

社交網(wǎng)絡(luò)的鏈路預(yù)測如圖1 所示，給定一組由時間1 到 |T|的G1=(I,J,E1),Gt=(I,J,Et),…,G|T|=(I,J,E|T|)時序圖，I和J分別是網(wǎng)絡(luò)中的兩個節(jié)點集，T是時間節(jié)點集，Et∈I×J是在時間t時的加權(quán)鏈路集。如果節(jié)點i和節(jié)點j之間在時間t時存在鏈路，則為(i,j,t)分量分配鏈路權(quán)重，反之如果沒有鏈路，則設(shè)為缺失的未知鏈路。該任務(wù)的目標(biāo)是基于先前時間1 到 |T|的時序數(shù)據(jù)，預(yù)測時間 |T|+1 時G|T|+1的鏈路結(jié)構(gòu)。

圖1 時序數(shù)據(jù)鏈路預(yù)測

在執(zhí)行動態(tài)數(shù)據(jù)預(yù)測前，先將這些動態(tài)圖Gt(1 ≤t≤ |T|)作為基本數(shù)據(jù)源輸入到張量中去。如圖2 所示，因為輸入的數(shù)據(jù)是在實數(shù)非負(fù)字段上定義的，所以此張量也由非負(fù)數(shù)據(jù)所占據(jù)，特別注意，張量中有很多缺失的鏈路而包含了許多未知條目，所以目標(biāo)張量Y通常是高維稀疏的。

圖2 社交網(wǎng)絡(luò)張量

2 NTF-HM模型

2.1 非負(fù)張量分解算法

張量分解常用的方法有CP分解和Tucker分解[9]，但由于Tucker 分解還需要額外考慮一個核心張量上的元素，需要消耗大量的時間成本。于是實驗使用了CP 分解。經(jīng)過CP 分解后，目標(biāo)張量Y就被分解為H個秩一張量P1,P2,…,PH的近似和，如式（1）所示：

其中，H是近似秩。秩一張量Ph是由三個隱特征向量ah,ch,kh的外積組成，展開之后中的每一個元素寫成：

因為Y中的大多數(shù)元素都是未知的，當(dāng)衡量Y與的誤差時，它是一個不適定問題[10]，同時也會導(dǎo)致分配不均勻，缺乏通用性，所以將L2 正則化[11-12]整合到其中。于是損失函數(shù)重新表示為：

λ為隱特征矩陣的正則化系數(shù)，Λ 為Y的已知項集合。

2.2 Holt-Winters預(yù)測方法

預(yù)測某些節(jié)點之間的鏈路變化是一個單變量時序預(yù)測任務(wù)，可以通過求解所有節(jié)點的組合來預(yù)測未來的鏈路結(jié)構(gòu)。

三階指數(shù)平滑法Holt-Winters 可以被用來預(yù)測具有季節(jié)性和趨勢性的時序數(shù)據(jù)[13]，季節(jié)性表示時序數(shù)據(jù)具有每M個周期重復(fù)一次的趨勢。Holt-Winters 有加性方法和乘性方法兩種方式，在季節(jié)性部分，不同的數(shù)據(jù)采用的方式也不同。加性方法更加適合季節(jié)變化大致恒定的時序數(shù)據(jù)。而乘性方法更適用于季節(jié)變化與水平值成比例變化的時序數(shù)據(jù)。在實驗中，模型選擇加性方法來驗證真實的數(shù)據(jù)集。加性Holt-Winters 預(yù)測方法由三個平滑方程和一個預(yù)測方程組成，如下所示：

其中α、β、γ是平滑參數(shù)，lt是對在時間t時的水平值的平滑估計，bt是對在時間t時趨勢變化的平滑估計，st是對在時間t時季節(jié)分量的平滑估計，這三個平滑方程可以最小化平方誤差和預(yù)測誤差。yt+g表示未來g個時間段的預(yù)測值。

3 NTF-HM模型優(yōu)化

3.1 線性偏差的擴(kuò)展

因為時序動態(tài)網(wǎng)絡(luò)的數(shù)據(jù)會隨著時間不斷變化。根據(jù)前人的研究[14-15]，基于隱特征張量分解模型的穩(wěn)定性和表達(dá)能力可以通過加入線性偏差得到提高。所以將線性偏差加入到式（1）中，重新表述為：

τ1、τ2、τ3是三個線性偏差張量，它們分別由線性偏差矩陣的第一、第二和第三列的線性偏差向量d|I|、e|J|、f|T|與兩個由常量1 的向量的外積生成。D、E、F只有對應(yīng)的第一、第二和第三列有線性偏差值，其余列由常量1 填充。那么每個元素表示為：

通過將式（9）與式（3）結(jié)合，實現(xiàn)了對Y執(zhí)行基于隱特征張量分解的目標(biāo)函數(shù)：

3.2 基于SLF-NMU規(guī)則的參數(shù)學(xué)習(xí)

首先，根據(jù)SLF-NMU 的學(xué)習(xí)規(guī)則[16]，實驗將每個隱特征因子和線性偏差都應(yīng)用加性梯度下降方法(Additive Gradient Descent，AGD)，以實現(xiàn)如下學(xué)習(xí)規(guī)則：

η為參數(shù)的學(xué)習(xí)率，為了保障更新過程中的非負(fù)穩(wěn)定性，將學(xué)習(xí)率設(shè)置如下：

將式（11）與式（12）結(jié)合，得到最終學(xué)習(xí)規(guī)則：

3.3 預(yù)測時間特征

引入Holt-Winters 預(yù)測方法感知隱特征以獲取 |T|+1 時的K與f，根據(jù)式（4）-（7），預(yù)測公式可表示為：

經(jīng)過NTF-HM 模型訓(xùn)練后，當(dāng)t=|T|+1 時，社交網(wǎng)絡(luò)張量中的每個元素表示如下：

4 實驗結(jié)果及分析

4.1 數(shù)據(jù)集設(shè)置

實驗選用了兩個數(shù)據(jù)集，分別是DBLP 數(shù)據(jù)集和Edit of Wikiquote(EOW)數(shù)據(jù)集。DBLP 數(shù)據(jù)集是由2011 年至2020 年收錄的出版物組成，數(shù)據(jù)由作者、期刊和年份組成，當(dāng)某作者的論文在某一年某一期刊上發(fā)表時，則作者就在那一年與該期刊之間建立了聯(lián)系。不同的期刊收錄的論文數(shù)具有一定的周期性和季節(jié)性，作者發(fā)表論文時也會考慮期刊的收錄數(shù)。從該數(shù)據(jù)集中提取了前1 000 名最常發(fā)表論文的作者和前500 個被發(fā)表最多次數(shù)的期刊。并將前9 年數(shù)據(jù)作為訓(xùn)練集，把最后一年的數(shù)據(jù)作為測試集。訓(xùn)練集和測試集的密度如表1 所示[17]。

表1 數(shù)據(jù)集描述

EOW 數(shù)據(jù)集包含了由2003 年至2017 年的頁面編輯次數(shù)組成。數(shù)據(jù)由用戶、頁面和時間組成，與DBLP 數(shù)據(jù)集類似，實驗選擇了前1 000 名最活躍的用戶和前500 個被編輯次數(shù)最多的頁面，前14 年作為訓(xùn)練集，最后一年作為測試集。訓(xùn)練集和測試集的密度如表1 所示。

4.2 評估指標(biāo)

對于一個動態(tài)鏈路預(yù)測問題，基于結(jié)果構(gòu)建ROC 曲線，曲線下包含的面積AUC 代表了辨別能力，即正確預(yù)測真陽性和真陰性的能力。為了計算AUC 分?jǐn)?shù)，對現(xiàn)有和不存在邊的相似性指數(shù)進(jìn)行了排名。然后，比較了n對存在和不存在邊的得分。如果在這n對邊中，n′表示比較中存在邊的得分大于不存在邊的得分，n″表示比較中存在邊的得分等于不存在邊的得分，當(dāng)AUC 分?jǐn)?shù)越大，說明模型的效果越好。AUC 分?jǐn)?shù)的表示公式如下：

在實驗中，因為數(shù)據(jù)集的值的寬度范圍不一，為了消除數(shù)據(jù)中大值的影響，根據(jù)文獻(xiàn)[10]提出觀點對數(shù)據(jù)進(jìn)行歸一化處理：

實驗的目的是預(yù)測節(jié)點i和節(jié)點j之間是否存在鏈路，其鏈路信息表示為：

4.3 比較結(jié)果

首先，實驗分別在兩個數(shù)據(jù)集中比較了NTF-HW模型與最新模型的性能，整個實驗包含以下模型。

模型一：簡單平均法,使用歷史時間段中數(shù)據(jù)的平均值作為基線方法。

模型二：Holt-Winters 模型[13]，是一種適用于具有季節(jié)性和趨勢性的時序數(shù)據(jù)預(yù)測方法。

模型三：NMF-HW 模型[4]，此方法采用NMF 提取隱特征，用Holt-Winters 方法捕捉特征隨時間的變化。

模型四：NTF-HW 模型，即該文提出的模型。

對于測試的模型，參數(shù)的最佳值是很難確定的。對于HW 的季節(jié)性參數(shù)M和NTF 以及NMF 的特征數(shù)H需要手動選擇，該實驗采用網(wǎng)格搜索法尋找最佳參數(shù)值。根據(jù)AUC 分?jǐn)?shù)比較了這些方法的性能，實驗結(jié)果如圖3-4 所示。

圖3 現(xiàn)有模型在DBLP數(shù)據(jù)集上的ROC

圖3、圖4 顯示了現(xiàn)有方法在DBLP 數(shù)據(jù)集和EOW 數(shù)據(jù)集上的性能表現(xiàn)。實驗提出的方法實現(xiàn)了動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的最高AUC 分?jǐn)?shù)。對于單一的HW 預(yù)測方法，它只適用于具有季節(jié)性的數(shù)據(jù)。因為作者發(fā)表論文數(shù)量是具有一定周期性的，所以在DBLP中預(yù)測效果也不錯。相對地，在EOW 數(shù)據(jù)集中，季節(jié)性表現(xiàn)不是很強(qiáng)烈，導(dǎo)致了預(yù)測效果一般。對于NMF-HW 來說，該模型結(jié)合了數(shù)據(jù)特征的挖掘，所以在預(yù)測鏈路時，HW 方法能夠根據(jù)動態(tài)隱特征得到更高的預(yù)測精度。在對隱特征挖掘時，NTFHW 能夠更好地保留時序特征，所以在預(yù)測精度上比NMF-HW 更高。

圖4 現(xiàn)有模型在EOW數(shù)據(jù)集上的ROC

實驗也比較了是否添加線性偏差的NTF-HW預(yù)測結(jié)果，從圖中可以看出當(dāng)添加線性偏差時，預(yù)測效果優(yōu)于沒有加入線性偏差的NTF-HW。此外，基線方法在兩個數(shù)據(jù)集預(yù)測效果都表現(xiàn)良好，這是因為在實驗中采用了最活躍的節(jié)點。

5 結(jié)論

該文針對傳統(tǒng)鏈路預(yù)測方法所存在的缺乏數(shù)據(jù)分析和預(yù)測準(zhǔn)確性問題展開研究，提出了一種NTFHW 模型進(jìn)行優(yōu)化，以此提高動態(tài)鏈路的預(yù)測精度。通過對不同數(shù)據(jù)集的實驗對比，證實了該方法具有更高的預(yù)測精度，對于時序動態(tài)社交網(wǎng)絡(luò)的鏈路預(yù)測具有很強(qiáng)的實用性。但該模型HW 方法需要數(shù)據(jù)具有季節(jié)性和趨勢性，針對沒有這些性質(zhì)的數(shù)據(jù)，將在未來計劃采用LSTM 或VAR 預(yù)測方法來進(jìn)行研究。