开放科学（资源服务）标志码（OSID）：

0 概述

随着网络科学的不断发展，在社会科学、自然科学、信息科学等领域中的复杂关系问题都可以通过复杂网络来描述^[1]。在复杂网络中通常出现网络未知或部分未知的情况，因此，对缺失信息的还原和预测是网络研究过程的关键。链路预测是根据已知的网络信息，预测尚未形成连边的两个节点之间产生链接的可能性，以预测未知链接^[2]和未来链接^[3]。链路预测被广泛应用在不同领域中，例如，在蛋白质网络中探究蛋白质之间的相互作用^[4-5]，在电商网络中推送客户感兴趣的产品^[6]，在社交网络中推荐可能认识的人^[7]，在航空网络中推测影响网络演化的重要因素^[8]等。

现有链路预测方法从结构相似性^[9]角度可以分为基于局部结构的方法（如共邻节点指标（CN）^[10]、Adamic-Adar（AA）^[11]、资源分配指标（RA）^[12]等）、基于半局部结构的方法（如局部路径指标（LP）^[13]）和基于全部结构的方法（如考虑全局路径的Katz指标^[14]、节点偏好性随机游走指标（DRW）^[15]）。基于局部结构的方法因计算复杂度低、适用性广等优点备受研究人员的关注^[16]，但这类方法大多简单地假设每个共邻节点对链路形成的贡献一致。为此，文献[17]提出局部朴素贝叶斯（LNB）模型，引入朴素贝叶斯理论来区分不同共邻节点的贡献，取得了较优的预测效果。文献[18]提出树增广朴素贝叶斯预测（TAN）方法，引入树增强朴素贝叶斯概率模型，缓解在共邻节点之间强独立性假设的问题。文献[19]提出扩展局部朴素贝叶斯（ELNB）方法，通过对共邻节点的角色贡献函数进行扩展，揭示了微观尺度下节点聚类系数对链路形成的作用。但这些方法都是基于共邻节点的角色贡献展开研究，忽略了路径结构特征的贡献。近年来，已有研究表明，考虑路径结构周围的拓扑信息能有效提升预测性能^[20-21]。

此外，LNB模型及其相关改进方法并未考虑网络中的模体结构特征，而真实网络（如食物链网络、社交网络）存在大量模体结构。针对含有模体特征的网络，LNB模型仍存在局限性问题。网络模体的概念最早由文献[22]提出，即在真实网络中富集出现的由少量节点形成的小规模同构子图。文献[23]提出模体顶点度和边度来衡量网络中点和边的重要性。文献[24]提出三角模体度和四边模体度的代数算法，设计基于模体特征的攻击策略。文献[25]依据朴素贝叶斯理论解释了使用模体边度进行链路预测的可行性，提出基于单模体边度和双模体边度的链路预测方法，揭示了模体对链路形成的重要作用。随着模体在复杂网络中深入研究，模体顶点度和边度已经不足以描述更复杂的拓扑特征，基于路径结构的模体测度量有待提出。

本文结合路径模体特征与朴素贝叶斯理论，提出一种基于模体的局部朴素贝叶斯链路预测方法MLNB，以分析路径结构的模体特征对节点相似性的影响。定义路径结构上三角模体的聚集程度——模体密度，考虑模体密度对待测连边的影响，通过构建路径的角色贡献函数分析路径的相似性贡献，同时推导出基于共邻节点的扩展指标。

1 基本概念 1.1 问题描述

本文给定一个无权无向网络$ G=(V, E) $，不考虑网络中的重边和自环，其中$ V $和$ E $分别表示网络中所有节点的集合和所有边的集合，全集$ U $表示所有可能边的集合。$ {e}_{xy}\in E $表示节点$ x $和节点$ y $存在连边，$ {\stackrel{-}{e}}_{xy}\notin E $表示节点$ x $和节点$ y $不相连。网络中节点总数为$ \left|V\right|=n $，边的总数为$ \left|E\right|=m $，最大可能的边的数量为$ \left|U\right|=\frac{n(n-1)}{2} $。节点$ x $的邻居集合用$ \mathit{\Gamma } \left(x\right) $来表示，节点$ x $和节点$ y $的共邻节点集合表示为$ \mathit{\Gamma } (x, y)=\mathit{\Gamma } \left(x\right)\bigcap \mathit{\Gamma } \left(y\right) $。链路预测的目标是寻找集合$ U-E $中缺失或暂未连接的边。

