李治成，吉立新，刘树新，李 星，李劲松

(中国人民解放军战略支援部队信息工程大学 郑州 450001)

随着网络科学的发展，复杂网络成为了重要的研究内容[1-5]。生活中的很多复杂系统都可以抽象为网络来表示，不同类型的网络如交通网络、引文网络、蛋白质作用关系网络、社交网络等均是复杂网络的研究对象。而链路预测作为复杂网络的研究方向，旨在利用已有的网络结构发现网络中缺失的连边、错误的连边和未来可能产生的连边[6-8]。链路预测应用于诸多领域，如在社交网络中用于好友推荐[9]，生物网络中用于发现未知的生物结构[10]，以及引文网络中发现科学家之间的合作关系[11]等。

当前，链路预测的研究已经取得较显著的成果。基于拓扑结构的链路预测方法因简单、高效而备受关注[12-14]，根据拓扑结构信息可将链路预测方法分为基于局部结构、基于半局部结构和基于全局结构3 种方法[15]。基于局部结构信息的预测方法假设如果节点越相似，产生连接的可能性越大，其中以共同邻居结构为出发点已有较多的研究方法，AA 指标对共同邻居的大度节点进行惩罚，CAR 方法考虑共同邻居节点之间相互交互[15]。文献[16]对资源分配指标RA 进行了改进，提出扩展的资源分配指标。全局信息考虑网络的全局结构，例如考虑全局路径的Katz 方法[17]，基于随机游走的节点偏好性游走指标(degree-biased random walk, DRW)[18]和有重启的随机游走指标(random walk with restart,RWR)[19]等，全局方法预测结果优于局部指标，但因其时间复杂度高不适用于大型网络。文献[20]提出的局部路径方法(local path, LP)在共同邻居的基础上考虑了三阶邻居所起的作用，在大部分网络中预测结果与Katz 方法相近。目前已有大量的链路预测方法，但现存的方法忽略了预测节点对之间的连边长度和连边上不同节点的影响力对相似性的贡献。节点对之间的相似性不仅与路径的长度有关，还与路径上的节点的影响力有关，节点影响力挖掘方法不同，连边传递的有效性也将不同。此外，还需探讨不同挖掘方法下节点影响力对相似性的贡献。

因此，本文分析了网络在不同路径长度和节点影响力下对节点相似性的贡献，提出基于拓扑有效连通路径的链路预测方法。而节点在网络中影响力的挖掘方法较多，为减少时间复杂度，本文主要从节点的出入度、半局部中心性和H-指数3 种中心性衡量指标来量化节点的局部影响力，并使用相应的方法来量化连边的传递能力。通过在多种实际网络中进行实验，验证了节点之间的相似性不仅与路径长度有关，还与节点影响力有关。

1 相关工作介绍

11) propflow[25]：该方法是一种有监督的随机游走方法，计算从源节点x开始以一定步长或更少的步长到达节点y的概率。

2 基于拓扑有效连通路径的有向网络链路预测方法

2.1 拓扑连通度的分析量化

传统的链路预测方法研究中，认为端点的影响力有助于连边的形成，且影响力大的节点之间更倾向于连接[26]。而网络中端点间实际通过路径建立联系，并通过建立的关系来传递影响力，从而发生相似性传递。而网络中相似节点对之间往往存在多条路径，路径结构的差异将影响相似性的传递。图1给出了拓扑结构与信息传输路径的示意图。信息从多条路径传递到y，结构的差异将影响路径连通度大小。对于相同长度路径，x→a→y和x→b→y，传递到y的信息与中继节点有关，中继节点的出入度不同，连边的连通度也不同。对于不同长度的路径x→a→y和x→b→e→f→y，分别通过2 跳和4 跳到达，节点信息在传递过程中往往随着长度的增加而减少，不如短路径传递的信息有效。而最终y获取到的有效信息是多条路径的叠加。因此，需要从拓扑结构对信息传输过程影响的角度，分析刻画 拓扑路径的连通度。

图1 网络中信息传输过程分析示意图

图2 不同路径长度下相似性传递过程分析

