基于资源传输节点拓扑紧密性的链路预测方法

李英乐，何赞园，王 凯，许明艳

（中国人民解放军战略支援部队信息工程大学信息技术研究所，郑州 450002）

0 概述

链路预测是网络科学的一个重要研究方向，其目的是通过分析网络当前的拓扑结构和属性信息，来预测网络中不存在链接的节点之间出现链接的可能性［1］，对研究复杂网络的演进机制具有十分重要的意义［2］，在生物网络［3］和社交网络［4］等现实网络实践中也具有很好的应用价值。

近年来，越来越多的学者对链路预测的方法进行了深入研究，并在多个方面都取得了一系列成果，特别是在基于网络拓扑结构的链路预测方法上的进展较大。基于网络拓扑结构的链路预测方法根据节点之间的链接关系计算节点之间的相似性，得到节点之间出现链接的可能性。节点相似性指标大体上包括全局相似性指标和局部相似性指标两大类。局部相似性指标主要根据节点的共同邻居来计算相似性，包括CN指标［5］、Salton指标［6］、AA指标［7］和RA指标［8］等。全局性指标是从整个网络拓扑结构着眼计算节点相似性，主要有基于随机游走的Cos+指标［9］、ACT 指标［10］、RWR 指标［11］和基于路径的LP 指标［12］、LHZ-II 指标［13］、Katz 指标［14］。局部性指标仅考虑邻居节点，其计算复杂度和精度较低；全局性相似指标考虑整个网络结构，预测精度较高，但计算复杂度也较高，难以用于大规模网络中。需要注意的是，由于RA 指标在局部相似性指标中取得相当高的预测精度，因此受到了广泛的关注。但RA 指标仅从简单的资源传输过程描述出发对其进行量化，忽略了传输节点周围拓扑信息对资源传输节点传输概率的影响［15-16］。在现实网络中，传输节点周围拓扑的聚集程度与资源传输的效果具有相关性［17-18］，传输节点越聚集，资源的传输效果越好。

针对上述问题，本文提出一种基于资源传输节点拓扑紧密性的链路预测方法。研究资源传输过程中多跳节点资源的传输情况，确定重要传输节点，对传输节点聚类系数进行分析，基于聚类系数改进拓扑紧密性量化方法，并利用传输节点紧密性对共同邻居传输资源进行参数调整，进而重新刻画节点间相似性，给出资源传输节点拓扑紧密性指标。此外，在Precision 衡量标准下，利用多个实际网络对所提指标进行有效性分析，以验证该方法的预测效果。

1 相关工作

当前基于相似性的链路预测方法有很多，研究人员基于不同原理提出多种预测指标，本节对几种知名预测指标及网络资源传输相关指标简要介绍如下：

1）CN 指标［5］。LORRAIN 等人直接利用共同邻居的数目衡量节点x和y的相似度，该方法复杂度低，在集聚性较高的网络中表现较好，但在稀疏网络中表现较差。Γ（x）为节点邻居的集合，表示为：

2）AA 指标［7］。根据节点对共同邻居的重要程度不同，ADAMIC 等人利用高度惩罚机制对共同邻居加权，权值为节点度对数的倒数，表示为：

3）CAR 指标［17］。在CN 的基础上考虑了共同邻居之间存在链接的情形，该方法在集聚性较高的网络中表现较好，CAR 指标可表示为：

4）LP 指标［12］。吕林媛等人在共同邻居（即2 阶路径）基础上，综合考虑了3 阶路径对节点相似性的影响，LP 指标可表示为：

其中，S为相似度矩阵，A是邻接矩阵，(An)xy表示节点x和y之间长度为n的路径数目，α为调节参数。该方法是预测效果与计算复杂度的合理折中，效果好于CN 指标。

5）Katz 指标［14］。KATZ 等人从网络全局角度充分考虑节点间所有的路径数目量化节点间的相似度，具有很好的预测精度，但复杂度较高，表示为：

6）ACT 指标［10］。KLEIN 等人将一个随机游走的粒子从一个节点x游走至另一个节点y所需要走的平均步数，作为两节点产生连接的可能性，提出平均通勤时间指标，表示为：

