基于混合深度学习的复杂网络链路预测研究

白 雪，董德森

(1.吉林化工学院信息中心，吉林吉林 132022；2.延边大学师范学院，吉林延吉 133002)

1 引言

在复杂网络的链路预测中，在已有的网络节点属性和信息获取过程中，不仅存在未来网络链路，还存在没有被发现的网络链路[1]。在预测复杂网络节点之间的链路中，通过找出复杂网络中很多不被知道的链路间关系，获取复杂网络结构分析与链路预测研究理论之间的关系，分析网络拓扑结构的演化机制，以此对复杂网络链路进行预测。链路预测来分析复杂网络和应用网络，来找出好的链路预测方法，继而找出预测复杂网络拓扑结构的演化规律[2]。在复杂网络分析中，链路预测问题是其重要的组成部分，链路预测在复杂网络中的目的是为了解决路由策略的难点。但是在不同的复杂网络中，链路预测的方法也存在不同[3]。所以要设计一个好的链路预测方法，在现有的经验和网络的实际条件下，根据复杂网络的特征来设计出链路预测方法。

王文涛等人[4]主要是对现有的链路预测方法进行着重研究，来获悉网络节点的领域拓扑信息，从而形成网络链路中的特殊向量，先是通过网络来学习node2vec算法，形成节点表示向量，而通过该向量来映射网络节点的结构信息，使之成为具有三维特征的数据，接着通过稠密连接卷积神经网络来获取链路的结构特征，并形成两个分类模型，形成了链路预测，并经仿真表明该链路预测方法具备较好的预测性能；白桦等人[5]为了提高网络链路预测的准确性，将节点局部相似性应用到了复杂网络链路预测中，并通过五个复杂网络数据集进行实验，采用AUC指标评价其效果，实验表明改进的方法在预测准确率上整体优于其它的局部相似性方法。但是以上两种方法在多次迭代的情况下，会出现网络链路的预测精度偏低，导致最终的预测结果较差。

针对以上研究背景，本文采用混合深度学习来预测复杂网络链路，从而提高复杂网络链路预测效果。

2 复杂网络链路预测方法

2.1 相似性指标

在复杂网络中，可以使用与节点属性相似的外部信息来预测网络链路，但由于复杂网络节点属性随网络结构的变化而变化[6]，因此无法应用于复杂网络的链路预测。但相对于复杂网络节点的属性信息，结构信息和历史行为信息具有更高的可信度，且更易于获取。

链路变化的情况具有不确定性，常常受到时间的演化和网络本身固有的某些因素影响，如果能在网络链路预测方法中加以考虑，并能进一步分析这些因素对链路变化的具体影响，则对实际复杂网络的链路预测研究有很大帮助[7]。图1显示了复杂网络链路变化的示意图。

图1 链路变化示意图

如图1所示，如果只考虑复杂网络在t3时刻的结构，那么当预测下一个时刻的复杂网络链路情况时，就可以直接得出节点S和节点D之间基本不会发生连接[8]。但是，综合考虑t1时刻和t2时刻的复杂网络拓扑结构，可以发现节点S和节点D之间的关系比较密切，它们之间存在着很高的连接可能性。如果能利用混合深度学习网络上的历史信息来预测复杂网络链路，则预测结果会更加准确[9]。

将复杂网络中节点对连接的总时长、频率和最终时刻相结合，计算网络历史信息对复杂网络链路的影响系数

HIC=Il+If+Ic

(1)

其中，Il表示复杂网络节点对连接的时长系数，If表示频次系数，Ic表示复杂网络节点对最近联系的时刻系数。

利用RA、AA、CN三个指标综合考虑复杂网络历史信息对链路的影响系数[10]，得到H_CN、H_AA、H_RA相似性指标，即

(2)

(3)

(4)

复杂网络会随着时间的频繁变化而产生一种拓扑结构，H_CN、H_AA、H_RA相似性指标考虑到了复杂网络结构对链路的影响程度，分析了复杂网络的拓扑特征，适合应用于复杂网络链路的预测。

