0 引言

随着复杂网络研究的不断深入，越来越多的复杂系统都成为了复杂网络的研究对象^[1-5]。链路预测作为网络科学领域的研究热点，主要用于预测网络中任意两个节点间连接的可能性^[6]。链路预测方法在实际应用中受到广泛关注，其可以预测发现生物蛋白质网络中未知的连接^[7]、预测人际关系网络中将来可能发生的连接^[8]以及纠正航空运输网络中错误的统计连接^[9]等。

当前，基于复杂网络拓扑演化机制，已经提出许多相关的链路预测方法。其中，基于拓扑结构的相似性方法具有简单、高效、低复杂度的特点，受到普遍关注^[10]。根据算法的复杂度和涉及网络结构的范围，相似性链路预测方法可以分为局部相似性指标和全局相似性指标^[11]。局部相似性链路预测方法包括直接计算共同邻居数目的共同邻居(Common Neighbor, CN)指标^[12]、对共同邻居进行加权的资源分配(Resource Allocation, RA)指标^[13]和Adamic-Adar (AA)^[14]指标以及考虑了三阶路径的局部路径(Local Path, LP)指标^[15]，当然也有对RA指标的拓展(Extend Resource Allocation, ERA)^[16]以及基于随机游走的链路预测方法^[17]，均取得了较好的效果。虽然局部相似性指标在较低的时间复杂度上取得了较好的效果，但为了进一步提高预测精度，又提出了许多全局相似性指标，如：Katz指标、LHN-Ⅱ^[18]指标、平均通勤时间(Average Commute Time, ACT)和余弦相似性指标^[19]。虽然多数全局相似性指标能够取得较好的预测效果，但具有较高的时间复杂度，难以应用到大型实际网络中。许多相似性方法忽略了节点和共同邻居节点之间紧密性的影响，且仅仅关注准确性评价指标，缺少对精确度指标的关注。而实际网络应用如蛋白质网络的链路预测中，会更多地关注排名靠前的连接的预测精度。因此，提高链路预测方法的精确度同样具有重要的实际意义。

在人际交互网络中，如果两个陌生人和共同好友的联系紧密，其更有可能成为朋友，且联系越紧密，其成为朋友的可能性越大。图 1所示两对不同的节点均包含一个共同邻居节点。根据CN、RA、AA和LP等局部相似性指标，两对节点之间存在连接的可能性是相同的。但实际情况中，由于节点与其共同邻居之间的紧密性更高(存在多个可能的连接)，所以相比而言它们更有可能建立连接。因此节点间的紧密性对于链路预测的精确性起着较大的作用。

基于上述分析，本文基于节点和共同邻居之间连接的紧密性，提出了一种基于拓扑连接紧密度的相似性链路预测算法，进而提高复杂网络中链路预测的精确度指标。在6个实际网络数据上的实验结果表明，相比CN、RA、AA、LP和Katz，该方法具有较高的预测精度。

1 相关相似性指标

相似性链路预测指标主要根据网络结构特点计算网络中两个未连接节点之间的相似程度。对于一对网络节点来说，算法标定得分值越高，其相似性越高，即存在连接的可能性越大。基于相似性的链路预测方法较多，以下将主要介绍CN、RA、AA和LP四个局部相似性指标以及Katz全局相似性链路预测方法。

1) CN^[12]。通过共同邻居的数目衡量任意未连接的两个节点v_x和v_y的相似度，以Γ(x)表示节点v_x的邻居集合，则共同邻居指标表示为：

$ s_{xy}^{\rm{CN}}=|\mathit{\Gamma }(\mathit{x})\cap \mathit{\Gamma }(\mathit{y})| $

(1)

2) AA^[14]。在CN的基础上根据共同邻居节点的度为每个节点赋予一个权重，而权重为该节点度的对数分之一，定义为：

$ s_{xy}^{\rm{AA}}=\sum\limits_{\mathit{z}\in |\mathit{\Gamma }(\mathit{x})\cap \mathit{\Gamma }(\mathit{y})|}{\frac{1}{\ln {{k}_{z}}}} $

(2)

3) RA^[13]。对于未连接的两个节点v_x和v_y，从v_x经过共同邻居传递部分资源到v_y，共同邻居传递资源的多少和其节点度成反比，则相似度描述为：

$ s_{xy}^{\rm{RA}}=\sum\limits_{\mathit{z}\in |\mathit{\Gamma }(\mathit{x})\cap \mathit{\Gamma }(y)|}{\frac{1}{{{k}_{z}}}} $

(3)

4) LP^[15]。在二阶路径(共同邻居)上，考虑了三阶路径对相似性的贡献：