1.2 相关指标

在现有链路预测方法中常用的相似性指标主要有8个：

1）共邻节点指标。对于待预测节点$ x $和节点$ y $，如果共邻节点个数越多，则$ x $和$ y $连边的可能性越大。通过节点对$ x $和$ y $的相似性得分计算它们共邻节点的个数，如式（1）所示：

$ {S}_{xy}^{\mathrm{C}\mathrm{N}}=\left|\mathit{\Gamma } \right(x, y\left)\right| $

(1)

2）Adamic-Adar指标。AA指标考虑共邻节点的度越小对链路形成的贡献越大，在CN指标的基础上为每个共邻节点分配一个权重，权值定义为该共邻节点度的对数的倒数。AA指标定义如式（2）所示：

$ {S}_{xy}^{\mathrm{A}\mathrm{A}}=\sum\limits_{\omega \in \mathit{\Gamma } (x, y)}\frac{1}{\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{a}}{k}_{\omega }} $

(2)

其中：$ {k}_{\omega } $为节点$ \omega $的度。

3）资源分配指标。对于未连接的节点$ x $和节点$ y $，在资源从节点$ x $传递到节点$ y $的过程中，每个共邻节点的资源传输量与其度值成反比。RA指标定义如式（3）所示：

$ {S}_{xy}^{\mathrm{R}\mathrm{A}}=\sum\limits_{\omega \in \mathit{\Gamma } (x, y)}\frac{1}{{k}_{\omega }} $

(3)

4）基于CN指标的局部朴素贝叶斯相似性指标（LNBCN）。在CN指标的基础上，LNBCN^[17]考虑不同共邻节点对链路形成的贡献不同，定义了角色函数$ {R}_{\omega } $来度量每个共邻节点的贡献，如式（4）所示：

$ {S}_{xy}^{\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{C}\mathrm{N}}=\sum\limits_{\omega \in \mathit{\Gamma } (x, y)}({{\rm{log}}}_{a}s+{{\rm{log}}}_{a}{R}_{\omega }) $

(4)

其中：$ s $为节点$ x $和$ y $相连的概率与不相连概率的比值。

5）基于AA指标的局部朴素贝叶斯相似性指标（LNBAA）。将局部朴素贝叶斯原理与AA指标相结合，LNBAA定义如式（5）所示：

$ {S}_{xy}^{\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{A}\mathrm{A}}=\sum\limits_{\omega \in \mathit{\Gamma } (x, y)}\frac{1}{\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}{k}_{\omega }}(\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}s+\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}{R}_{\omega }) $

(5)

6）基于RA指标的局部朴素贝叶斯相似性指标（LNBRA）。将局部朴素贝叶斯原理与RA指标相结合，LNBRA定义如式（6）所示：

$ {S}_{xy}^{\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{R}\mathrm{A}}=\sum\limits_{\omega \in \mathit{\Gamma } (x, y)}\frac{1}{{k}_{\omega }}(\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}s+\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}{R}_{\omega }) $

(6)

7）局部路径指标。不同于上述6种局部指标，LP指标是一种半局部指标，不仅考虑了二阶路径（即共邻节点）的贡献，也考虑了三阶路径对节点相似性的贡献。LP指标计算如式（7）所示：

$ {\mathit{\boldsymbol{S}}}_{}^{\mathrm{L}\mathrm{P}}={\mathit{\boldsymbol{A}}}^{2}+\alpha {\mathit{\boldsymbol{A}}}^{3} $

(7)

其中：$ \mathit{\boldsymbol{A}} $为网络的邻接矩阵；$ {\mathit{\boldsymbol{A}}}^{2} $和$ {\mathit{\boldsymbol{A}}}^{3} $分别为待测节点对的二阶路径数和三阶路径数；$ \alpha $为控制三阶路径权重的可调参数，一般取值为0.01。

8）Katz指标。全局相似性指标Katz计算节点$ x $和$ y $之间所有路径的贡献，其定义如式（8）所示：

