·102· 智能系统学报 第14卷 2融合朴素贝叶斯链路预测模型 居间链接的产生有促进作用；节点c和节点d的 共同邻居有3个，但每个共同邻居的邻居之间基 在介绍SNB模型之前，首先考虑一个问题， 本没有链接，说明这些共同邻居对其邻居间链接 节点之间链接的产生到底与什么因素有关？图1 的产生有抑制作用。综上，节点a和b在未来产 给出了3种不同的思路。 生链接的可能性更大。 实际生活中，节点间链接的产生不仅受到共 个个 同邻居的影响，与其自身的活跃程度也是密不可 分的。在共同邻居数目相等的条件下，节点倾向 于和更活跃的个体产生链接；当共同邻居数目不 。共同邻居 等时，如图1(c)中，节点a和b的共同邻居少且均 ·待预测节点对 为促进作用，但其自身的度比较小；节点c与d (a)CNs结构示意 的共同邻居多且均为抑制作用，但其自身的度比 较大。共同邻居与节点自身究竞谁的作用更大， 需要具体计算，这便是SNB模型的核心思想。 本文认为，节点x和y之间链接的产生受到 内部和外部因素的影响。其中，共同邻居的作用 属于外部影响，根据LNB的相关知识，每个共同 。共同邻居 邻居的作用不尽相同，或促进或抑制。另一方 ·待预测节点对 面，链接的产生与节点x和y自身的活跃程度密 (b)LNBs结构示意 切相关，影响大小可以通过节点的度进行量化。 这意味着，度相同的两对节点产生链接的概率会 因共同邻居贡献不同而不同，受共同邻居作用相 同的两对节点也会因其自身的度不同而产生差 异。基于此思想，本文综合考虑了共同邻居与节 点对自身的作用，提出了融合朴素贝叶斯(SNB) 链路预测模型。 。共同邻居 在SNB模型下，节点x和y产生链接的后验 ·待预测节点对 概率为： (c)SNBs结构示意 P(eIN(x,y),k.k,)= 图1CNs、LNBs、SNBs结构示意 P(eg).P(N(x,y),k:,kylex) (10) Fig.1 Structure schematic diagram of CNs,LNBs and SNBs P(N(x,y),kx.ky) 最简单的一种思路是：两节点的共同邻居数 P(@slN(x.y).kx.k,)= (11) 目越多，它们的兴趣属性等越接近，未来越有可 P(e)·PN(x,y,kx,ke) P(N(x,y),kx,k) 能产生链接，这便是图l(a)中CNs指标的主要思 由概率论相关知识，可得： 想。因此，图中节点c和d的共同邻居数目多， P(N(x.y).k.kle)= 它们产生链接的可能性大于节点a和b。 在CNs的基础上，有学者指出，每个共同邻 P(N(x.y)le)P(kleN(x.y))- (12) 居扮演角色不同，对于节点对产生链接的贡献不 P(kleN(x,y).k,) 同，因此不能通过简单计算共同邻居的数目得到 P(N(x,y),k:.kle)= 相似性，而应该累加共同邻居的贡献以得到最终 P(N(x,y))P(ke N(x,y))- (13) 的相似性分数。按照此思想，图1(b)中节点a和 P(kles.N(x,y).k,) b的共同邻居只有2个，但每个共同邻居的邻居 将式(12)和式(13)分别代入式(10)和式(11)， 之间大多存在链接，说明这两个共同邻居对其邻 可得2 融合朴素贝叶斯链路预测模型 在介绍 SNB 模型之前，首先考虑一个问题， 节点之间链接的产生到底与什么因素有关？图 1 给出了 3 种不同的思路。 a b ? ? c d 共同邻居 待预测节点对 (a) CNs 结构示意 a b c d c ? ? 共同邻居 待预测节点对 (b) LNBs 结构示意 a b ? c ? d 共同邻居 待预测节点对 (c) SNBs 结构示意 图 1 CNs、LNBs、SNBs 结构示意 Fig. 1 Structure schematic diagram of CNs, LNBs and SNBs c d a b 最简单的一种思路是：两节点的共同邻居数 目越多，它们的兴趣属性等越接近，未来越有可 能产生链接，这便是图 1(a) 中 CNs 指标的主要思 想。因此，图中节点 和 的共同邻居数目多， 它们产生链接的可能性大于节点 和 。 a b 在 CNs 的基础上，有学者指出，每个共同邻 居扮演角色不同，对于节点对产生链接的贡献不 同，因此不能通过简单计算共同邻居的数目得到 相似性，而应该累加共同邻居的贡献以得到最终 的相似性分数。按照此思想，图 1(b) 中节点 和 的共同邻居只有 2 个，但每个共同邻居的邻居 之间大多存在链接，说明这两个共同邻居对其邻 c d a b 居间链接的产生有促进作用；节点 和节点 的 共同邻居有 3 个，但每个共同邻居的邻居之间基 本没有链接，说明这些共同邻居对其邻居间链接 的产生有抑制作用。综上，节点 和 在未来产 生链接的可能性更大。 a b c d 实际生活中，节点间链接的产生不仅受到共 同邻居的影响，与其自身的活跃程度也是密不可 分的。在共同邻居数目相等的条件下，节点倾向 于和更活跃的个体产生链接；当共同邻居数目不 等时，如图 1(c) 中，节点 和 的共同邻居少且均 为促进作用，但其自身的度比较小；节点 与 的共同邻居多且均为抑制作用，但其自身的度比 较大。共同邻居与节点自身究竟谁的作用更大， 需要具体计算，这便是 SNB 模型的核心思想。 x y x y 本文认为，节点 和 之间链接的产生受到 内部和外部因素的影响。其中，共同邻居的作用 属于外部影响，根据 LNB 的相关知识，每个共同 邻居的作用不尽相同，或促进或抑制。另一方 面，链接的产生与节点 和 自身的活跃程度密 切相关，影响大小可以通过节点的度进行量化。 这意味着，度相同的两对节点产生链接的概率会 因共同邻居贡献不同而不同，受共同邻居作用相 同的两对节点也会因其自身的度不同而产生差 异。基于此思想，本文综合考虑了共同邻居与节 点对自身的作用，提出了融合朴素贝叶斯 (SNB) 链路预测模型。 在 SNB 模型下，节点 x 和 y 产生链接的后验 概率为: P(exy|N(x, y), kx , ky) = P(exy)· P(N(x, y), kx , ky |exy) P(N(x, y), kx , ky) (10) P(exy|N(x, y), kx , ky) = P(exy)· P(N(x, y), kx , ky |exy) P(N(x, y), kx , ky) (11) 由概率论相关知识，可得： P(N(x, y), kx , ky |exy) = P(N(x, y)|exy)· P(kx |exy,N(x, y))· P(ky |exy,N(x, y), kx) (12) P(N(x, y), kx , ky |exy) = P(N(x, y)|exy)· P(kx |exy,N(x, y))· P(ky |exy,N(x, y), kx) (13) 将式 (12) 和式 (13) 分别代入式 (10) 和式 (11)， 可得: ·102· 智 能 系 统 学 报 第 14 卷