7）Cos+指标［9］。FOUSS 等人在基于随机游走的基础上，提出余弦相似性指标，在矩阵L+计算2 个向量之间的相似性：

8）RA 指标［8］。周涛等人基于资源传输原理，认为共同邻居传递资源的多少和其路径上共同邻居的节点度成反比，RA 指标具体表示为：

9）ERA 指标［19］。刘树新等人在RA 指标的基础上，详细分析节点间多跳的局部路径传输的资源，提出了扩展的资源分配ERA 指标，具体表示为：

其中，参数σ表示多跳路径资源对相似性的贡献，当σ=0 时，该指标退化为RA 指标。

10）EP 指标［20］。王凯等人考虑资源传输路径有效程度对传输性能的影响，分析了潜在的资源传输路径有效性并对双向资源传输量进行刻画，EP 指标具体表示为：

其中，Wz表示节点z所有连边的路径有效量化值之和，wlij表示节点i、j之间的有效资源传输量。

11）QN 指标［21］。王凯等人在研究路径传输有效性基础上，分析传输路径的资源承载能力，提出资源承载度及相应的预测方案，具体表示为：

其中，Qλ（i，j）表示节点i、j之间量化的资源承载能力。

综上可见，资源传输原理是节点相似性刻画的重要参考，其不仅应从传输过程分析，而且在传输路径、局域拓扑等方面有更多待研究之处。

2 资源传输节点拓扑紧密性链路预测方法

2.1 资源传输节点拓扑紧密性分析与量化

研究发现，网络演进时连边的变化会影响到网络中的信息的传播［23］，同时网络中信息的传播也会影响到连边的变化［24］，此两者具有相关性［25］。任意2 个未连接点之间的资源传输需要经过多跳节点进行，共同邻居节点作为最短跳的资源传播节点，是资源传输过程的核心。图1 所示为不同类型资源传输节点在资源传输过程中的作用（图中仅以节点x传输一定的资源至节点y的过程为例）。

图1 不同类型资源传输节点在资源传输中的作用Fig.1 Effect of different types of resource transmission nodes in resource transmission

从图1 可以看出，在多跳路径传输中，随着路径上节点数目的增加，资源传输过程趋于复杂，资源量的传输“衰落”现象也越来越明显，导致节点x到节点y的资源传输量也会以一定的比例逐步减少。而仅经过两跳传输的共同邻居节点z，其传输资源的效率和确定性明显高于其他传输节点。因此，在资源传输过程中，共同邻居是资源传输的核心节点，发挥着关键作用。在资源传输的后续分析中，将重点针对核心资源传输节点共同邻居。

资源传输指标（RA）是直接利用核心传输节点共同邻居进行资源传输过程分析，然后对任意2 个未连接节点进行相似性刻画。该方法效果较好，但现实网络中核心传输节点共同邻居周围拓扑结构较为复杂，仅利用节点度对其进行资源传输量的刻画难以更加有效地量化传输过程。共同邻居节点周围拓扑结构的紧密性会对资源传输有着较大影响，如图2 所示。对于节点x和节点y的共同邻居节点zn，其周围存在邻居节点｛v1，v2，v3，v4，v5｝和许多连边构成了相对稠密的局部结构，这对于资源传播具有很大的促进作用。为量化局部结构对节点间资源传输的作用，需要分析刻画传输节点周围拓扑结构的资源传播紧密性。

图2 资源传输节点周围拓扑结构示意图Fig.2 Schematic diagram of topology around resource transmission nodes

网络节点的聚类系数是刻画网络局部拓扑结构紧密性的重要参数［26］。对于网络中任意一个节点i，有ki个邻居节点。若所有邻居节点间两两互联，则所有连边数目表示为ki（ki-1）/2，此时网络邻居节点的紧密性最大。在正常情形下，节点i的聚类系数可以表示为：