$ {S}_{xy}^{\mathrm{K}\mathrm{a}\mathrm{t}\mathrm{z}}=\sum\limits_{l=1}^{\infty }{\alpha }^{l}\cdot \left|{{\rm{path}}}_{x, y}^{l}\right|=\\ \;\;\;\;\;\;\;\;{\alpha }^{1}{A}_{xy}^{1}+{\alpha }^{2}{A}_{xy}^{2}+\cdots +{\alpha }^{n}{A}_{{x}{y}}^{{n}} $

(8)

其中：$ \left|\mathrm{p}\mathrm{a}\mathrm{t}{\mathrm{h}}_{x, y}^{l}\right| $为节点$ x $和$ y $之间$ l $阶路径的数目；$ \alpha $为控制各个路径权重的参数。

2 本文方法 2.1 模体理论

模体是一种介于节点和社团之间的网络子图，是在真实网络中频繁出现的结构单元，可以很好地反映网络的结构和功能。模体的基本特性是在真实网络中出现的频率远高于其在规模相同的随机网络中出现的频率。模体的基本统计特征如下：

1）模体的频率。对于给定的含有$ n $个节点的子图$ M $，如果子图$ M $是网络的模体，那么模体$ M $的频率^[22]定义如式（9）所示：

$ f\left(M\right)=\frac{n\left(M\right)}{N} $

(9)

其中：$ n\left(M\right) $表示该子图在真实网络中出现的次数；$ N $表示含有$ n $个节点的子图出现的总次数。

2）模体的$ P $值。模体$ M $在随机网络中出现次数的频率大于节点数量相同的真实网络中出现次数的频率。$ P $值越小，说明真实网络的模体特征越明显^[22]。

3）模体的$ Z $得分。对于模体$ {M}_{i} $，$ {{N}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}}_{i} $表示该模体在真实网络中出现的次数，$ {{N}_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}}_{i} $表示该模体在随机网络中出现的次数。$ {{N}_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}}_{i} $的平均值为$ < {{N}_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}}_{i} > $，标准差为$ {{\sigma }_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}}_{i} $，则模体$ {M}_{i} $在真实网络中的$ Z $得分^[22]如式（10）所示：

$ {Z}_{i}=\frac{{{N}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}}_{i}- < {{N}_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}}_{i} > }{{{\sigma }_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}}_{i}} $

(10)

网络中模体的存在性可以根据上述模体概念和基本统计特征来检验。在大多数无向网络中，三节点模体是最常见的模体结构。三节点构成的两种模体结构如图 1所示。$ \mathrm{\Delta } $型三角模体作为网络中最小的完全图，构成网络中信息传播的局部单元，能反映网络局部结构中的聚集特性。本文基于网络的三角模体特征，提出针对三角模体结构的链路预测方法。

2.2 模体密度的分析与量化

LNBCN指标在CN指标的基础上，区分每个共邻节点对待测连边的不同贡献，进一步提高预测精度，但忽略了经过不同共邻节点的路径对待测连边贡献的差异性。在路径上三角模体的聚集程度即模体密度，对待测节点间连边的产生具有重要影响。本文引入不同的局部结构图进行对比分析，3种不同的节点连接方式如图 2所示。

