复杂系统通常都可以通过网络表示，其中节点表示系统中的个体或诸多对象，边则表示个体或对象间的关系^{[1, 2]}。随着互联网的快速发展，形成了诸如Facebook、人人网、微博等社交网络，使得人与人之间的交流变得更加便利。因此，开展此类数据分析，提取网络特征是一项非常有意义的工作。网络的社会分析也成为近年来统计学、计算机科学、物理学、社会科学等研究领域的一个热点，其中链接预测是网络分析中的一个基本问题。

链接预测是指通过网络已知的连接边及节点属性或网络结构等信息，预测未连接边的2个节点之间产生连接的可能性。近年来，基于网络结构和节点属性的链接预测方法受到广泛关注^{[3, 4]}，例如O′Madadhain等^[5]利用节点属性以及网络的拓扑结构信息，建立了一个局部条件概率模型并以此进行预测；Bai等^[6]通过结合RA指标和LP指标提出了一个半局部相似性指标(即RALP指标)，实验得出该指标在网络的链接预测中优于RA和LP指标。

链接预测的许多算法已被应用于很多真实的网络，但是这些学习算法很少考虑网络中边的权重信息。Murata和Moriyasu^[7]提出了共同邻居(CN)、Adamic-Adar(AA)、偏好连接(PA)3个相似性指标及其加权形式，并将其应用于Question-Answer Bulletin Boards System网络。结果显示，考虑权重信息提高了链接预测精度，但在共同作者网络和美国航空网络中加权指标预测结果反而比无权的差，即所谓的“弱连接”效应。Zhou等^[8]研究了CN、AA、RA指标以及其加权形式等在3个真实网络中的预测效果，验证了链接预测问题中存在的“弱连接”效应。进而，Wang等^[9]考虑了网络节点的邻域结构信息，提出了将网络中每条边的簇系数作为其权重的方法，研究了CN、AA、RA、LP 4种相似性指标在8个真实网络中的链接预测情况，实验结果表明，当以边的簇系数作为权重时，可以有效提高加权网络的链接预测精度。一个很自然的问题是，能否将RALP指标应用于考虑结构权重或者同时考虑结构权重和真实权重信息时的网络链接预测情况呢？

本文中，我们将考虑网络的结构权重信息，研究RALP等指标在这些真实网络中的链接预测效果。通过研究，我们发现无论是无权网络还是加权网络，当其考虑结构权重信息时对于RALP、RA和LP指标都能有效提高网络的链接预测效果，同时RALP指标的预测结果优于RA指标和LP指标。

我们考虑简单无向网络G(V,E)，其中V表示节点集，E表示边集合，并且忽略节点间多边信息和同一节点自连接信息。对于每一对节点x,y∈V，根据文中所提相似性指标计算数值S_xy，其中S_xy表示2个节点x和y间的相似性，值越高表示两节点越相似。

1)资源分配(RA)指标：Zhou等^[10]提出了资源分配指标,其定义为

点击浏览公式

式中，k(z)表示节点z的度，Γ(x)表示节点x的邻居。

2)局部路径(LP)指标：Zhou等^{[10, 11]}提出基于局部路径的相似性指标。其定义为

点击浏览公式

式中，(A²)_xy表示节点x和节点y之间长度为2的路径数目，(A³)_xy表示节点x和节点y之间长度为3的路径数目，ε=0.001为可调参数。

3)沿局部路径的资源分配(RALP)指标：Bai等^[6]提出了将资源分配过程结合到局部路径中得到了一个新的指标。其定义为

点击浏览公式

式中，l_x→y表示从节点x到节点y的长度为3的路径，i和j是路径l_x→y中的2个节点。

上述3个相似性指标都是基于无权网络定义的，然而在真实世界中，网络中的边通常都含有权重信息。因此当考虑权重信息时，上述3个相似性指标的加权形式可定义如下：

1)加权RA(WRA)指标：

点击浏览公式

