一种基于贝叶斯估计和大度节点不利的链路预测方法

摘要

一种基于贝叶斯估计和大度节点不利的链路预测方法，建立网络模型，任取两个未直接连接的节点作为种子节点，分别计算它们之间存在和不存在连边的概率，根据二节点之间长度为2或3路径中间节点的度信息，分别计算二节点之间产生和不产生连边的概率，根据贝叶斯估计和大度节点不利思想，计算二节点之间长度为2和3路径的每一中间节点的似然值,相似性分数为所有中间节点似然值之和；遍历网络，用上述方法获取任意两个种子节点间相似性分数，将所有种子节点对按相似性分数降序排列，取前B个分数值对应节点对为预测连边。本发明根据贝叶斯估计，结合大度节点不利思想，区分两节点间局部路径中不同中间节点具有不同重要性，算法预测效果好。

权利要求

1.一种基于贝叶斯估计和大度节点不利的链路预测方法，其特征在于：包括以下步骤：步骤一：建立网络模型G(V,E)，V代表网络中的节点集合，E代表网络中的连边集合，网络的节点总数记为N,用U表示网络中节点对的集合，|U|＝N(N-1)/2表示网络中节点对的总数；

步骤二：任意选取网络中的两个未连接节点x和y作为种子节点，计算它们之间存在直接连边的可能性：其中，|E|表示网络中实际存在的连边总数，A1表示x和y两个节点之间存在直接连边；

步骤三：计算网络中任意两个未连接节点x和y之间不存在直接连边的概率：其中，A0表示x和y两个节点之间不存在直接连边；

步骤四：根据节点x和y之间长度为2或者3的路径的一个中间节点Vw的度信息，计算节点x和y之间产生连边的概率：P(A1|Vw)＝Cw

其中，Cw＝2Ew/kw(kw-1),kw表示节点Vw的度数，Ew表示节点Vw的kw个邻居节点之间实际存在的边数；

步骤五：根据节点x和y之间长度为2或者3的路径的一个中间节点Vw的度信息，计算节点x和y之间不产生连边的概率：P(A0|Vw)＝1-Cw；

步骤六：根据贝叶斯估计的方法，计算节点x和y之间长度为2和3的路径的任意一个中间节点Vw的似然值步骤七：对节点x和y之间长度为2和3的路径的每一个中间节点，重复步骤四至步骤六，计算每一个中间节点的似然值步骤八：计算节点x和y的相似性分数：

其中Q表示节点x和y之间长度为2和3的所有路径中的所有中间节点的数量，kx表示节点x的度数，ky表示节点y的度数；

步骤九：遍历整个网络，对任意两个未连接节点，重复步骤二至步骤八，计算所有未连接节点对之间的相似性分数，并按照相似性分数值从高到低排列顺序，取前B个相似性分数值对应的节点对为预测连边，其中，B为设定的一个正整数，B≤D，D为网络中所有未连接节点对的数量。

说明书

一种基于贝叶斯估计和大度节点不利的链路预测方法

技术领域

[0001] 本发明涉及网络科学和链路预测领域，特别是指一种基于贝叶斯估计和大度节点不利的链路预测方法。

背景技术

[0002] 现实生活中的复杂系统可以使用复杂网络进行研究，网络中的节点代表复杂系统中的个体，连边代表系统中节点之间的相互关系。链路预测是复杂网络的重要研究领域之一，因为链路预测可以对网络的演化过程中节点之间可能产生的链路进行预测，所有可以提前预判出网络的演化趋势，并且可以判断出网络中并不存在的“幽灵边”，能够更好的帮助研究人员研究网络的内在规律。

[0003] 链路预测问题受到研究人员的广泛关注。相比较而言，基于网络结构的链路预测算法相对于基于网络节点属性信息的预测算法更加可靠、准确。共同邻居(CN)算法是一种基于网络结构的经典链路预测算法，这种算法又被称为结构等价算法，即节点之间有很多的共同邻居节点，那么这两个节点就越相似，在CN算法的基础之上衍生出的链路预测算法有Salton算法、Jaccard算法、Sorenson算法、HPI(大度节点有利指标)、HDI(大度节点不利指标)、LHN-I算法、AA算法和RA算法等等，其中Salton算法又被称为余弦相似性算法，Sorenson算法常被用于生态学数据的研究，HPI算法常被用来分析新陈代谢网络的拓扑相似性，AA算法的思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，RA算法是在AA算法的基础之上，受资源分配过程的启发而提出来的；基于路径的相似性算法，主要包括了局部路径指标(Local Path，LP)、Katz算法LHN-II算法，这些算法克服了CN算法使用的网络有效信息过少的缺点，从全局的角度利用网络的有效信息，因此，一定程度上提高了链路预测的精确性。

[0004] 上述的一些经典算法主要考虑的是网络中的拓扑结构特性，即两个节点之间的网络特征越相似，那么这两个节点之间越有可能产生链路，这些方法在很多的网络中被证明是很有效果的，但是这些算法只是简单地统计了网络中节点对之间的中间节点的度数，并没有考虑每一个中间节点的其它属性。事实上很多网络中两个节点之间的中间节点对于节点对之间产生链路的作用存在很大的不同，不同的中间节点对于产生链路的贡献也是不相同的。传统的基于大度节点不利的指标并没有对不同的中间节点进行有效的区分。

发明内容