$ \mathit{\boldsymbol{s}}={{\mathit{\boldsymbol{A}}}^{2}}+\alpha {{\mathit{\boldsymbol{A}}}^{3}} $

(4)

其中:A为网络的邻接矩阵，α则为调节参数。

5) Katz。考虑了未连边节点之间的所有路径，表示为：

$ s_{xy}^{\rm{Katz}}=\sum\limits_{l=1}{{{\alpha }^{l}}\cdot |path_{xy}^{l}|}=\alpha \mathit{\boldsymbol{A}}+\alpha {{\mathit{\boldsymbol{A}}}^{2}}+ \cdots $

(5)

其中path_xy^l为节点v_x和v_y之间路径长度为l的集合。

上述指标中，CN、RA、AA和LP为局部相似性指标，而Katz则为全局相似性指标，复杂度较高。

2 基于节点间紧密性的相似性链路预测指标

对于一个无权无向网络G(V, E)，V和E分别为网络中点和边的集合。每一个链路预测算法给任意一对网络节点x和y分配一个分数值s_xy用于衡量节点x和y之间的相似性，即存在连接的可能性。在实际网络预测中，通过分数值的高低便可确定连边可能的大小。

网络节点之间的紧密性往往与节点之间存在间接联系的数目有关，共同邻居节点作为大多数相似性指标最为关注的对象，其和两个端点之间的拓扑结构是影响相似性的主要根源。图 2所示，z₁和z₂分别为节点x和y的共同邻居节点。对于共同邻居和节点x之间的紧密性来说，虽然两个共同邻居节点具有相同的节点度(连边数目)，但由于z₁与x之间存在更多的相关边，因此紧密性R(z₁, x) > R(z₂, x)。同理，对于z₁与x、y之间的紧密性来说，R(z₁, x) > R(z₁, y)。基于上述定性讨论，本文将从共同邻居角度分析、定义其周围拓扑结构对于端点之间的紧密性。

定义1  共同邻居紧密度。对于网络中的任意两个节点x和y，其共同邻居节点为z。共同邻居z和节点x的紧密度为在共同邻居z的所有邻居节点中和节点x存在直接联系的比例，具体表示为：

$ R(z, x)={{\left( (\left| \mathit{\Gamma }(x)\cap \mathit{\Gamma }(z) \right|+1)/{{k}_{z}} \right)}^{\delta }} $

(6)

其中δ为调节参数，用于刻画不同具体网络中紧密度的强度。同理，共同邻居z和节点y的紧密度表示为：

$ R(z, y)={{\left( (\left| \mathit{\Gamma }(y)\cap \mathit{\Gamma }(z) \right|+1)/{{k}_{z}} \right)}^{\delta }} $

(7)

紧密度R在一定程度上反映了共同邻居节点和其他节点交互的可能性，且通过一个调节强度的参数来刻画不同实际网络中共同邻居周围结构对于紧密程度的影响。在共同邻居紧密度的基础上，本文进一步提出基于节点间紧密性的相似性链路预测指标，具体定义如下：

定义2  基于节点间紧密性的相似性指标(RC)。对于一个无权无向网络G(V, E)，网络中的任意两个节点x和y，z为共同邻居节点。节点x和y之间的相似性为所有共同邻居节点与其之间紧密度的求和，具体为：

$ s_{xy}^{\rm{RC}}=\sum\limits_{\mathit{z}\in \mathit{\Gamma }(x)\cap \mathit{\Gamma }(y)}{R(z, x)+R(z, y)} $

(8)

当δ=0时，RC指标与CN指标相同。与以图 2为例，对于邻居节点z₁，其紧密度分别为R(z₁, x)=1/2^δ和R(z₁, y)=1/4^δ；而对于邻居节点z₂, 其紧密度分别为R(z₂, x)=1/8^δ和R(z₂, y)=1/4^δ。总体来说，基于节点间紧密性的相似性指标计算图中节点x和y之间相似性为s_xy^RC=2×4^-δ+2^-δ+8^-δ。

具体算法步骤如下：

步骤1  输入训练集网络矩阵；

步骤2  选取一对节点i和j，其中i≠j；

步骤3  寻找节点i和j的共同邻居{z₁, z₂, …}；

步骤4  根据式(8) 计算节点间的相似度，并记录到相似矩阵的i行j列中；

步骤5  返回步骤2，直到所有网络节点对间相似度计算完毕。

算法与CN、RA的复杂度相同，均为O(n²)。相比全局性预测方法，其时间复杂度较低，可以应用于大型复杂网络中。

3 衡量指标与网络数据

本文所关注的链路预测算法衡量标准为精确度指标Precision^[20]。Precision具体为前L个预测边中预测准确的比例，可以表示为：

$ precision\rm{=}\mathit{m}/\mathit{L} $