从图 2可以看出，在3种结构中均有一对待测节点$ x $和$ y $，以及待分析的路径结构$ {w}_{x\omega y} $。从图 2（a）和图 2（b）可以看出，节点$ x $和节点$ y $的度值都相同，3个共邻节点的度值也都相同。但结构1中路径$ {w}_{x\omega y} $的$ \mathrm{\Lambda } $型模体都不构成$ \mathrm{\Delta } $型模体，例如$ {\mathrm{\Lambda }}_{{v}_{1}x\omega } $和$ {\mathrm{\Lambda }}_{x\omega {v}_{2}} $。在结构2的路径$ {w}_{x\omega y} $上$ \mathrm{\Delta } $型模体的聚集程度更高，这说明结构1的路径$ {w}_{x\omega y} $对$ \mathrm{\Lambda } $型模体形成$ \mathrm{\Delta } $型模体起到抑制作用，结构2的路径$ {w}_{x\omega y} $对形成$ \mathrm{\Delta } $型模体有促进作用。对于三节点模体$ {\mathrm{\Lambda }}_{x\omega y} $，结构2比结构1形成三角模体$ {\mathrm{\Delta }}_{x\omega y} $的可能性更大，即节点$ x $和节点$ y $产生连边的可能性更大。从图 2（b）和图 2（c）可以看出，3个共邻节点既具有相同的度值，邻居之间的连边数也相同。根据LNBCN原理，即用节点聚类系数来区分和量化不同共邻节点的贡献，由于在结构2和结构3中共邻节点$ \omega $的聚类系数相同，因此对待测边的贡献相同。从图 2（c）可以看出，以节点$ \omega $为共邻节点的任意待测节点对，例如$ ({v}_{1}, {v}_{2}) $和$ ({v}_{3}, {v}_{5}) $，节点$ \omega $对它们连边的贡献度都是相同的。LNBCN方法仅考虑共邻节点本身的局部特征属性的差异化，却忽略了共邻节点与其待测节点之间连边的局部结构差异。在结构2中路径$ {w}_{x\omega y} $上的$ \mathrm{\Delta } $型模体个数明显更多，模体聚集程度明显高于$ \mathrm{\Lambda } $型模体，说明结构2中路径$ {w}_{x\omega y} $对形成$ \mathrm{\Delta } $型模体$ {\mathrm{\Delta }}_{x, \omega , y} $的促进作用更大，节点$ x $和节点$ y $更有可能形成连边。在结构3中3对待预测节点$ (x, y) $、$ ({v}_{1}, {v}_{2}) $和$ ({v}_{3}, {v}_{5}) $，路径$ {w}_{x\omega y} $、$ {w}_{{v}_{1}\omega {v}_{2}} $和$ {w}_{{v}_{3}\omega {v}_{5}} $上的$ \mathrm{\Delta } $型模体聚集程度各不相同，分别对待测节点产生连边的影响程度也不相同，不能简单地用同一节点聚类系数来度量各自的贡献。此外，从信息传播路径的角度，共邻节点提供二阶传播路径，模体聚集程度越高的二阶路径结构也能提供更多的三阶传播路径，以图 2（b）为例，三阶传播路径有$ {w}_{x{v}_{1}\omega y} $、$ {w}_{x{v}_{2}\omega y} $和$ {w}_{x\omega {v}_{5}y} $，为节点$ x $和$ y $之间信息传播提供更大的可能性。

上述分析表明，节点$ x $和$ y $产生连边的可能性会因路径模体特征的不同而不同。因此，本文考虑到每条路径的模体特征对相似性有一定的影响，通过定义新的模体测度量来描述路径结构上模体的聚集程度。

在复杂网络中边聚类系数是刻画局部三角环聚集程度的重要参数。根据边聚类系数的定义，即一条边的两个端点与其共邻节点之间所构成的三角形数与所有可能包含该边的三角形数的比值^[26]，图 2（b）中节点$ x $和节点$ \omega $形成的连边$ {e}_{x\omega } $的边聚类系数计算如式（11）所示：

$ {C}_{x\omega }=\frac{\left|\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} \right(x, \omega \left)\right|+1}{\mathrm{m}\mathrm{i}\mathrm{n}\{{k}_{x}-1, {k}_{\omega }-1\}} $

(11)

边聚类系数准确地描述了一条边上三角模体的聚集程度。

定义1（模体密度（Motif Density，MD））  对于网络中任意的待测节点$ x $和$ y $，$ \omega $是节点对的共邻节点，将路径$ {w}_{x\omega y} $的模体密度定义为包含路径$ {w}_{x\omega y} $的所有三角模体数目与所有可能包含该路径的三角模体数目的比值，如式（12）所示：

$ {M}_{\mathrm{M}\mathrm{D}}\left({w}_{x\omega y}\right)=\frac{\left|\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} \right(x, \omega \left)\right|+\left|\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} \right(\omega , y\left)\right|+1}{\mathrm{m}\mathrm{i}\mathrm{n}\{{k}_{x}-1, {k}_{\omega }-1\}+\mathrm{m}\mathrm{i}\mathrm{n}\{{k}_{\omega }-1, {k}_{y}-1\}+2} $