利用链路变化示意图，分析了历史信息对复杂网络链路的影响系数，结合RA指标、AA指标和CN指标的计算，分析了复杂网络的拓扑特征。

2.2 基于混合深度学习的预测模型

通过混合深度学习技术，在机器学习的过程中构建人工神经网络[11]。在网络每一隐含层中，神经网络都会产生非线性变换，最后，提取输入数据中的隐藏规律。现有的机器学习模型都是在浅层次学习的基础上进行的，不能很好的提取网络链路的基本特征，而混合深度学习技术中的隐藏层具有非线性计算功能，能快速的处理信息，因此，利用混合深度学习技术，对复杂网络链路进行预测[12]。

混合深度学习技术是在输入网络数据和模型的基础上，构建一个与人大脑层次结构类似的神经系统。混合深度学习的反向传播的流程如图2所示。

图2 混合深度学习的反向传播流程图

基于混合深度学习的反向传播流程，可以在t时刻描述出复杂网络链路隐藏层的状态，如下

(5)

t时刻复杂网络隐藏层的状态是由t-1时刻的状态和t时刻的输入数据来决定的，其中，σ表示激活函数，b表示偏置参数，那么t时刻复杂网络隐藏层的输出为

o(t)=Vh(t)+c

(6)

那么t时刻预测出的复杂网络链路输出值为

(7)

利用时间窗中的相似性指标对复杂网络链路进行预测，取得了良好的效果，但目前还没有发现时间窗和时间窗之间的具体联系。若能随着时间变化，挖掘出复杂网络链路的规律，则能较好地预测复杂网络中的链路，并能准确地将相似度指标作为混合深度学习的训练样本，预处理训练之后，再将数据输入到复杂网络链路预测模型中，以相似度指标作为网络链路的基本特征，提取出复杂网络的变化规律。

基于深度学习的复杂网络链路预测模型框架如图3所示。

图3 基于深度学习的复杂网络链路预测模型框架

基于混合深度学习的反向传播流程，描述出复杂网络链路隐藏层的状态，利用复杂网络隐藏层的输出，预测出的复杂网络链路输出值，将相似性指标作为复杂网络链路预测的训练样本，构建了复杂网络链路预测模型。

2.3 复杂网络链路预测实现

复杂网络节点移动的随机性会导致复杂网络出现稀疏的特性。由于大多数情况下网络连接数较少，在链路预测模型的训练阶段，正负样本的比例严重失衡。为了减少上述问题对模型精度的影响，有必要针对性地选择预测区域中的复杂网络节点，以保证其中生成的连接不太稀疏。本文不根据节点在物理空间中的位置划分预测区域，而是确定节点组成的逻辑空间。具体方法是：遍历所有复杂网络节点，获取每个节点的历史连接信息，计算每个节点的连接权重，如下式所示

(8)

其中，R(i)表示每个节点的连接权重，i表示复杂网络节点的编号，j表示与节点i产生连接的节点编号，R表示相关性系数。接下来对所有复杂网络节点的连接权重进行排序，按照下式来计算复杂网络节点的多项式概率分布情况

(9)

其中，Rall表示所有节点的连接权重。在目前主流的网络链路预测研究中，由于网络的演化过程都比较复杂，大多数链路预测方法都考虑了一对节点之间的链路。然而，在实际的网络环境中，多个网络节点之间的链路情况往往反映了复杂网络结构的演化规律。单节点对之间的链路预测本质是一个二元分类问题。如果预测结果为1，则表示该对节点在下一个周期内可以连接，如果预测结果为0，则不连接。在此基础上，针对多个网络节点之间的链路，将多个网络节点之间的每一个可能的连接视为一个模式(如图4所示)，然后利用模式分类方法实现多个网络节点之间的链路预测。

图4 复杂网络链路划分结果

复杂网络在下一个时刻的链路模式就是预测的输出标签，每一类标签都具有特定的编号，由下式计算得到

(10)

其中，N表示复杂网络节点对的数量，Si表示第i个复杂网络节点对之间的链路状态，N的大小由下式决定