其次，节点间路径的长短虽然重要，但路径中节点的差异性也决定了路径能传递的信息多少，还需分析路径连通度与中继节点的关系。节点影响力描述了节点在网络中的重要程度，且节点影响力能够决定节点在路径中捕获资源和信息的能力[27]，路径中传递资源往往偏向于影响力大的节点。文献[28]证实了在电力网络中，节点的度与承受的电力负荷成正比，现实生活中“富者愈富”的现象也说明影响力大的节点在网络中占有优势[29]。在有向网络中，相连节点之间的路径连通度与中继节点的出入边的影响力有关。在图3 所示的网络结构中，如果仅以节点出入度作为判断节点影响力的大小，则节点z2具有较高影响力，节点x传递资源时偏向于z2，但由于影响力大的中继节点能传递的连边较多，最终能传递到相邻节点y的资源较小，即中继节点影响力低且路径短的预测节点之间的连边连通度较大。

图3 中继节点与路径连通度的关系分析

可以看出，任意一条路径信息传输的有效性可以量化为路径长度和路径中节点影响力对信息传递能力的影响。然而，有向网络中影响力的挖掘方法较多，不同网络中，中心性衡量存在差异，因此，本文还分析了在不同节点度中心性指标下对路径连通度的贡献。目前已有的中心性方法并不能完全挖掘节点在网络中的影响力，为减少时间复杂度，主要利用局部结构方法定义节点的重要程度，选取基于节点的度中心性、节点的半局部中心性和H-指数3 种中心性指标量化节点的入边和出边影响力，并给出了相应方法的路径连通度的表达式，具体方法定义如下。

2.2 预测方法提出

为了从路径有效性对信息传输影响的角度刻画任意两点间的相似性，将基于路径传输影响因素分析节点间信息传输能力。“三度影响力”认为人与人之间相互影响，且影响力的传递是在三度以内，超出三度节点，影响力将会逐渐消失[31]，当源节点和目标节点之间经过三跳或者更多跳路径时，相似性传递也将随着路径长度的增加而无法有效的传递到目标节点。“六度分割理论”认为世界上任何两个陌生人之间的距离不超过6 个人，也就是说，每个人最多通过6 个人就可以认识世界上任何一个陌生人[32]。兼顾“三度影响力”和“六度分割理论”，将两度节点和六度节点之间的路径称为拓扑有效连通路径，并从信息传递的角度定义了相关方法。

3 衡量指标和数据集介绍

3.1 衡量指标

对于给定的链路预测方法，通过计算节点对之间的相似性得分来衡量未连接的节点对之间的相似性，本文通过AUC(area under receiver operating characteristic curve)、precision、排序分(ranking score,RS)来衡量预测精确度，将有向网络G(V,E)的连边E分为训练集ET和测试集EP，满足EP∪ET=E，且EP∩ET=φ。

AUC 为随机从测试集EP中随机选取一条边的分数值比未连接边的分数值大的概率[33]。如果选取的测试边的分数值有n′条大于未连接边的分数值，则加n′分，若分数值相等的有n′′条 ，则加 0.5n′′分，AUC 的计算公式表达为：

式中：λ为预测的响应值； α0 为常系数；αi为线性系数；αii为二次方系数；αij为相互作用系数；χi，χj 为实验因素。

1) FWEW[35]：生活在Everglasdes Gramininoids的湿季生物构成的食物链网络，节点表示物种，连边表示物种之间的捕食关系；

2) High-school (HIG)[36]：描述美国伊利诺伊州某高中男生间建立的朋友关系网络。数据集中每个用户被问谁是朋友，A→B表示用户A认为B是A的朋友；

3.2 网络数据介绍

本文选取了不同类型的有向网络用于预测验证，数据集介绍如下：

3) Residence_hall (RES)[36]：澳大利亚国立大学朋友关系网络，与HIG 类似；

4) CollegeMessage (CM)[36]：一个由加州大学欧文分校构成的邮件网络构成的社交网络；

5) Political_blogs (PB)[37]：美国政治博客网络，节点表示网页，连边表示网页之间的连边关系；

6) Scimet[38]：引用“科学计量学”的论文引文网络，节点表示论文，连边表示论文引用关系；

7) SmaGri2[38]：一个由Small & Griffith and Descendants 相关的论文引用网络，节点表示论文，连边表示引用关系；

8) Air traffic control (AIR)[36]：由美国国家联邦航空局飞行数据中心构建的航空网络，节点表示机场或者服务中心，连边表示飞行路线。

表1 使用网络数据参数说明