(12)

以图 2（b）为例，路径$ {w}_{x\omega y} $的模体密度计算为：

$ {M}_{\mathrm{M}\mathrm{D}}\left({w}_{x\omega y}\right)=\frac{2+1+1}{\mathrm{m}\mathrm{i}\mathrm{n}\left\{\mathrm{5, 6}\right\}+\mathrm{m}\mathrm{i}\mathrm{n}\left\{\mathrm{6, 4}\right\}+2}=\frac{4}{11} $

2.3 基于模体的朴素贝叶斯相似性指标

本文在对路径结构上模体密度进行分析和量化后，基于模体密度来分析路径的相似性贡献，进而在朴素贝叶斯指标的基础上提出改进的链路预测方法。

根据文献[17]，LNB方法将共邻节点$ \omega $的相似性贡献函数计算为待测节点$ x $和$ y $之间连接与不连接的概率之比，如式（13）所示：

$ {R}_{\omega }=\frac{P\left({e}_{xy}\right|\omega )}{P\left({\stackrel{-}{e}}_{xy}\right|\omega )} $

(13)

其中：$ P\left({e}_{xy}\right|\omega ) $为$ \omega $的节点聚类系数，且满足$ P\left({e}_{xy}\right|\omega )+P({\stackrel{-}{e}}_{xy}\left|\omega \right)=1 $。$ {R}_{\omega } $表示共邻节点$ \omega $对待测节点产生连边和不产生连边的贡献比。由于这种贡献函数的定义方式无法区分因路径模体特征不同而产生的贡献，为量化每条路径对节点相似性的影响，采用模体密度来定义路径的角色贡献函数。

定义2（基于路径模体密度的角色贡献函数）  将路径$ {w}_{x\omega y} $的角色贡献函数$ R\left({w}_{x\omega y}\right) $定义为在路径条件下，待测节点产生连边和不产生连边概率的比值，连边概率用模体密度来表示，如式（14）所示：

$ R\left({w}_{x\omega y}\right)=\frac{P\left({e}_{xy}\right|{w}_{x\omega y})}{P\left({\stackrel{-}{e}}_{xy}\right|{w}_{x\omega y})}=\frac{{M}_{\mathrm{M}\mathrm{D}}\left({w}_{x\omega y}\right)}{1-{M}_{\mathrm{M}\mathrm{D}}\left({w}_{x\omega y}\right)} $

(14)

其中：$ P\left({e}_{xy}\right|{w}_{x\omega y}) $表示路径$ {w}_{x\omega y} $对链接形成有促进作用，用该路径的模体密度来计算；$ P\left({\stackrel{-}{e}}_{xy}\right|{w}_{x\omega y}) $表示路径$ {w}_{x\omega y} $对链接形成有抑制作用。由式（14）可知，$ {M}_{\mathrm{M}\mathrm{D}}\left({w}_{x\omega y}\right) $越大，路径$ {w}_{x\omega y} $的促进作用越大，抑制作用越小，路径相似性贡献$ R\left({w}_{x\omega y}\right) $就越大，与2.2节的分析相符。因此，本文利用$ R\left({w}_{x\omega y}\right) $量化路径$ {w}_{x\omega y} $对连边相似性的贡献是准确合理的。

定义3（基于模体的朴素贝叶斯链路预测指标）  根据贝叶斯理论^[17-19]，在所有经过共邻节点路径的条件下，节点$ x $和$ y $连边与不连边概率的计算如式（15）和式（16）所示：

$ P\left({e}_{xy}\right|W(x, y))=\frac{P\left({e}_{xy}\right)\cdot P\left(W\right(x, y\left)\right|{e}_{xy})}{P\left(W\right(x, y\left)\right)} $

(15)

$ P\left({\stackrel{-}{e}}_{xy}\right|W(x, y))=\frac{P\left({\stackrel{-}{e}}_{xy}\right)\cdot P\left(W\right(x, y\left)\right|{\stackrel{-}{e}}_{xy})}{P\left(W\right(x, y\left)\right)} $

(16)

其中：$ W(x, y) $表示经过共邻节点且连接节点$ x $和$ y $的所有路径的集合。