(11)

其中，n表示复杂网络节点的数量。

综上所述，采用历史信息计算复杂网络链路的影响系数，引入复杂网络链路预测相似性指标，利用混合深度学习构建复杂网络链路的预测模型，结合模式分类方法实现多个网络节点之间的链路预测

3 实验对比分析

3.1 实验数据集

采用复杂网络中比较具有代表性的数据集进行实验分析，数据集的参数设置如表1所示。

表1 数据集的参数设置

Infocom05数据集中的复杂网络节点的活动范围比较小，具有较高的相遇频率，而MIT数据集具有节点密度小、场景大的特点，且复杂网络节点的相遇频率比较低。两个数据集之间具有非常强烈的针对性。

3.2 实验平台及工具

采用Matlab仿真工具计算Infocom05数据集和MIT数据集在特定时间窗口内的指标值，并对复杂网络中的链路数据进行分割处理，使复杂网络链路数据在测试过程中与混合深度学习的格式更贴切。在复杂网络链路预测对比测试中，采用机器学习库中的算法进行比较，验证基于混合深度学习的复杂网络链路预测方法的准确性。

3.3 实验结果分析

在Infocom05数据集和MIT数据集中，复杂网络节点对平均每一个240秒和1400秒都会自动完成一次连接，令复杂网络链路不发生改变。实验测试过程中，设置Infocom05数据集在60秒～600秒的相邻范围内进行对比，采样间隔为60秒，设置MIT数据集在300秒～3000秒的相邻范围内进行对比，对比结果如表2所示。

表2 不同时间窗口下复杂网络链路的预测效果

从表2的结果可以看出，时间窗口的长度不同会影响复杂网络链路的预测效果，如果时间窗口比较短，输入的复杂网络链路样本就会出现过多的链路数据重复的特征，并且在训练网络链路数据样本的过程中，由于复杂网络中新链路特征的敏感性比较强烈，导致链路预测的效果越来越差；如果时间窗口随着实验测试的进行越来越大，就会增大复杂网络链路特征的提取难度，还会在链路数据训练过程中，无法提取出网络链路特征。根据表2的仿真结果可以得出，为了使预测效果达到最优，需要将时间窗口在两个数据集中分别设为360秒和180秒。

在链路预测效果实验中，假设链路数据样本的维度在100步长～600步长之间，实验结果采集间隔为50个步长。结果如表3所示。

表3 不同维度下复杂网络链路的预测结果

从表3的结果可以看出，样本维度的不同会影响复杂网络链路的预测效果，在Infocom05数据集和MIT数据集中，复杂网络链路要想达到最好的预测效果，需要将样本维度设置为500和600。

为了验证本文方法的有效性，采用本文提出的基于混合深度学习的复杂网络链路预测方法、文献[4]提出的基于密集连接卷积神经网络的链路预测方法和文献[5]提出的基于节点局部相似性的复杂网络链路预测方法，对复杂网络链路预测精度进行对比分析，对比结果如图5所示。

图5 三种方法的预测精度对比结果

根据图5可知，随着迭代次数的不断增加，本文方法的复杂网络链路预测精度较稳定，一直持续在99%左右，而文献[4]提出的基于密集连接卷积神经网络的链路预测方法和文献[5]提出的基于节点局部相似性的复杂网络链路预测方法随着迭代次数的不断增加，复杂网络链路预测精度曲线波动较大，最高只有90%，说明本文方法的复杂网络链路预测精度比文献[4]提出的基于密集连接卷积神经网络的链路预测方法和文献[5]提出的基于节点局部相似性的复杂网络链路预测方法的复杂网络链路预测精度高。

4 结束语

为了解决传统的复杂网络链路预测方法存在预测精度低的问题，本文提出了基于混合深度学习的复杂网络链路预测方法，利用混合深度学习构建了复杂网络链路的预测模型，结合复杂网络链路程序设计，实现了复杂网络链路的预测。仿真结果显示，该方法的复杂网络链路预测精度较高，预测效果较好。