[0005] 为了克服现有的基于大度节点不利的链路预测方法只是简单地考虑了任意两个未连接节点的中间节点的度数，并没有考虑节点其他属性而导致的预测精度不高的不足，本发明提出了一种准确度较高的基于贝叶斯估计和大度节点不利的链路预测方法。

[0006] 本发明解决其技术问题所采用的技术方案是：

[0007] 一种基于贝叶斯估计和大度节点不利的链路预测方法，包括以下步骤：

[0008] 步骤一：建立网络模型G(V,E)，V代表网络中的节点集合，E代表网络中的连边集合，网络的节点总数记为N,用U表示网络中节点对的集合，|U|＝N(N-1)/2表示网络中节点对的总数；

[0009] 步骤二：任意选取网络中的两个节点x和y作为种子节点，计算它们之间存在直接连边的可能性：

[0010]

[0011] 其中，|E|表示网络中实际存在的连边总数，A1表示x和y两个节点之间存在直接连边；

[0012] 步骤三：计算网络中任意两个节点x和y之间不存在直接连边的概率：

[0013]

[0014] 其中，A0表示x和y两个节点之间不存在直接连边；

[0015] 步骤四：根据节点x和y之间长度为2或者3的路径的一个中间节点Vw的度信息，计算节点x和y之间产生连边的概率：

[0016] P(A1|Vw)＝Cw

[0017] 其中，Cw＝2Ew/kw(kw-1),kw表示节点Vw的度数，Ew表示节点Vw的kw个邻居节点之间实际存在的边数；

[0018] 步骤五：根据节点x和y之间长度为2或者3的路径的一个中间节点Vw的度信息，计算节点x和y之间不产生连边的概率：

[0019] P(A0|Vw)＝1-Cw；

[0020] 步骤六：根据贝叶斯估计的方法，计算节点x和y之间长度为2和3的路径的任意一个中间节点Vw的似然值

[0021]

[0022] 步骤七：对节点x和y之间长度为2和3的路径的每一个中间节点，重复步骤四至步骤六，计算每一个中间节点的似然值

[0023] 步骤八：计算节点x和y的相似性分数：

[0024]

[0025] 其中Q表示节点x和y之间长度为2和3的所有路径中的所有中间节点的数量，kx表示节点x的度数，ky表示节点y的度数；

[0026] 步骤九：遍历整个网络，对任意两个未连接节点，重复步骤二至步骤八，计算所有未连接节点对之间的相似性分数，并按照相似性分数值从高到低排列顺序，取前B个相似性分数值对应的节点对为预测连边，其中，B为设定的一个正整数，B≤D，D为网络中所有未连接节点对的数量。

[0027] 本发明的有益效果为：考虑网络中两个未连接节点之间路径长度等于2或3的局部路径，区分网络中的中间节点的度数对产生链路的贡献，提出了一种基于贝叶斯估计和大度节点不利的链路预测方法，链路预测准确度较高。

附图说明

[0028] 图1为网络中的任意一个不存在直接连边的节点对之间的不同中间节点对这个节点对之间产生链路的影响。

具体实施方式

[0029] 下面结合附图对本发明做进一步说明。

[0030] 参照图1，一种基于贝叶斯估计和大度节点不利的链路预测方法，包括以下步骤：

[0031] 步骤一：建立网络模型G(V,E)，V代表网络中的节点集合，E代表网络中的连边集合，网络的节点总数记为N,用U表示网络中节点对的集合，|U|＝N(N-1)/2表示网络中节点对的总数；

[0032] 步骤二：任意选取网络中的两个节点x和y作为种子节点，即图1中黑色圆点表示，计算它们之间存在直接连边的可能性：

[0033]

[0034] 其中，|E|表示网络中实际存在的连边总数，A1表示x和y两个节点之间存在直接连边；

[0035] 步骤三：计算网络中任意两个节点x和y之间不存在直接连边的概率，如图1所示：

[0036]

[0037] 其中，A0表示x和y两个节点之间不存在直接连边；

[0038] 步骤四：根据节点x和y之间长度为2或者3的路径的一个中间节点Vw(如图1所示)的度信息，计算节点x和y之间产生连边的概率：

[0039] P(A1|Vw)＝Cw

[0040] 其中，Cw＝2Ew/kw(kw-1),kw表示节点Vw的度数，Ew表示节点Vw的kw个邻居节点之间实际存在的边数；

[0041] 步骤五：根据节点x和y之间长度为2或者3的路径的一个中间节点Vw(如图1所示)的度信息，计算节点x和y之间不产生连边的概率：

[0042] P(A0|Vw)＝1-Cw；

[0043] 步骤六：根据贝叶斯估计的方法，计算节点x和y之间长度为2和3的路径的任意一个中间节点Vw的似然值

[0044]

[0045] 步骤七：对节点x和y之间长度为2和3的路径的每一个中间节点，重复步骤四至步骤六，计算每一个中间节点的似然值

[0046] 步骤八：计算节点x和y的相似性分数：

[0047]

[0048] 其中Q表示节点x和y之间长度为2和3的所有路径中的所有中间节点的数量，kx表示节点x的度数，ky表示节点y的度数；

[0049] 步骤九：遍历整个网络，对任意两个未连接节点，重复步骤二至步骤八，计算所有未连接节点对之间的相似性分数，并按照相似性分数值从高到低排列顺序，取前B个相似性分数值对应的节点对为预测连边，其中，B为设定的一个正整数，B≤D，D为网络中所有未连接节点对的数量。

[0050] 如上所述，本专利实施的具体实现步骤使本发明更加清晰。在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。