假设每条路径对待测连边的贡献是相互独立的，则：

$ P\left(W\right(x, y\left)\right|{e}_{xy})=\prod\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}P\left({w}_{x\omega y}\right|{e}_{xy}) $

(17)

$ P\left(W\right(x, y\left)\right|{\stackrel{-}{e}}_{xy})=\prod\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}P\left({w}_{x\omega y}\right|{\stackrel{-}{e}}_{xy}) $

(18)

通过式（15）和式（16）相除的方式构建相似性指标，如式（19）所示：

$ \begin{array}{l}{r}_{xy}^{\mathrm{M}\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{C}\mathrm{N}}=\frac{P\left({e}_{xy}\right|W(x, y))}{P\left({\stackrel{-}{e}}_{xy}\right|W(x, y))}=\frac{P\left({e}_{xy}\right)\prod\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}P\left({w}_{x\omega y}\right|{e}_{xy})}{P\left({\stackrel{-}{e}}_{xy}\right)\prod\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}P\left({w}_{x\omega y}\right|{\stackrel{-}{e}}_{xy})}=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\underbrace{\frac{P\left(e_{x y}\right)}{P\left(\bar{e}_{x y}\right)} \prod\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }}(x, y)} \frac{P\left(\bar{e}_{x y}\right)}{P\left(e_{x y}\right)}}_{\text {constant value }}\underbrace{\prod\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }}(x, y)} \frac{P\left(e_{x y} \mid w_{x \omega y}\right)}{P\left(\bar{e}_{x y} \mid w_{x \omega y}\right)}}_{\text {role of } w_{x \omega y}}\end{array} $

(19)

其中：$ P\left({e}_{xy}\right) $和$ P\left({\stackrel{-}{e}}_{xy}\right) $分别表示整体网络中连边存在和不存在的概率，均为常数。$ P\left({e}_{xy}\right) $和$ P\left({\stackrel{-}{e}}_{xy}\right) $的计算如式（20）和式（21）所示：

$ P\left({e}_{xy}\right)=\frac{2\left|E\right|}{\left|V\right|\cdot \left(\right|V|-1)} $

(20)

$ P\left({\stackrel{-}{e}}_{xy}\right)=1-P\left({e}_{xy}\right) $

(21)

显然，$ {s}^{-1}=\frac{P\left({e}_{xy}\right)}{P\left({\stackrel{-}{e}}_{xy}\right)} $也为常数，表示网络中连边存在和不存在的比值，可以忽略。

将式（14）、式（20）和式（21）代入式（19）中，等式两边取对数，得到其简化形式，如式（22）所示：

$ {s}_{xy}^{\mathrm{M}\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{C}\mathrm{N}}=\sum\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}(lo{g}_{a}s+lo{g}_{a}R({w}_{x\omega y}\left)\right) $

(22)

定义4（扩展指标）  基于共邻节点的相似性预测模型有很多经典的预测指标。受LNB模型启发，为进一步验证MLNB方法的有效性，本文把MLNB思想应用到AA指标和RA指标上，得到MLNB扩展指标，如式（23）和式（24）所示：

$ {s}_{xy}^{\mathrm{M}\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{A}\mathrm{A}}=\sum\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}\frac{1}{\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}{k}_{\omega }}(lo{g}_{a}s+lo{g}_{a}R({w}_{x\omega y}\left)\right) $

(23)

$ {s}_{xy}^{\mathrm{M}\mathrm{L}\mathrm{N}\mathrm{B}\mathrm{R}\mathrm{A}}=\sum\limits_{\omega \in \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} (x, y)}\frac{1}{{k}_{\omega }}(lo{g}_{a}s+lo{g}_{a}R({w}_{x\omega y}\left)\right) $

(24)

3 实验与结果分析 3.1 实验数据与预分析

