0 引言

复杂网络链路预测是根据已知、可观察到的节点的拓扑结构、节点属性等特征，预测网络中其他节点之间缺失的链接和未来可能产生的链接^[1]。在社会网络分析、蛋白质交互作用、神经网络、电力网络等领域中，链路预测方法可广泛应用于分析网络数据的缺失、分析复杂网络演化机制等问题，在理论和实际应用中都发挥着巨大的作用，受到各领域的科学家的广泛关注^[2]。

网络结构链路预测方法主要有基于相似性的链路预测、基于最大似然估计的链路预测和概率模型等方法^[3]。基于相似性的方法是目前运用最多的链路预测算法之一，其前提是刻画节点相似性指标，由于基于相似性的方法计算简单、速度快、准确率高，吸引了很多研究学者的关注，但该方法在节点信息使用方面不够充分^[4]。

在复杂网络中，一些具有重要作用的成员节点可能具有更大的影响力或者更强的信息传播能力，网络中节点的重要性可以用节点中心性来表示^[5]。由于社交网络中大量活动都是围绕一些重要成员节点开展或与其具有密切的关系，因此，节点中心性在复杂网络研究中具有重要的理论价值和现实意义。杨建祥等^[6]针对无权网络的介数中心性提出了快速更新算法；李静茹等^[5]将度量节点中心性的方法应用于有权社交网络中，证明了加权网络中节点中心性的有效性及作用。

现有的基于局部相似性的链路预测方法，仅仅考虑了节点度这类局部信息，忽略了节点在网络中的重要程度，导致预测算法正确率降低。本文提出了基于复杂网络节点重要性的链路预测算法，在基于局部信息链路预测相似性指标研究的基础上，考虑了节点在网络中的重要性。本文使用Matlab作为仿真工具，在真实数据集上进行仿真实验，实验结果表明改进的相似性指标在链路预测精度上有了一定的提升。

1 相关工作 1.1 链路预测 1.1.1 问题描述

定义G(V，E)为无向网络，其中V为节点集合，E为边集合。网络中总的节点数为N，边数为M，则该网络最多有N(N-1)/2条链接，记为全局U。链路预测问题可描述为：对于给定的一个网络拓扑，设计一种链路预测方法，对每个未连接的节点对(x，y)∈U-E 赋予分数值S_xy，然后按照该分数值从大到小排序，则排序越靠前的节点对之间就越有可能产生链接关系。

1.1.2 基于相似性的链路预测

应用相似性进行链路预测的重要前提是：假设两个节点之间相似性越大，它们之间存在链接的可能性就越大。如何定义节点之间的相似性成为基于节点相似性的链路预测方法的核心问题，根据不同的相似性度量方法，可将该类相似性指标分为基于局部信息的相似性指标、基于路径的相似性指标和基于随机游走的相似性指标。

基于局部信息相似性链路预测算法出现较早，应用较多，该方法认为两个端点的共同邻居越多则两个节点越相似，它们之间存在链接的可能性越大。共同邻居(Common Neighbor,CN)指标是基于局部信息相似性链路预测算法中衡量节点间相似性最简单的指标，此外，如果考虑共同邻居节点的度，还有优先连接指标^{[3, 7]}、AA(Adamic-Adar)指标及RA(Resource Allocation)指标^[8-9]。

基于路径相似性的链路预测算法从整体网络出发，考虑了所有长度路径的影响。如果两个节点之间最短路径的长度越短，只需要较少个数的节点就能相互访问，说明节点间关系相对密切。该方法需要考虑网络中所有长度的路径，复杂度高，计算开销大，不适合于实际网络应用。基于路径的相似性指标有局部路径指标、 Katz指标和LHN-II(Leicht，Holme,Newman)^[9]等。

基于随机游走的相似性指标根据随机游走模型定义，随机游走指的是任何无规律行走者所带的守恒量都各自对应着一个扩散运输定律^[10]，通常包括平均通勤时间(average commute time)、 Cos+指标、有重启的随机游走(random walk with restart)、SimRank指标^[3]等。

1.2 典型的局部信息相似性指标

基于局部信息相似性的链路预测算法中，最简单的相似性指标是共同邻居(CN)指标，AA指标与RA指标也因考虑了节点度的信息而被广泛应用^[11]。

