基于非负张量分解的动态社交网络链路预测

杨兆鹏，袁华强

（东莞理工学院计算机科学与技术学院，广东东莞 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 预测方法来进行研究。