为了评价MLNB指标的预测准确性，本文在Football网络^[27]、USAir网络^[28]、C.elegans网络^[29]、FWMW网络^[30]、FWEW网络^[31]和FWFW网络^[32]这6个真实网络上进行实验。不同的网络具有不同的模体特征。当网络具有显著的模体特征时，挖掘模体特征的链路预测方法在性能上显著区别于传统的链路预测方法。因此，本文在进行仿真实验之前，首先要检验网络模体的存在性。本文基于2.1节的模体基本理论以及Rand-ESU^[33]算法，通过模体发现软件FANMOD对6个网络进行模体存在性检验。6个网络的特征参数及模体存在性检验如表 1所示。从表 1可以看出，$ Z $得分为正数，$ P $值为0，说明以上6种网络都有三角模体特征，可以用来测试MLNB方法的准确度。

3.2 评价指标

为了量化链路预测方法的准确性，一般将边集$ E $随机划分为训练集$ {E}^{T} $和测试集$ {E}^{P} $，满足$ E={E}^{T}\bigcup {E}^{P} $，并且$ {E}^{T}\bigcap {E}^{P}=\mathrm{\varnothing } $。训练集$ {E}^{T} $作为可观察到的已知网络信息用于计算待测节点对的相似性分数。测试集$ {E}^{P} $作为待预测的网络信息用于验证预测的准确性。本文使用AUC（Area Under the Curve）值^[34]、精确度（P）^[35]来评价链路预测方法。AUC从整体上衡量方法的准确性，P衡量局部预测的准确性。