上述的网络具体参数特征如表1 所示，包括网络类型Type、节点数|V|、 边数|E|、最大入度MID、最大出度MOD、平均度 〈k〉、 平均距离 〈d〉、聚类系数C。实验中，设置训练集和测试集所占的比例为9:1，每个实验结果均为50 次实验结果的均值。

4 实验分析

为了验证路径的有效传播在链路预测方法中的作用，在8 个真实网络上进行实验分析。实验首先分析路径中节点影响力与拓扑路径有效连通的关系，并对不同路径长度下的有效连通度进行对比。

4.1 中心度方法之间对比分析

图4 为EPD、EPLC、EPH 在8 个真实网络中的AUC 性能曲线，本文取节点之间最长的路径为10，以验证节点之间的有效路径连通度是否在6 步以内。首先对比不同的网络中各个节点中心度量化方法之间的差异度，根据曲线变化可以看出EPLC的预测结果波动性较大，在有的网络中表现较好，有的网络中表现较差，在EPD 和EPH 表现相对较好，且EPH 优于EPD。因此，相比于节点度中心、节点的半局部中心的中心衡量指标，H-指数更适用于量化节点的影响力。信息在传递过程中，并不是所有量化方法都能准确衡量出节点的影响力，H-指数考虑邻居节点个数的同时，还考虑了邻居节点的质量，能有效计算连边传递的相似性，因此该方法表现较好且稳定。EPD 仅根据节点的出入度量化节点的影响力，并不能充分挖掘节点的重要程度。EPLC 在EPD 的基础上考虑了局部邻居节点的数目，近似地计算了节点在全局网络中的相对作用大小，但应用于链路预测的时候，预测精度较低，且稳定性较差。

图4 不同中心度方法之间AUC 对比分析

不同游走步数下，AUC 表现各不相同，说明不同路径长度下对节点的相似性贡献不同。当游走长度为2 时，计算的是粒子从源节点出发两步到达目标节点的相似度，从预测结果中可以看出，大部分网络中的AUC 预测精度并不是很高。在CM 网络中，由于网络中节点具有较高的平均度，和节点之间平均距离较大，当网络中具有较多大度节点时并不能促进相似节点产生，当路径长度为2～4 时，EPD 方法没有准确对连边的连通度进行衡量，在计算节点之间的相似性得分的时候，增加了干扰信息，造成EPD 方法在网络中随着路径的增长预测精度下降，但当路径长度大于4 时候，路径的连通度变得微乎其微，因此，路径长度为4 之后预测精度逐渐趋于稳定。而在Air 航空网络中平均距离较大，当一个机场有多条路径可达一个机场时，说明该机场可能是一个大型国际机场，目标节点越重要，与其产生连接的可能性越大，所以AUC 结果会增加。可以看出，在所有网络中，3 种节点量化节点重要性的方法均随着路径长度的增加而改变，在大部分网络中，当路径长度达到6 时基本趋于稳定。因此，节点之间的拓扑路径有效连通路径在2 度和6 度节点之间。

4.2 不同预测方法对比分析

基于不同中心度量化节点影响力的实验结果可以看出，当游走的步长为6 时AUC 值趋于稳定，为了便于与其他链路预测方法进行对比分析，同时兼顾六度分割理论，EPD、EPLC、EPH 游走的步长l值均为6，使用AUC、precision、排序分3 种衡量指标进行评价。

4.2.1 AUC 实验对比分析

表2 给出了AUC 的对比分析，Katz.01 表示调节参数α 的取值为0.01，LRW_3 中3 表示游走的步数为3。通过对比分析可以得出，基于H-指数量化的方法表现较好，在Scimet、SmaGri2、AIR 网络中EPD、EPLC 均比EPH 差，说明在一些网络中影响力的有效传播与连边的量化方式相关，并不是所有的量化方法都能有效量化连边影响力。4 种局部指标DCN、DAA、DRA、DPA 考虑的网络结构简单，在各种类型的网络中表现差异较大。而LP在共同邻居(DCN)的基础上考虑了三阶路径所起的作用，有较大的改进。全局方法Katz 因考虑全局网络的拓扑结构信息均表现最好。而随机游走方法局部随机游走和有叠加效应的随机游走方法在不同的网络中表现差距较大，在规模相对较大的网络Scimet 中表现较好，小规模网络中预测的AUC 值几乎接近于0，而ACT 方法在所有预测方法中是最差的，说明相似性在传递过程中并不一定能传递到目标节点，且该方法时间复杂度较高。Bifan 在食物链方法中预测精度较高，超过了考虑全局信息的Katz 方法，而此网络结构并不适用于其他类型的网络，说明食物链网络在演化过程中产生较多的Bifan 结构，能有效提升食物链网络中的预测精度。

