基于非負張量分解的動態社交網絡鏈路預測

楊兆鵬，袁華強

（東莞理工學院計算機科學與技術學院，廣東東莞 523000）

近年來信息技術發展與日俱進，社交網絡作為一個大規模的交流媒介，龐大的用戶關系得到了廣泛關注，如何對其進行數據分析和鏈路預測是社交網絡領域中的熱門課題。鏈路預測可以挖掘用戶間的隱特征，從而為用戶推薦新朋友[1-2]。通過動態社交網絡在時間1 到t的鏈路結構，預測出該網絡在t+1時的鏈路結構。

當前眾多的鏈路預測方法已經被提出，用于解決這個問題，Ahmed 等[3]通過非負矩陣分解(Non-Negative Matrix Factorization,NMF)從網絡的時間和拓撲結構中學習隱特征，通過時間和結構信息融合預測動態網絡。Mutinda 等[4]結合了NMF 和HW方法，NMF 提取隱特征，HW 方法提取時間動態特征，預測未來鏈路的隱藏鏈路。Muro 等[5]通過短隨機游動收集更高階的結構作為拓撲矩陣，然后基于拓撲矩陣的NMF 優化全局矩陣和臨時矩陣來計算未來相似矩陣。但上述方法只是通過將動態網絡圖轉化為靜態網絡圖或僅考慮部分信息，容易丟失動態網絡中的時序特征，對預測精度有一定影響。

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

1 社交網絡鏈路預測

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

圖1 時序數據鏈路預測

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

圖2 社交網絡張量

2 NTF-HM模型

2.1 非負張量分解算法

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

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

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

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

2.2 Holt-Winters預測方法

預測某些節點之間的鏈路變化是一個單變量時序預測任務，可以通過求解所有節點的組合來預測未來的鏈路結構。

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

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

3 NTF-HM模型優化

3.1 線性偏差的擴展

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

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

通過將式（9）與式（3）結合，實現了對Y執行基于隱特征張量分解的目標函數：

3.2 基于SLF-NMU規則的參數學習

首先，根據SLF-NMU 的學習規則[16]，實驗將每個隱特征因子和線性偏差都應用加性梯度下降方法(Additive Gradient Descent，AGD)，以實現如下學習規則：

η為參數的學習率，為了保障更新過程中的非負穩定性，將學習率設置如下：

將式（11）與式（12）結合，得到最終學習規則：

3.3 預測時間特征

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

經過NTF-HM 模型訓練后，當t=|T|+1 時，社交網絡張量中的每個元素表示如下：

4 實驗結果及分析

4.1 數據集設置

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

表1 數據集描述

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

4.2 評估指標

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

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

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

4.3 比較結果

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

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

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

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

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

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

圖3 現有模型在DBLP數據集上的ROC

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

圖4 現有模型在EOW數據集上的ROC

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

5 結論

該文針對傳統鏈路預測方法所存在的缺乏數據分析和預測準確性問題展開研究，提出了一種NTFHW 模型進行優化，以此提高動態鏈路的預測精度。通過對不同數據集的實驗對比，證實了該方法具有更高的預測精度，對于時序動態社交網絡的鏈路預測具有很強的實用性。但該模型HW 方法需要數據具有季節性和趨勢性，針對沒有這些性質的數據，將在未來計劃采用LSTM 或VAR 預測方法來進行研究。