AUC值可解释为随机选择一条缺失边（即$ {E}^{P} $中的边）的分数值大于随机选择一条不存在边（即$ U-E $中的边）的分数值的概率。本文进行$ n $次独立抽取，如果有$ {n}^{\text{'}} $次缺失边的分数值更高，$ {n}^{″} $次抽取两条边的分数值相等。AUC值如式（25）所示：

$ {A}_{\mathrm{A}\mathrm{U}\mathrm{C}}=\frac{{n}^{\text{'}}+0.5{n}^{″}}{n} $

(25)

精确度（P）计算前$ L $条边的预测准确率。将预测边的相似性得分按照降序进行排序，如果在测试集中排名前$ L $的有$ m $条边，那么精确度计算如式（26）所示：

$ P=\frac{m}{L} $

(26)

由于本文选取6个真实网络的规模不同，因此统一将各数据集边数的10%作为$ L $的值。

3.3 仿真实验结果分析

本文实验针对6个具有模体特征的网络进行仿真实验，采用随机抽样方法按9∶1划分训练集和测试集。为了消除随机误差的影响，对每个网络进行100次独立实验并取平均值。本文将提出的MLNBs指标与局部属性的CN指标、AA指标、RA指标、LNBs指标，半局部属性的LP指标和全局属性的Katz指标进行对比。在多个不同类型网络中MLNBs指标与现有指标的AUC值对比如表 2所示。

从表 2可以看出，在每个网络上MLNBs系列指标（MLNBCN、MLNBAA、MLNBRA）的AUC值均优于对应的原始指标（CN、AA、RA）和LNBs指标（LNBCN、LNBAA、LNBRA），表明路径模体密度对链路形成的可能性是有一定的影响。在MLNBs系列指标中，MLNBRA指标的AUC值最高，MLNBAA指标次之，MLNBCN指标最低，这说明惩罚度大的共邻节点能够有效提高预测精度。MLNBRA指标的AUC值在Football网络中仅次于LP和Katz指标，相差不超过1%，在剩余的网络中MLNBRA指标均具有较优的AUC值。LP指标在共同邻居的基础上考虑了三阶路径信息。Katz指标考虑全局信息，时间复杂度相对较高。因此，LP指标和Katz指标的预测精度有一定优势。而MLNBs系列指标计算二阶路径的局部信息，时间复杂度低于LP和Katz指标。本文提出的MLNB方法能解释路径模体聚集程度与节点对链接的关系，且复杂度低于半局部和全局方法，在含有模体的网络上具有较优的适用性。

在FWMW、FWEW、FWFW这3个食物链网络中，MLNBs系列指标的AUC值均优于所有的基准指标。若以次优的全局Katz指标为基准，MLNBs系列指标的AUC值在FWMW网络中至少提升了5%，在FWEW网络中至少提升了2%，在FWFW网络中至少提升了7%。从表 1可以看出，FWMW、FWEW、FWFW网络的三角模体平均频率较大，说明食物链网络中存在大量的三角模体，对于这类模体特征较为明显的网络，基于模体特征的MLNB方法预测的效果更好，进一步验证了MLNB指标针对此类网络具有一定的的有效性和可行性。

在不同类型网络中MLNBs系列指标与现有指标的精确度对比如表 3所示，所有指标的预测结果在0~0.28，大多数指标的精确度小于0.2。

在USAir网络中，MLNBs系列指标（MLNBCN、MLNBAA、MLNBRA）的精确度不仅优于对应的原始指标（CN、AA、RA）和LNBs系列指标（LNBCN、LNBAA、LNBRA），而且相对半局部LP指标和全局Katz指标也有明显提升。其中MLNBRA指标的精确度最优，RA和LNBRA指标的精确度次优。精确度分析结果说明在USAir网络中，共邻节点的度对链路的形成具有较大作用。在剩余的网络中，MLNBs系列指标的精确度均优于所有的基准指标。在所有网络中，MLNBs系列指标的精确度由大到小排序：MLNBRA > MLNBAA > MLNBCN。从表 3可以看出，基于模体特征的MLNB指标的精确度相比局部和全局指标有较大幅度提升，证明了计算模体结构信息有助于提升预测性能。

3.4 鲁棒性分析

为了进一步分析MLNBs指标的鲁棒性，本节在不同的训练集比例下研究MLNBs指标与基准指标预测结果的变化情况。在不同网络中各指标的预测值仍然是取100次独立实验的平均值。当训练集比例从0.6开始每次增加0.1直到0.9时，各指标的AUC值对比如图 3所示。

从图 3可以看出，当训练集比例增加时，多数指标的AUC值随之增大，这是由于训练集比例增加使网络中共邻节点数目和已知拓扑信息增加，预测性能也随之提升。MLNBs指标的AUC值随训练集比例增大而增大。当可观测数据仅有60%时，除了USAir和C.elegans网络中MLNBs指标相对局部相似性指标变化范围不大，在其余网络中仍取得相对较优的预测结果，表明MLNBs指标在不同网络中具有较优的鲁棒性。LNBs指标在FWMW、FWEW、FWFW网络中并不遵从预测值随训练集比例增大而增大的规律，说明这3个网络中LNBs指标对训练集比例变化的敏感程度不同。

当训练集比例从0.6开始每次增加0.1直到0.9时，各指标的精确度对比如图 4所示。

与AUC值的变化规律相反，图 4中各指标的精确度随训练集比例的增加而下降，这是由于精确度计算前$ L $条边预测的准确率，训练集比例越大，前$ L $条预测边在测试集中的可能性越小，精确度就越小。当可观测数据仅有60%时，在各网络中MLNBs指标（MLNBCN、MLNBAA、MLNBRA）的精确度均优于对应的原始指标（CN、AA、RA）和LNBs指标（LNBCN、LNBAA、LNBRA），相对LP和Katz指标也有明显提升，这表明MLNBs指标具有较优的鲁棒性。

无论训练集如何划分，在图 3中Football和C.elegans网络上的LP、Katz指标相较于MLNBs指标的AUC值有一定的优势，而图 4中LP、Katz指标的精确度都低于MLNBs指标，说明LP和Katz指标并不是在所有评价指标下都表现良好。因此，MLNBs指标在AUC值和精确度两种评价指标测试下具有较优的性能，与不同基准指标相比，在各网络中具有较优的鲁棒性。

4 结束语

本文针对具有模体特征的网络提出一种基于模体的朴素贝叶斯链路预测方法。从模体角度定义模体密度来描述路径结构上模体的聚集程度。考虑到路径结构上模体密度对链接形成的作用，构建基于路径的角色贡献函数，以量化路径的相似性贡献。在此基础上，结合朴素贝叶斯理论，推导MLNBCN及其扩展指标。实验结果表明，本文方法具有较优的鲁棒性，所提相似性指标的AUC值和精确度均优于LNBs指标和CN、AA、RA等基准指标。本文所提的链路预测方法仅针对无权无向、含有模体结构的网络，后续将本文方法MLNB应用到加权有向网络中，研究加权有向网络的模体特征对链路预测准确度的影响。此外，设计适用于更多不同领域网络的链路预测方法也是下一步的重点研究方向。