1) CN指标：共同邻居算法将共同邻居的数量作为衡量两节点间建立直接链路可能性的指标，即两节点间共同邻居越多，产生连接的可能性越大。对于节点x、y，它们的邻居节点集合分别为Γ(x)、Γ(y)，则节点x、y共同邻居集合为Γ(x)∩Γ(y)，CN指标被定义为：

${{S}_{xy}}=\left| \Gamma (x)\cap \Gamma (y) \right|$

(1)

2) AA指标：该算法的思想是度小的共同邻居节点的贡献大于度大的共同邻居节点。例如：在社交网络中，共同关注一个比较冷门话题的两个人之间相连的概率往往会比关注同一热门话题的两个人之间连接的概率高。因此，根据共同邻居节点的度为每个节点赋予一个权重值，AA指标被定义为：

${{S}_{xy}}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\operatorname{lb}{{k}_{z}}}}$

(2)

其中:z为节点x，y的共同邻居;k_z表示节点z的度。

3) RA指标：该算法从资源分配的角度出发，认为网络中每个节点都有一定的资源，并将资源平均分配给它的邻居。网络中没有直接相连的两个节点x、y之间，可从节点x传递一些资源到节点y，在此过程中，节点x和y的共同邻居成为传递媒介。则节点y接收到的资源数就定义为节点x、y的相似度。RA指标被定义为：

${{S}_{xy}}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{{{k}_{z}}}}$

(3)

2 基于节点重要性的链路预测算法 2.1 节点中心性计算方法

在链路预测中，节点的重要性在一定程度上影响了预测的正确性。所谓节点的重要性指的是节点在网络中的地位，也可以看作节点在网络中的影响力^[12]。目前，人们对节点影响力已有很多研究。评价节点影响力的方法有度中心性(Degree Centrality,DC)、接近中心性(Closeness Centrality,CC)和介数中心性(Betweenness Centrality,BC)^[12-13]。

1) 度中心性(DC)。

节点的度定义为目标节点与其他节点存在连接或关系的数量，即邻居个数。度中心性认为一个节点的邻居数目越多，影响力就越大。n阶网络中的任一节点v_i的度中心性被定义为：

$DC(i)=\frac{{{k}_{i}}}{n-1}=\sum\limits_{j}{{{a}_{ij}}}/\left( n-1 \right)$

(4)

其中：a_ij是网络G的邻接矩阵A中的i行和第j列的元素；k_i代表节点i的度；n代表网络中节点个数。节点度中心性指标是对节点最直接影响力的描述，拥有简单、直观、计算复杂度低的特点。度中心性越接近 1 表示节点越重要。

2) 接近中心性(CC)。

接近中心性通过计算网络中的任意节点与其他节点的距离的平均值来取得。一个节点与网络中其他节点的平均距离越小，该节点的接近中心性就越大。对有n个节点的连通网络G，G中任意一个节点v_i到网络中其他节点的平均最短距离为d_i：

${{d}_{i}}=\frac{1}{n-1}\sum\limits_{j\ne i}{{{d}_{ij}}}$

(5)

其中:d_ij表示节点i到节点j的距离，d_i的取值越小，意味着节点v_i更能接近网络中的其他节点。节点v_i接近中心性定义如下：

$CC(i)=\frac{1}{{{d}_{i}}}=\left( n-1 \right)/\sum\limits_{j\ne i}{{{d}_{ij}}}$

(6)

接近中心性指标采用了平均值来计算节点的重要性，故能在一定程度上消除对特殊值的干扰。

3) 介数中心性(BC)。

节点的介数用来衡量一个节点位于其他节点最短路径上的次数，即网络中所有其他节点之间的最短路径中经过该节点的次数，代表该节点控制其他节点的能力^[10]。也就是说，如果其他节点的最短路径都有经过该节点，那么该节点具有较高的重要性，节点的介数中心性指标值就越高。对于n阶网络G中的任一节点v_i，其介数中心性指标定义如下：

$BC(i)=\sum\limits_{i\ne s,i\ne t,s\ne t}{\frac{g_{st}^{i}}{{{g}_{st}}}}$

(7)

