一种基于时间序列的复杂网络链接预测方法

摘要

本发明公开了一种基于时间序列的复杂网络链接预测方法，包括如下步骤：步骤一、使用静态方法对任意两个节点的链接概率进行评分；步骤二、使用时间序列的方法，获取最近不相连的任意两节点的链接出现概率；步骤三、对于使用静态方法计算出的链接出现概率序列p

说明书

技术领域

本发明属于复杂网络链接预测技术领域，特别涉及一种基于时间序列的复杂网络链接预测方法。

背景技术

复杂网络模型是对各种真实存在网络的抽象，比如社交网络、科研合作网络、生物代谢网络等。链接预测，是根据观察到的网络中已有的链接和节点属性信息，来估计两个节点间链接存在的可能性，包括当前存在但是观察不到的链接，以及将来可能出现的链接。作为链接挖掘分析中最重要的问题之一，链接预测有着多种多样的应用：它可以用于推荐系统，帮助人们找到新朋友或潜在的合作者，在网上购物中提供感兴趣的商品；也能用来推断完整的网络结构，更好地理解网络演化；在生物学领域，还能用来发现蛋白质之间的交互情况。

现有的链接预测可以分为两类：静态网络链接预测以及基于时间序列的网络连接预测。

静态方法主要采用网络拓扑信息以及节点属性信息进行链接预测。

时间序列预测方法主要采用不同时间点的网络变化信息对链接进行预测。预测的网络变化需要满足线性变化的条件。

两种方法对任意两个不直接相连节点之间存在链接的概率进行评分，最后通过评分阈值或整体预测比例进行确定存在链接的节点对。然而这种方法对以下两种情况不能很好的预测：第一种是两个节点之间距离较近并且节点较为相似但是网络比较稳定的情况(即：预测出现不应出现的链接)；第二种是两节点之间连接概率随着时间点的推移不断增大但是当前结果并没有达到阈值的情况(即：不能预测应该出现的链接)。

发明内容

本发明的目的是解决现有网络链接预测方法中预测出现不应出现的链接和不能预测应该出现的链接的缺陷，提供了一种基于时间序列的复杂网络链接预测方法。

本发明提供的技术方案为：

一种基于时间序列的复杂网络链接预测方法，包括如下步骤：

步骤一、使用静态方法对任意两个节点的链接概率进行评分；

步骤二、使用时间序列的方法，获取最近不相连的任意两节点的链接出现概率；

步骤三、对于使用静态方法计算出的链接出现概率序列p₁，p₂，…p_k，计算其权值：

W(i)＝α(p_i-p_i-1)+(1-α)W(i-1)i＝2…k

W(1)＝1

其中α为调整系数，k为网络快照个数；

得到最终的链接出现的概率P＝W(k)p_k+1；

步骤四、对步骤三中计算得到的结果进行排序，输出预测的链接。

优选的是，步骤一中，任取节点A和节点B，节点A到节点B的链接概率为

其中为从节点A到节点B的第i条无环路径，为这条路径的长度。

优选的是，步骤一中，节点A到节点B的链接概率评分为：

ε_t是独立同分布的随机变量序列，满足期望为0的条件，Φ_i是不同时刻网络快照的权重。

本发明的有益效果是：本发明提供了一种于时间序列的复杂网络链接预测方法，通过加权算法，使预测结果更为精确。

附图说明

图1为本发明所述的基于时间序列的复杂网络链接预测方法流程图。

图2为第一时刻节点连接示意图。

图3为第二时刻节点连接示意图。

图4为第三时刻节点连接示意图。

图5为第四时刻节点连接示意图。

具体实施方式

下面结合附图对本发明做进一步的详细说明，以令本领域技术人员参照说明书文字能够据以实施。

如图1所示，本发明提供了一种基于时间序列的复杂网络链接预测方法，包括如下步骤：

步骤一：使用静态方法对任意两个节点的链接概率进行评分。在该阶段可以使用网络拓扑，节点属性等信息对。