(9)

其中：m为预测准确的个数，文中设置L=100^[21]。显然，算法的Precision值越大，其预测的精度则越高。许多实际复杂网络如蛋白质网络更多地关注预测结果中排名靠前边的准确性，故越来越多的文章使用Precision作为衡量指标。

为了测试本文方法的有效性，选择了6个常用的复杂网络数据：1) Jazz^[22]，即爵士音乐家合作网络，网络中的节点代表音乐家，而连边则表示音乐家之间存在合作关系；2) Kohonen^[23]，是有关自组织映射主题或T. Kohonen的论文引用网络；3) Hamster^[24]，是在hamsterster.com网页上的用户朋友关系网络，其中点表示网页用户，连边表示他们之间存在朋友关系；4) Metabolic^[25]，即线虫的新陈代谢网络；5) Email^[26]，是一个中型企业的邮件通信网络，节点为员工，连边则表示他们之间的邮件往来；6) Yeast^[27]，是蛋白质相互作用网络，网络节点表示蛋白质，而边则为它们之间的相互作用关系。

上述6个网络具体的特征参数如表 1所示，包含节点数目|V|、边的数目|E|、平均度〈k〉、集聚系数C和匹配系数r。在实验测试中，每个网络数据分为训练集合E^T边数占比为0.9，测试集合E^P则为0.1，每个测试结果均为20次结果的均值。

4 结果及分析

以精确度指标Precision为衡量标准，在6个实际网络中测试基于节点间紧密性的相似性指标的预测效果，具体结果分为两部分：一是不同网络中共同邻居节点集聚性对Precision结果的影响；二是与其他相似性指标的对比结果分析。

4.1 不同网络中精确度结果分析

针对6个实际网络数据，首先了分析不同网络中紧密度参数δ对RC预测结果的影响。图 3中显示了δ > 0时所有网络的Precision曲线。相比δ=0(此时RC即CN指标)，指标均不同程度地提高了其预测精度，且在合适的参数下均可以取得最大预测精度。一般情形下，在取得最大精度值后Precision曲线都会呈现不同程度的下降。但在某些网络如Email、Yeast、Metbolic等网络中，Precision曲线会保持在一定数值之上，这一定程度上说明了在这些网络中紧密度参数在达到一定数值后对相似性的影响就相对稳定。

RC指标的Precision最大精度均高于δ=0时的预测值，这说明了共同邻居的紧密度确实能够提升链路预测中的精确度Precision。同样，相比δ=1时，即共同邻居紧密度没有强度时，最大Precision精度也明显更高，这从另一个侧面表达了紧密度的强度对于Precision的提高具有重要作用。总体来说，在不同的网络数据中，RC均能够在δ > 0时迅速提高预测的Precision值，且一般情形下在δ > 3时取最高点，在实际应用中可在一定范围内调节，可较大程度上提高预测精度。

4.2 与其他相似性指标对比

为了进一步说明RC指标的有效性，以下将与现有的相似性指标进行对比性分析。

表 2显示了各个相似性指标的Precision结果对比，其中每个结果均是20次预测的均值，每次均是独立随机产生训练集和测试集。可以看出，6个实际网络中，相比CN、RA、AA、LP等局部相似性指标和Katz全局相似性指标，RC指标具有较高的预测精度。在局部相似性指标中，CN仅仅利用了共同邻居数量这一信息，表现相对一般；RA和AA利用共同邻居的节点度进行加权，在复杂度较低的情形下，大多数网络中Precision结果明显好于CN；在考虑了三阶路径后，LP指标在多数网络中如Kohonen、Hamster等网络中均表现较好。Katz虽然考虑了网络中所有可能的路径，但其在Precision标准下与LP指标非常接近，且Katz指标的时间复杂度较高。RC指标在考虑了共同邻居与预测节点间紧密度的情况下，取得了较高的预测精度。很明显，在许多集聚系数较低的网络中，多数相似性指标预测精度较低，而RC指标可以极大限度地提高其预测精度，如在Hamster网络中CN的预测精度为0.015，而RC的预测精度为0.186，提高比率为12.4倍。此外，RC的时间复杂度较低，非常适合于大型实际网络中的链路预测。

5 结语

近年来，提出了大量的相似性链路预测方法，许多方法都取得了较好的预测效果。针对现有的方法在精确度衡量标准Precision上效果较差的问题，提出了一种基于拓扑连接紧密度的相似性链路预测算法。6个实际网络数据测试表明，当前方法具有较高的精确度，而且该方法的时间复杂度较低，完全可以用于大型复杂网络的链路预测。本文算法完全基于网络结构进行链路预测，下一步可以结合网络节点属性、行为等多维度信息研究大数据挖掘下的链路预测方法。