其中，Ei表示节点i的所有邻居节点间实际存在连边的数目。节点聚类系数会随着邻居节点连边数目不断增加，如图3 所示。图3（a）中邻居节点之间无任何连接，此时节点i的拓扑集聚性最低，Ci=0；图3（b）中邻居节点之间存在一条连接，此时聚类系数Ci=2×1/（4×3）=1/6；图3（c）中邻居节点之间的连接大幅度增加，此时拓扑间关系更加紧密，聚类系数为Ci=2×3/（4×3）=1/2；图3（d）中所有邻居节点都存在连接，局部拓扑集聚性达到最大，此时聚类系数为Ci=1。可以看出，网络节点聚类系数一定程度上表征了独立节点周围拓扑紧密性。然而，不同于独立节点仅考虑局部拓扑结构，对于一对未连接节点的核心资源传输节点，其资源传输紧密性的刻画需要考虑资源传输节点周围拓扑结构对资源传输过程的影响，而且直接使用聚类系数难以表征不同邻居节点对传输资源紧密性的作用。

图3 独立节点不同拓扑结构下的紧密性分析Fig.3 Tightness analysis of independent nodes under different topology

为分析在不同拓扑结构下资源传输节点周围局部拓扑对节点间资源传输的影响，进而刻画资源传输节点拓扑结构的紧密性，本文引入多个局部拓扑结构进行对比分析，如图4 中的4 个网络结构中均存在一对未连接的节点x和y，以及待分析的资源传输节点zi。下文将对比分析zi周围不同拓扑结构对于节点x和y资源传输过程的影响，即对资源传输节点紧密性的影响。对于图4（a）和图4（b），传输节点zi具有相同数目的邻居节点，但后者邻居节点之间连边数目明显高于前者，因此从节点x和y资源传输的角度，后者传输节点zi的资源传输紧密性明显高于前者；对于图4（b）和图4（c），传输节点zi既具有相同数目的邻居节点，也具有相同数目的邻居连边，不同的是前者是｛v1，v3｝和｛v2，v3｝，而后者是｛v1，x｝和｛v1，z1｝。虽然从聚类系数角度，图4（b）和图4（c）的集聚性相同，但是很明显后者zi的邻居节点v1的连边为资源传输提供了更大的可能（对比来看，后者邻居节点v1为节点x和y提供了更少跳数的稠密拓扑传输结构），因此，从节点x和y资源传输的角度，图4（c）传输节点zi的资源传输紧密性高于图4（b）；对于图4（c）和图4（d），传输节点zi具有相同数目的邻居节点，但后者具有更多邻居连边和有效邻居节点v4。因此，从节点x和y资源传输的角度，图4（d）传输节点zi的资源传输紧密性高于图4（c）。

图4 不同资源传输节点周围拓扑结构Fig.4 Topology around different resource transmission nodes

通过上述分析可以看出，传输节点的邻居在资源传输紧密性的刻画上发挥着不同的作用。对于资源传输始发、终结节点x和y，若传输节点zi的邻居与其存在连接，则其对于资源传输的贡献较大，如图5中的v1、v2、v3。与之相反，若传输节点zi的邻居与始发、终结节点并无连接，其对于资源传输的贡献非常小，考虑到路径上资源的“衰落”，可以忽略其对于节点资源传输紧密性的影响，如图5 中的v4、v5。因此，为从资源传输的角度更好地刻画传输节点的紧密性，对传输节点的邻居中对紧密性贡献较大的邻居进行定义。

图5 资源传输节点周围拓扑结构示意图Fig.5 Schematic diagram of topology around resource transmission nodes

定义1（资源传输节点的紧密邻居） 网络中任意一对未连接的资源传输始发、终结节点x和y，共同邻居节点z是其核心传输节点。对于传输节点z的所有邻居节点，其紧密邻居包含始发、终结节点x和y，主要囊括与其存在直接连边的邻居节点。传输节点z的紧密邻居集合可表示为：

其中，Γ（z）为传输节点z的所有邻居节点集合，Γ'（x）、Γ'（y）为包括自身节点x、y及其所有邻居节点的集合。图6 所示为资源传输节点的紧密邻居，对于资源传输始发、终结节点x和y，其资源传输节点z的紧密邻居为：