表2 AUC 结果分析

纵向对比分析发现在航空网络AIR 数据集上，Katz.01 时预测精度较高，而LP 方法预测结果与其相差接近0.2，说明在该网络中，路径越长，航班之间直飞的可能性越大。而改进后的EPD、EPH 预测结果与Katz.01 相差不大，考虑路径的异构性确实能促进节点对之间的相似。在DCN 基础上改进的DAA 指标，在RES 和AIR 网络中预测精度提高较大，大度节点在这两个网络中抑制节点对之间的相似连接，而在其余网络中预测结果均无改进。对于大部分网络，PA 方法结果具有较高的预测精度，很好的解释了“富者愈富”的现象，节点更倾向于和大度节点相连接。而本文方法针对不同的网络结构，路径的有效连通度并不相同，在各种连边量化的方法中EPH 方法具有较高的预测精度，所有网络均具有较好的表现，能较好地量化节点对之间的连边的连通度，也进一步说明有效的邻居节点确实能提高节点之间的相似性。

4.2.2 precision 结果分析

表3 给出了precision 的结果，可以看出，预测结果与AUC 结果差不多，食物链网络中依旧bifan 结构最高，4 种局部结构中，PA 在食物链网络中表现较好，LP 和Katz 方法的预测精度较为接近；3 种随机游走方法ACT、LRW_3、SRW_3预测准确度较低，但在社交网络中表现较好，而在大型网络中预测精度几乎为0；在小规模网络的社交网络RES、HIG 预测结果较好，可能随机游走的指标在大规模网络中更适合AUC。在CM 网络中，相比Katz0.01 预测精度提升了1%，且时间复杂度远小于Katz。在CN 基础上改进的AA、RA 指标，在引文网络Scimet、Smagri2 和航空网络中精度较差，引文网络和航空网络节点的度与重要程度成正比，重要节点并不会抑制网络连边的L 形成。考虑了有效路径连通度之后，EPH 的precision结果在除了生物网络之外的所有网络中表现均较好，说明节点的影响力不仅与节点自身有关，还与邻居节点的重要性相关，在量化邻居节点重要性的基础上，EPH 方法能有效计算路径的连通度。

表3 precision 结果分析

4.2.3 排序分结果分析

表4 为排序分的实验结果，与AUC、precison预测结果不同，该衡量指标的预测结果越小，精度越高，即预测结果越排在前，证明方法的可行性越好。从表4 的预测结果中可以看出，EPH 方法表现的结果依旧较好，局部指标CN、AA、RA 预测结果较为接近，因为这3 种方法网络结构相同。在不同的度中心衡量方法中，EPLC 的预测结果最差，说明该方法并不能有效量化路径连通度，考虑的网络结构不适合应用于该链路预测中。而随机游走方法LRW_3、SRW_3 偏差较大，在SmaGri2、AIR 网络，排序结果均错误，可能与取的游走方向和步数有关。相比于局部方法，PA 排序结果较好，对大部分网络能准确地将连边出现的概率进行排序。在所改进的方法中，EPLC 在EPD 的基础上考虑了节点在局部结构中的相对重要性，排序结果较差。综合对比，在局部网络结构中，使用H-指数量化路径中节点影响力的方法最为有效。

表4 排序分结果分析

5 结 束 语

近年来，基于网络拓扑结构相似性的链路预测方法备受学者关注，已提出了较多方法。大部分方法将节点的度构建为节点的影响力，影响力越大，与之产生连接的可能性越大，但连边的建立本质上与路径的有效性连通有关，路径上中继节点的影响力将影响连边的建立。本文将节点影响力应用于有向网络链路预测中，通过多种方法量化路径的连通能力。在多个实际网络中进行实验，结果表明，对于相同的游走步数，用基于H-指数更适合表示节点的影响力，能有效量化路径的有效连通度，而当有多条路径可达目标节点时，3 阶以上路径对节点之间的相似性传递贡献较小。本文所提出的方法说明路径的有效连通度不仅与路径长度有关，还与路径上的节点影响力有关。此外，该预测方法能应用于大型网络，能有效地揭示连边的形成机理和网络的演化机制。