步骤二：使用时间序列的方法针对所有的静态链接概率评分结果进行计算，得出最近不相连的任意两节点的链接出现概率。

第三步：计算权值。具体方法如下：

对于一个使用静态方法计算出的一个链接出现概率序列p₁，p₂，…p_k，其中k表示时间序列的中时间步的个数，他的权值可以使用以下递归公式计算出来：

W(i)＝α((p_i-p_i-1)+(1-α)W(i-1)i＝2…k

W(1)＝1

对于最终的链接出现的概率计算加权得到：P＝W(k)p_k+1

步骤四：排序所有结果，根据定义好的阈值或比例系数输出预测的链接。

其实现过程如下：

静态方法中使用了拓扑信息，节点A到节点B的链接概率为

其中为从节点A到节点B的第i条无环路径。为这条路径的长度。在时间序列方法中使用了ARMA方法，得到概率评分：

如图2-图5所示，通过静态方法获得的评分如表1-表4所示。

表1：通过静态方法计算出的图2中两个节点链接概率评分

123456781NANANANA2/95/16NA1/82NA5/16NA5/162/91/834/2253NANA1/2NA5/162/94NANA1/22/95/165NANA5/16NA6NANA5/167NA34/2258NA

表2：通过静态方法计算出的图3中两个节点链接概率评分

表3：通过静态方法计算出的图4中两个节点链接概率评分

123456781NANANANA118/22511/16NA11/362NA49/72NA5/9118/22519/363439/110253NANA49/72NA49/723782/110254NANA11/16118/22557/1445NANA5/9NA6NANA57/1447NA3439/110258NA

表4：通过静态方法计算出的图5中两个节点链接概率评分

123456781NANANANA3013/3600131/144NA411/9002NA1319/1800NA1061/1200697/900683/90080749/1764003NANA523/600NA1447/180081337/1764004NANA131/1443013/3600571/12005NANA56/75NA6NANA571/12007NA25283/588008NA

通过时间序列的方法获得的评分如表5所示，其中其中ε_t取值为0，Φ_i＝{0.5，0.3，0.16，0.04}。

表5：通过时间序列方法得出的最终评分

根据时间序列的方法获得的链接可能性排列为：<4，6>,<1，6>,<3，5>,<2，5>,<3，7>,<2，3>,<4，7>,<5，7>,<2，6>,<2，7>,<6，8>,<4，8>,<3，8>,<1，8>,<2，8>,<1，5>。

权值为：

123456781NANANANA0.3030.251NA0.1852NA0.180NA0.3160.2130.2910.0983NANA0.212NA0.1900.2604NANA0.2340.3090.1285NANA0.227NA6NANA0.1287NA0.0988NA

最终的评分为：

123456781NANANANA0.1066560.191764NA0.0663722NA0.11447NA0.2135480.1267350.121790.0346953NANA0.159NA0.1714020.100064NANA0.1804140.1968330.0541445NANA0.139151NA6NANA0.056197NA0.034508NA

加权之后的链接可能性排列为：<2，5>,<4，7>,<1，6>,<4，6>,<3，7>,<3，5>,<5，7>,<2，6>,<2，7>,<2，3>,<1，5>,<3，8>,<1，8>,<6，8>,<4，8>,<2，8>,<7，8>。

和之前的序列相比，节点2和节点5的链接概率以及节点4和节点7的链接概率被提升到最前方，而节点4和节点6的链接概率以及节点1和节点6的链接概率在序列中被后移。通过网络演化可看出，我们解决了前文提及的两个问题。

尽管本发明的实施方案已公开如上，但其并不仅仅限于说明书和实施方式中所列运用，它完全可以被适用于各种适合本发明的领域，对于熟悉本领域的人员而言，可容易地实现另外的修改，因此在不背离权利要求及等同范围所限定的一般概念下，本发明并不限于特定的细节和这里示出与描述的图例。