其中：g_st是从节点v_s到v_t的所有最短路径数目，g_stⁱ是从节点v_s到 v_t最短路径中经过节点v_i的最短路径数。由此可见，当一个节点不在任何一条最短路径上时，节点的介数中心性为0。归一化的介数中心性定义为：

$BC'(i)=\frac{2}{(n-1)(n-2)}\sum\limits_{i\ne s,i\ne t,s\ne t}{\frac{g_{st}^{i}}{{{g}_{st}}}}$

(8)

节点的介数中心性越高，说明该节点越重要，其控制信息流动的能力就越强，其他节点的依赖性就越大^[14-15]。

2.2 考虑节点重要性的CN算法

CN、AA、RA指标均为基于局部结构信息的算法，其中，CN指标均一地为所有邻居节点分配权重，简单地将邻居节点的个数作为链路关联度的衡量标准^[16]，此算法虽然能够简洁地度量两点间存在链路的可能性，但没有充分考虑不同邻居节点在网络中重要性的差距。

图 1为两个节点个数为10的社交网络：图 1(a)中，用户A、B的共同邻居为X和Y；图 1(b)中，用户C、D的共同邻居为P和Q。如果仅考虑节点共同邻居节点的个数，则用户A、B和用户C、D间存在链路的可能性相同。

由图 1可以看出：用户A、B在社交网络中较用户C、D具有更多的共同邻居节点和更强的连通性，即用户A、B较用户C、D重要程更高，因此可以根据共同邻居节点重要性的总和优化用户间存在链路可能性的值。考虑节点重要性的CN算法在共同邻居链路预测指标的基础上分别考虑了网络中节点的度中心性、接近中心性及介数中心性^[17]，改进的算法如下。

1) DCCN算法：如果节点X、Y的共同邻居节点拥有较大的度中心性，那么节点X、Y之间建立链路的可能性更大。DCCN算法相似性指标定义如下：

$S_{xy}^{DCCN}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{DC(z)}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{{{k}_{z}}}{n-1}}$

(9)

其中：x、y表示任意两用户。

2) CCCN算法：如果节点X、Y的共同邻居节点拥有较大的接近中心性，那么节点X、Y之间建立链路的可能性更大。CCCN算法相似性指标定义如下：

$S_{xy}^{CCCN}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{CC(z)}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{n-1}{\sum\limits_{j\ne z}{{{d}_{zj}}}}}$

(10)

3) BCCN算法：如果节点X、Y的共同邻居节点拥有较大的介数中心性，那么节点X、Y之间建立链路的可能性更大。BCCN算法相似性指标定义如下：

$\begin{align} & S_{xy}^{BCCN}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{BC'(Z)}= \\ & \frac{2}{(n-1)(n-2)}\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\sum\limits_{z\ne s,z\ne t,s\ne t}{\frac{g_{st}^{z}}{{{g}_{st}}}}} \\ \end{align}$

(11)

2.3 考虑节点重要性的AA算法

AA指标根据共同邻居节点的度值进行刻画，根据共同邻居节点的度，将节点度对数的倒数，即1/(lg k)作为权重值赋予每个节点。因此，AA指标对于度值相同的节点仍看作是一样的。然而，重要性不同的节点具有不同的中介能力和信息转移能力，AA指标没有考虑节点的重要性。考虑节点重要性的AA算法分别考虑了网络中节点的度中心性、接近中心性及介数中心性，改进的算法如下。

1) DCAA算法: 如果节点X、Y共同关注了度中心性较低的节点，则节点X、Y之间建立链路的可能性更大。DCAA算法相似性指标定义如下：

$S_{xy}^{DCAA}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\operatorname{lb}DC(z)}}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\operatorname{lb}\left( {{k}_{z}}/\left( n-1 \right) \right)}}$

(12)

2) CCAA算法：如果节点X、Y共同关注了接近中心性较低的节点，则节点X、Y之间建立链路的可能性更大。CCAA算法相似性指标定义如下：

$S_{xy}^{CCAA}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\operatorname{lb}CC(z)}}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\operatorname{lb}\left( \left( n-1 \right)/\sum\limits_{j\ne z}{{{d}_{zj}}} \right)}}$

(13)

3) BCAA算法：如果节点X、Y共同关注了介数中心性较低的节点，那么节点X、Y之间建立链路的可能性更大。BCAA算法相似性指标定义如下：

