本发明属于网络演化链路预测领域，具体涉及一种基于深度学习算法的有向链路预测模型。
背景技术：
链路预测(linkprediction，lp)是指如何通过已知的网络结构等信息预测网络中两个节点之间是否存在或产生链接的可能性，即链路预测包括：1)预测已存在但尚未被发现的链接，即预测未知链接；2)预测现在未存在但未来可能新产生的链接，即预测未来链接。
解决链路预测问题，从采用的技术上来说，可以分为基于马尔可夫链的方法和基于学习的方法。其本质都是计算网络中两个节点存在链接的概率问题。
将马尔科夫模型引入链接预测，最初由zukerman等在1999年提出。其通过抽象浏览用户的浏览过程，建立马尔科夫链，利用转移概率矩阵进行预测。由于该类型方法只考虑建立一步状态转移概率矩阵，预测准确率不高，因此，目前的研究已向基于学习的方法发展。根据基于学习的链接预测方法相关文献所采用的技术，该类方法可分为两类：
1)基于机器学习的方法
基于机器学习相关技术的链路预测方法可以通过构建学习网络来探索多个指标，而不是使用某种单一指标度量。在将多个度量作为特征向量输入后，可产生对每个潜在链接形成可能性的预测。在近五年该类方法相关成果中，涉及了多种机器学习算法，如logistic、支持向量机、神经网络等传统算法，以及cnn、lstm、rnn等深度学习算法。由此可见，链路预测领域所用技术已向机器学习倾斜。需要指出的是，随着网络数据量的膨胀以及硬件计算性能的提高，目前深度学习算法较传统的机器学习算法更易被研究人员重视。
2)基于矩阵分解的方法
矩阵分解是一种获得网络邻接矩阵的低秩近似和全局信息的技术。由于基于矩阵分解的方法要求全局信息，且较基于机器学习的方法可理解掌握性差，因此，近几年相关研究文献相对较少。
关于链路预测面向的网络特点，已有技术主要关注网络的动态或静态、有向或无向特征。静态网络特征指网络在某一时间点的拓扑结构、节点属性等的特征；动态网络特征指的是网络在某一时间段内或几个连续的时间段内，发生着不断变化的拓扑结构、节点属性等的特征。可见，动态网络相当于是一个序列的静态网络，这个序列一般指时间序列或周期序列。
在已有的面向动态网络进行链路预测的相关成果中，并不能很好地掌握动态信息的变化规律，未充分利用多个时间段构成的序列信息。本发明将从每个节点出发，进行其出度方向的链路预测。但在预测时，会考虑不同方向的链路在计算网络拓扑相关指标时如何运用，以及节点间建立有向链路的基数约束。
技术实现要素：
目前已经证明，深度学习算法lstm(longshort-termmemory，长短期记忆网络)是解决序列依赖问题的有效技术，其能把握序列数据的发展趋势，普适性非常高；而dnn适用于非序列数据，一般情况下，相较于启发式方法或传统的机器学习算法，其分类或预测的准确性相对较优。因此，本发明分别利用dnn和lstm算法来处理候选邻居节点的一次快照特征和序列特征，设计了一种基于深度学习算法的链路预测模型cfsf(currentfeatures&sequencefeatures)，以解决分布式大规模动态网络中的有向链路预测问题，提高链路预测准确性。模型包括以下内容：
1.模型包括对拥有全部候选节点最近n个周期结束时的网络结构和属性特征时的链路预测和未拥有全部候选节点最近n个周期结束时的网络结构和属性特征时的链路预测，最终根据链接基数约束条件，基于预测中使用的回归算法的输出和设定的阈值，获得有向链路预测结果；
2.当拥有全部候选节点最近n个周期结束时的网络结构和属性特征时，将利用回归lstm算法，得出回归值，最终在回归值大于设定阈值的节点中，按回归值从大到小确定下一轮的直接邻居，获得链路预测结果；
3.当未拥有全部候选节点最近n个周期结束时的网络结构和属性特征时，针对拥有其最近n个周期结束时的网络结构和属性特征记录的这一部分候选节点，基于回归lstm，得出回归值，将回归值大于预先设置的阈值的节点，形成子候选集1；针对未拥有其最近n个周期结束时的网络结构和属性特征记录的候选节点，如候选节点当前为主体节点直接邻居，则基于dnn1网络得出回归值，回归值大于预先设置的阈值的节点，形成子候选集2，否则，将基于dnn2网络得出回归值，回归值大于预先设置的阈值的节点，形成子候选集3；然后，按子候选集1>2>3的优先选择顺序，在每个子候选集内，按回归值从大到小选取节点作为下一周期直接邻居，获得链路预测结果。
建立在足够数据量之上的基于学习的链接预测方法，其准确率比基于链路预测指标的启发式方法高。因此，本发明抽取了每次链路维护前节点间的相关指标特征，利用当前特征向量和序列特征向量，基于深度学习算法dnn和lstm，提出了cfsf链路预测模型，该模型的一个显著优点即可挖掘出节点性能的变化规律，进而提高链路预测的准确性。
附图说明
图1为cfsf模型的链路预测流程。
图2为训练cfsf模型中lstm网络的示意图。
图3为训练cfsf模型中dnn1和dnn2网络的示意图。
具体实施方式
下面结合附图对本发明作进一步说明，构成本发明的一部分。所应理解的是，此处所述仅为本发明的具体实施个例，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内所做的任何等同替换或改进等，均应包含在本发明的保护范围之内。
如图1所示，cfsf模型的链路预测流程如下：
1)如拥有主体节点全部候选节点的最近n个周期结束时的特征，则利用lstm得出的回归值确定下一周期的邻居节点，该回归值指节点预测下一周期如与该候选节点链接，下一周期结束时其能高于设定的链路断开阈值从而继续保持链接的概率值；
2)如并未拥有主体节点全部候选节点的最近n个周期结束时的特征，则针对其中拥有的一部分候选节点，利用lstm得出邻居子候选集1；
3)针对未拥有最近n个周期结束时特征的候选节点，如其是当前邻居，则利用dnn1得出邻居子候选集2，如不是当前邻居，利用dnn2得出邻居子候选集3；
4)因lstm能抓住动态变化规律，预测结果较dnn更加准确，加上对当前轮链接的候选邻居内容属性特征把握较全面，且能尽量避免与当前邻居断开与再与其它节点链接的时间开销等原因，设计按子候选集1>2>3的优先选择顺序，根据邻居数量最大阈值，在每个子候选集内按回归值从大到小选取下一周期直接邻居。
下面，将具体介绍cfsf模型所涉及的相关深度学习网络是如何训练的。
1)如图2所示，训练lstm时的输入和标签设计如下：
以ui链路预测主体节点；以ui的每一个当前候选邻居节点ui′为对象，当拥有它们大于等于n个连续周期结束时的相关数据特征，且ui′在n 1周期与ui为邻居关系时，每次输入一个节点n个周期的序列特征；如第n 1个周期结束时，节点因低于ui设定的执行性能要求阈值而被断开链接，标签为0，否则为1。
2)如图3所示，训练dnn1和dnn2时的输入和标签设计如下：
训练dnn1的数据集为：针对ui每一周期(如第k个周期)的每一个直接邻居节点ui′，如ui′在下一周期(如第k 1周期)继续与ui保持链接，则提取ui′在周期k结束时的特征，形成特征向量；在k 1周期结束时，如ui′因低于ui设定的执行性能要求阈值而被断开链接，则该特征向量对应的标签为0，否则为1。
训练dnn2的数据集为：针对ui每一周期(如第k个周期)的每一个非直接邻居候选节点ui′，如ui′在下一周期(如第k 1周期)为ui的直接邻居，则提取ui′在周期k结束时的特征，形成特征向量；在k 1周期结束时，如ui′因低于ui设定的执行性能要求阈值而被断开链接，则该特征向量对应的标签为0，否则为1。
上述说明示出并描述了本发明的优选实施例，应当理解本发明并非局限于本文所披露的形式，不应看作是对其他实例的排除，而可用于各种其他组合、修改和环境，并能够在本文发明构想范围内，通过上述教导或相关领域的技术或知识进行改动。而本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。
1.一种基于深度学习算法的有向链路预测模型(1)，其特征在于是否拥有主体节点的链接候选节点最近n个周期结束时的网络结构和属性特征，即分为拥有全部候选节点最近n个周期结束时的网络结构和属性特征时的链路预测(11)和未拥有全部候选节点最近n个周期结束时的网络结构和属性特征时的链路预测(12)，最终根据链接基数约束条件，基于预测模型中使用的回归算法的输出值和设定的阈值，获得有向链路预测结果(13)。
2.根据权利要求1所述的拥有全部候选节点最近n个周期结束时的网络结构和属性特征时的链路预测(11)，其特征在于将利用回归lstm算法，得出回归值，最终在回归值大于设定阈值的节点中，按回归值从大到小确定下一轮的直接邻居，获得链路预测结果(13)。
3.根据权利要求1所述的未拥有全部候选节点最近n个周期结束时的网络结构和属性特征时的链路预测(12)，其特征在于面向拥有其最近n个周期结束时的网络结构和属性特征记录的这一部分候选节点，基于回归lstm得出回归值，回归值大于预先设置的阈值的节点，形成子候选集1(121)；面向未拥有其最近n个周期结束时的网络结构和属性特征记录的候选节点进行链路预测时(122)，如候选节点当前为主体节点直接邻居，则基于dnn1网络得出回归值，回归值大于预先设置的阈值的节点，形成子候选集2(1221)，否则，将基于dnn2网络得出回归值，回归值大于预先设置的阈值的节点，形成子候选集3(1222)；然后，按子候选集1>2>3的优先选择顺序，在每个子候选集内，按回归值从大到小选取节点作为下一周期直接邻居，获得链路预测结果(13)。
技术总结