图6 资源传输节点的紧密邻居示意图Fig.6 Schematic diagram of tight neighbors of resource transmission nodes

对于同样的网络结构，若其资源传输的始发、终结节点发生了变化，其紧密邻居也会发生变化。若图6 中资源传输始发、终结节点是v4和v5，其资源传输节点z的紧密邻居为：

在对资源传输节点z的紧密邻居进行定义后，便可以对其紧密性进行量化，本文基于聚类系数，从紧密邻居的角度定义传输节点的紧密性。

定义2（资源传输节点拓扑紧密性） 网络中任意一对未连接的资源传输始发、终结节点x和y，共同邻居节点z是其核心传输节点。对于传输节点z，其资源传输拓扑紧密性量化为紧密邻居间实际连边数目占比紧密邻居最大连边数目，即：

具体表示为：

2.2 资源传输节点拓扑紧密性指标

对资源传输节点拓扑紧密性进行量化后，便可以基于拓扑紧密性分析节点之间的相似性，进而预测任意节点之间存在的可能性。在一般情况下，与资源分配指标RA 相似，可以直接利用传输节点拓扑紧密性对资源传播进行加成：

式（18）直接利用存在相似度量化上的问题，若资源传输节点z的紧密邻居之间并无连接，其相似度则量化为0。该量化方法会一定程度上忽视共同邻居节点本身的资源传输能力。因此，在刻画资源传输节点拓扑紧密性指标时，需要同时考虑两个方面：一方面考虑关键资源传输节点本身的资源传输能力；另一方面需要考虑该资源传输节点拓扑紧密性对资源传输能力的影响。如图7 所示，若资源从节点x传输指定资源到端节点y，则该传输过程的资源量与共同邻居节点本身资源传输和其拓扑紧密性对资源传输影响相关。

图7 资源传输节点拓扑紧密性指标示意图Fig.7 Schematic diagram of tightness index of resource transmission node topology

定义3（资源传输节点拓扑紧密性指标） 对于一个无向网络G（V，E），其中网络中任意存在两个节点x和y，从网络中关键资源传输节点的局部拓扑出发，即共同邻居节点拓扑紧密性的角度，节点x和y之间的相似性可量化为所有共同邻居节点本身传递资源量与其拓扑紧密性加成资源量之和，具体表示为：

其中，β为调节参数，用于调整不同网络中资源传输节点拓扑紧密性对资源传输量的影响程度，1/kz表示共同邻居节点本身传递资源量，而表示拓扑紧密性加成资源量。当β=0 时，资源传输节点拓扑紧密性指标（TT 指标）与资源分配指标RA 相同。而对于图7 所示的拓扑结构中

3 网络数据集

为了验证基于传输节点拓扑紧密性的链路预测方法的有效性，本文选取了多个不同类型的实际网络进行实验，对具体网络数据分别介绍如下：

1）爵士音乐家合作网络Jazz［27］：一种表示爵士音乐家之间的合作关系的网络，其中音乐家用网络节点表示，音乐家之间的合作关系用网络中的连边表示。

2）食物链网络FWEW［28］：一种生活在Everglades Graminoids 湿季的69 种生物组成的网络，不同生物用网络节点表示，生物之间的捕食关系用网络的边表示。

3）美国航空线路网络USAir［29］：网络的节点代表不同的机场，网络中的连边代表机场之间有直达航线。

4）线虫神经网络CE［30］：线虫神经元用网络节点表示，线虫的神经元突触或其之间的连接用网络的连边表示。

5）邮箱通信网络Email（EM）［31］：一种规模为中型的工厂工人之间的邮箱通信网络，工人的邮箱地址用网络节点表示，不同工人之间的邮件往来用网络连边表示。

6）线虫新陈代谢网络Metabolic［32］：秀丽隐杆线虫的新陈代谢网络，节点表示代谢物，而连边表示它们之间的相互作用关系。