$S_{xy}^{BCAA}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\operatorname{lb}(\frac{2}{(n-1)(n-2)}\sum\limits_{z\ne s,z\ne t,s\ne t}{\frac{g_{st}^{z}}{{{g}_{st}}})}}}$

(14)

2.4 考虑节点重要性的RA算法

RA指标根据共同邻居节点的度值，从资源的角度出发，将共同邻居节点作为传递的媒介，使用共同邻居节点度的倒数为节点赋值。与AA指标相同，RA指标对于度相同的节点也看作是一样的，没有充分利用网络节点的重要性。考虑节点重要性的RA算法分别考虑了网络中节点的度中心性、接近中心性及介数中心性，改进的算法如下。

1) DCRA算法: 如果节点共同关注了度中心性较低的节点，那么共同邻居节点将会因为分到节点X、Y更多的资源而具有更强的信息传递能力，则节点X、Y之间建立链路的可能性就越大。DCRA算法相似性指标定义如下：

$S_{xy}^{DCRA}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{DC(z)}}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{n-1}{{{k}_{z}}}}$

(15)

2) CCRA算法：如果节点共同关注了接近中心性较低的节点，那么共同邻居节点将会因为分到节点X、Y更多的资源而具有更强的信息传递能力，则节点X、Y之间建立链路的可能性就越大。CCRA算法相似性指标定义如下：

$S_{xy}^{CCRA}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{CC(z)}}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\left( \sum\limits_{j\ne z}{{{d}_{zj}}} \right)/\left( n-1 \right)}$

(16)

3) BCRA算法：如果节点共同关注了介数中心性较低的节点，那么共同邻居节点将会因为分到节点X、Y更多的资源而具有更强的信息传递能力，则节点X、Y之间建立链路的可能性就越大。BCRA算法相似性指标定义如下：

$S_{xy}^{BCRA}=\sum\limits_{z\in \Gamma (x)\cap \Gamma (y)}{\frac{1}{\frac{2}{(n-1)(n-2)}\sum\limits_{z\ne s,z\ne t,s\ne t}{\frac{g_{st}^{z}}{{{g}_{st}}}}}}$

(17)

3 实验结果与分析

在链路预测评估阶段，将网络中已存在的链接集合E按照随机划分的方法划分为训练集E^T和测试集E^P两个集合，E=E^T∪E^P，E^T∩E^P=∅。

3.1 评价指标

AUC(Area Under the receiver operation characteristic Curve)是衡量链接预测算法精度最常用的一种指标，该方法从整体上衡量算法的精确度，本文选择AUC指标作为验证实验的评价指标。AUC可解释为从测试集E^P中随机取一条链接的预测概率值比随机地的从不存在的链接集合E^O选择的一条链接的概率值大的可能性^[10]，即每次随机从测试集E^P中选择一条链接(x,y)与随机地从不存在的链接集合E^O中选择的链接(x′,y′)的测试值进行比较，若S_xy＞S_x′y′，则加1分；若S_xy= S_x′y′，则加0.5分；否则加0分。独立随机比较n次，记加1分的次数为n′，加0.5分的次数为n″，因此AUC的计算公式定义为：