式中，w_xz表示2个节点x和z之间边的权重，且w_xz为节点z的度。

2)加权LP(WLP)指标：

点击浏览公式

3)加权RALP(WRALP)指标：

点击浏览公式

本文结合RALP、RA和LP 3个加权相似性指标与结构权重信息，推广了Zhou等^[8]和Bai等^[6]的工作，分别对4个无权网络和3个加权网络进行了研究。由于在真实世界中，一些网络中的边是不含权重信息的，所以为了研究和提高无权网络的链接预测精度，以结构权重作为网络中边的权重，研究RALP、RA和LP 3个指标的链接预测问题。同时为了比较，也研究了无权网络在不考虑结构权重信息时的链接预测情况。其中结构权重(主要研究边的簇系数)^[9]表示真实网络中边存在的概率，其定义为：

点击浏览公式

式中，N_ij表示共同邻居的个数。

当然，有些网络中的边是含有权重信息的。所以，为了研究和提高这些加权网络的链接预测效果，我们分别以网络的真实权重、结构权重、两者结合后的值作为边的权重，研究RALP、RA、LP 3个指标的预测情况。其中分别采用3种方式结合真实权重和结构权重：平均值法、最小值法、最大值法。

由于研究的是无向网络，所以相似性数值是对称的，即S_xy=S_yx。将所有未连接的边根据它们的数值按降序排列，排在最前面的是最可能存在的边。对于网络，我们随机抽取观测边E的80%作为训练集E_T，剩下的20%作为测试集E_P，用于检验算法的有效性。显然，E=E_T∪E_P且E_T∩E_P=Φ。衡量链接预测算法精确度的指标包括AUC、精确度和排序分，这里我们利用AUC来衡量链接预测算法的精确度。在大样本情况下，可以采用抽样的方法得到近似值。事实上，AUC可以理解为在测试集中随机选择一条边的分数值比随机选择的一条不存在的边的分数值高的概率。在实验中，独立比较n次，如果有n′次测试集中的边分数大于不存在的边分数，有n″次分数值相等。那么AUC可定义为：AUC=。如果分数都是随机产生的，可取AUC≈0.5。可见，AUC大于0.5的程度衡量了算法在多大程度上比随机选择的方法精确。

选用UCI数据库中来自不同领域的7个网络，并忽略网络中边的方向。其中这7个网络分别为：空手道俱乐部、海豚社会网络、美国大学橄榄球、美国政治书籍网络、线虫的神经网络、孤星泪网络小说中的人物共性网络、国航空网络。

研究了无权网络和加权网络。实验1中将网络结构权重作为无权网络的权重，作为比较，同时也研究在其不考虑结构权重信息时的链接预测能力，结果如表 1所示。

在实验2中，分别以网络的真实权重、结构权重、两者结合后的值作为边的权重，结果如表 2所示。

通过比较，发现以结构权重作为网络边的权重时，提高了网络的链接预测精度，且实验2中同时考虑结构权重和真实权重(尤其是取两者中最小值)时也提高了网络的链接预测效果，而且RALP指标的预测精度比RA指标和LP指标的高。

其中，每个数值都是将数据随机独立分成训练集和测试集进行10次实验平均得到的，ε=0.001。“无权”、“结构权重”、“真实权重”、“最小值权重”分别表示不含权重时、以结构权重作为边的权重时、以网络本身含有的权重、取真实权重和结构权重两者中最小的值作为网络中边的权重时的链接预测。

本文中，我们根据网络的结构权重(边的簇系数)，研究了3个相似性指标在7个真实网络中的链接预测情况。研究发现，当网络中考虑结构权重信息时，可有效提高网络的链接预测效果，而且RALP指标的预测精度优于RA和LP指标。当加权网络中同时考虑结构权重和真实权重(尤其是取两者中最小值)时也改善了网络的链接预测效果。从实验结果可知：结构权重在提高网络的链接预测过程中起了很重要的作用；而且加权RALP指标的预测效果也得到改善。