7）Infectious（Infect）［33］：2009 年，在柏林科学美术馆的表演“Infectious：Stay away”中人们面对面行为的网络，参与的人员用网络节点表示，人与人之间的沟通用连边表示。

8）mac-animal［34］：一种62 个成年雌性日本猕猴的支配行为有向网络，节点表示猕猴，网络连边表示左侧节点对右侧节点的支配行为。

上述网络数据集的具体网络统计特征参数如表1 所示。表1 主要包含网络节点数目（|V|）、网络中边的数目（|E|）、网络平均聚类系数（C）、网络平均节点度和网络平均最短路径。在后续网络数据实验中，本文设置训练集合ET中连边数目占比为0.9，测试集EP的连边占比为0.1，此次每个数据测试点的结果均为20 次实验的平均值。

表1 实验数据集统计信息Table 1 Statistical information of experimental datasets

4 实验结果与分析

为验证资源传输节点拓扑紧密性指标的有效性，本文在多个不同类型网络中进行实验验证。在实验研究中，由于该指标主要针对Precision 指标，因此重点对Precision 结果进行实验。具体地，首先实验分析了不同网络中调节参数对TT 的Precision 结果的影响，然后与现有指标进行对比，分析TT 的实验效果和有效性，并给出现实网络应用时的合理使用建议值。

4.1 Precision 结果的参数影响分析

资源传输节点拓扑紧密性指标的具体相似性刻画，利用了参数β调节不同网络中资源传输节点拓扑紧密性的影响程度。图8 显示了不同网络中参数β对资源传输节点拓扑紧密性指标预测结果的影响。

图8 TT 指标Precision 结果随参数变化示意图Fig.8 Schematic diagram of TT index Precision results with parameters changes

可以看出，不同网络中参数β对TT 指标的影响较大，在Jazz 和Metabolic 网络中随着β值的增大，在β=0 处迅速增长，说明传输节点拓扑紧密性影响非常明显。当Precision 值达到较高值后，随参数持续稳定，说明此时传输节点拓扑紧密性强度的增大对节点间相似性的贡献不再明显增大；在FWEW 和macanimal 网络中，参数β对TT 指标的影响较为复杂，随着β值的增大，Precision 值逐渐下降到极点后逐步上升，说明较低的拓扑紧密性强度对于相似性刻画促进作用逐渐下降，而到达较大强度后会逐渐增强其影响力；USAir 和CE 网络相似，在参数β较小时其Precision 值上升至最大值，然后随着参数β的增大呈现轻微下降趋势；与其他网络不同，在Email 网络中，在参数β接近0 时Precision 值呈现急剧上升趋势，表明较低的传输节点拓扑紧密性强度便可以产生较好的效果。同样，当达到最高点后，随着参数β的增大，呈现快速下降趋势，也说明了此时传输节点拓扑紧密性强度对其影响正在逐渐降低；在Infectious 网络中，当参数β较小时Precision 呈现持续上升态势，到达最大值顶点后逐步下降，而后又呈现上升，说明传输节点拓扑紧密性强度在不同阶段对其影响各异。总之，在多数网络中，当参数β较小时，传输节点拓扑紧密性强度对Precision 结果促进作用较强，部分网络中提升幅度较大且相对稳定，说明传输节点拓扑紧密性对相似度刻画具有一定的有效性。

4.2 Precision 结果对比分析

为进一步研究分析资源传输节点拓扑紧密性指标的有效性和特点，本文选取了8 个相似性指标进行对比分析。对比指标方法主要包括局部相似性和全局相似性指标，其中局部相似性指标包括共同邻居指标CN、资源分配指标RA、AA 指标和考虑共同邻居相互关系的CAR 指标，全局相似性指标包括全路径指标Katz、平均通勤时间ACT 和余弦相似性指标Cos+，还包括介于局部和全局之间的局部路径指标LP。

表2 为多个不同类型网络中TT 指标与现有指标的Precision 结果对比情况。其中，（a）可调参数α=0.001，（b）可调参数α=0.01。

表2 Precision 结果对比分析Table 2 Comparative analysis of Precision results