$AUC=\frac{n'+0.5n''}{n}$

(18)

由式(18)可见，如果所有分数都是随机产生的，AUC=0.5，因此AUC值大于0.5的程度衡量了算法在多大程度上比随机选择的方法精确。

3.2 实验数据集

为了评价算法的有效性，本文在四个典型的真实网络数据集上开展实验，各数据集特征如下：

1) USAir网络(http://vlado.fmf.uni-lj/si/pub/networks/data/)：该网络是美国航空路线无向加权网络，网络中的节点代表机场，节点间的链接代表机场之间的航线，网络中共包含332个节点，2 126条链路关系。

2) C.elegans网络(http://www.linkprediction.org/index.php/link/resource/data)：该网络为蠕线虫神经无向无权网络，网络中的节点代表神经元，节点之间的链接代表神经元之间的链接关系，网络中包含453个节点，2 298条链路关系。

3) Jazz网络(http://www-personal.umich.edu/~mejn/netdata/)：该网络为爵士音乐人合作网络，网络中的节点代表音乐人，节点之间的链接代表音乐人之间的合作关系，网络中包含192个节点，2 742条链路关系。

4) Email网络(http://konect.uni-koblenz.de/networks/)：该网络为西班牙Universitat Rovira i Virgili(URV)大学邮件通信网络，网络中的节点代表个人，节点之间的链接代表通过邮件的通信关系，网络中包含1 133个节点，5 451条链路关系。

3.3 实验结果

本文以AUC值作为精度衡量指标，分别以基于局部相似性链路预测算法的CN指标、AA指标和RA指标作为基准方法进行对比，将改进的链接预测方法应用于USAir网络、C.elegans网络、Email网络及Jazz网络四4个真实数据集，采用Matlab作为仿真工具，进行100 次独立实进行验证，其结果如图 2所示,图中竖条从左到右依次为CN、DCCN、CCCN、BCCN、RA、DCRA、CCRA、BCRA、AA、DCAA、CCAA、BCAA。

实验过程中将训练集占数据集的比例定义为proportion，根据proportion随机地划分为训练集与测试集。第一次实验proportion的值是0.9，其后每次实验减少0.1，直到0.5。由图 2可以看出，在四个数据集中，随着设定的训练集比例proportion数值的减小，AUC值也随之降低，因此，本文将训练集的比例设为0.9。

将训练集比例为0.9时的几种相似性指标的预测精确度记录在表 1中，表 2记录了改进算法AUC指标相对于对比算法的改进程度。

从表 1可以看出，在四个数据集上，考虑节点重要性的CN算法：DCCN、CCCN、BCCN算法的预测精度总体优于CN算法的预测精度；从表 2可以看出，DCCN、CCCN、BCCN算法在四个数据集上相比CN算法，其预测精度分别提升了0.178 1%，0.500 2%和0.978 2%。考虑节点重要性的AA算法：DCAA、CCAA、BCAA算法的预测精度总体优于AA算法的预测精度，以上3种算法在四个数据集上相比AA算法，其预测精度分别提升了0.014 7%，0.128 9%和0.378 9%。考虑节点重要性的RA算法：DCRA、CCRA、BCRA算法的预测精度总体优于RA算法的预测精度，以上3种算法在四个数据集上相比于RA算法，其预测精确度分别提升了0.033 6%，0.107 6%和0.382 1%。表 1列出了对比算法与改进算法的预测精度的AUC值，可以看出，80.6%的改进算法的预测精度高于对比算法预测精度，同时也出现了个别预测精度低于对比算法预测精度的现象，这与数据集的大小及其准确度有关。

在算法效率方面，设N为节点个数，CN算法首先要查找网络中每一对被预测的节点，然后在两个节点上查找共同邻居节点，因此CN算法的时间复杂度为O(N²)。AA和RA算法只是在共同邻居节点的基础上根据节点的度数进行一些计算^[18]，因此时间复杂度与CN算法相同。考虑节点度中心性的算法，在查找到共同邻居节点后计算每个节点的DC值，计算节点DC的时间复杂度为O(N)，因此，在CN、AA、RA指标的基础上考虑节点度中心性后，改进算法时间复杂度不改变。同理，考虑节点接近中心性、介数中心性的算法，在共同邻居节点的基础上根据节点的CC值、BC值进行计算，计算节点CC值、BC值的计算复杂度分别为O(N²)、O(N³)，因此，考虑节点接近中心性、介数中心性的算法的时间复杂度分别为O(N²)、O(N³)，与共同邻居、AA、RA算法相比，考虑节点介数中心性算法的时间复杂度有所提升，考虑节点度中心性、接近中心性算法的时间复杂度不变。上述实验结果表明，节点重要性在链路预测精确度方面起到了积极的作用，链路预测算法在AUC评价指标下较原始链路预测算法在预测精度上有了一定程度的提升。

4 结语

将复杂网络节点中心性信息应用到了链路预测问题中，本文提出了考虑节点重要性的CN、AA、RA算法，并将改进的算法在真实数据集上与经典的链路预测指标进行比较，结果表明改进的算法能够提升链路预测精度。在算法效率方面，融合节点重要性后的部分算法的时间复杂度有所增加。在接下来的研究中，将对以上算法的效率进行改进，并对节点影响力进行进一步研究。