从表2 可以看出，相比其他的相似性指标，总体上TT 指标具有较高的预测精度，8 个网络中有7 个网络TT 指标的Precision 值最高（见粗体数字），只有在FWEW 网络中排名第三，这在一定程度上说明了资源节点拓扑紧密性对节点间相似性刻画的有效性。作为最简单的共同邻居指标CN，由于仅考虑了共同邻居的数目，其Precision 预测结果具有一定的效果，但相比其他相似性方法，大多数网络中CN 的预测结果略低（除在Email、Metabolic 和Infectious 网络中，CN 的Precision 高于CAR、LP、Katz）。资源分配指标RA 通过利用资源分配过程计算节点间传输的资源量进行量化节点间相似性，其复杂度较低但效果明显好于一般局部相似性指标，尤其是在FWEW、USAir、CE、Metabolic、Infectious 和macanimal 等网络中，部分甚至高于全局相似性指标LP或Katz。与RA 指标类似，AA 指标利用共同邻居的节点度对共同邻居进行加权，其效果在多数网络中好于共同邻居指标，部分网络如Jazz、USAir、CE、Email、Metabolic 和Infectious 中其结果好于全局指标。CAR 指标考虑了共同邻居之间存在的部分连接对相似性的影响，其效果明显好于共同邻居指标，但在多数网络中比RA 和AA 效果略差。LP 和Katz 是基于长路径的相似性指标，在多数网络中效果较好且相对稳定，尤其是在FWEW、CE、Email 和macanimal 网络中效果最好。平均通勤时间ACT 指标是基于随机游走的相似性指标，不过在Precision 衡量标准下，多数网络中普遍较低，许多Precision 值甚至接近于0，这可能是与ACT 指标更多地适用于AUC衡量标准，而不适用于Precision 标准。余弦相似性指标Cos+同样是基于随机游走的相似性指标，相比ACT 其效果有了一定的提升，但与其他相似性指标相比，其总体效果较差。ACT 和Cos+的Precision 效果分析结果表明，部分基于随机游走的相似性指标更多地倾向于AUC 衡量标准，难以适应于Precision衡量标准。在考虑了资源传输节点拓扑紧密性后，TT 指标在8 个网络中表现普遍较好。多个网络中如在Jazz、USAir、Email 和Infectious 中，其Precision 的提高幅度较高，明显高于其他局部和全局相似性指标。在mac-animal 中，TT 指标与RA 相似，说明了当前网络中资源传输节点拓扑紧密性的影响较低，其设置参数为0。在现实网络的链路预测应用中，建议参数设置为11.1，各个网络中表现普遍较高。此外，本文所提方法时间复杂度介于共同邻居指标CN 和局部路径指标LP 之间，复杂度相对较低，可以应用于大规模复杂网络链路预测。

综上所述，本文方法能够同时在2 个衡量指标AUC 和Precision 下取得较好的效果。AUC 和Precision 作为链路预测2 个重要但角度不同的衡量标准，在一定程度上说明了本文方法的普适性较高。此外，本文方法在8 个不同网络的实验预测效果相对较高，也验证了其在不同网络数据集上的普遍应用价值。

5 结束语

本文根据传输节点周围拓扑紧密性对资源传输节点传输概率的影响，结合节点拓扑紧密性的特点，提出一种基于资源传输节点拓扑紧密性的链路预测方法。从资源传输过程分析重要的传输节点，重点研究传输节点周围拓扑关系的量化问题，以节点聚类系数为突破点，通过分析当前聚类系数在刻画资源传输节点有效性中存在的问题，提出相应的资源传输紧密性量化方法，并基于资源传输紧密性，对任意未连边节点间的资源传输量进行刻画，给出资源传输节点拓扑紧密性指标。在多个实际网络数据中的实验结果表明，本文相似性指标适合于Precision标准，且相比其他指标具有较好的预测效果。本文方法和思路可以为资源传输过程的刻画提供一种新思路和借鉴。在后续研究中，将通过探讨传输路径有效性对资源传输过程的影响，进一步丰富和拓展基于资源传输过程的链路预测方法。