基于资源分配与图嵌入加权的链路预测算法

万杨晔,郭进利

(上海理工大学管理学院,上海 200093)

0 引 言

现实世界中不同实体之间的相互作用组成了各式各样的网络，实体之间的关系是不断变化的，所以节点和连边的增加或移除总在发生，导致网络的高度动态和复杂，理解这些网络的演化机制具有理论价值和实际意义。链路预测能处理网络的结构和演化的问题，能根据节点属性信息、结构特征来估计2个节点间存在链接的可能性[1]。在现实生活中，预测网络中的缺失链接有着广泛的应用。在京东、淘宝等线上购物网络中，链路预测能根据用户购物记录或浏览记录推荐用户感兴趣的商品；在生物领域，利用已知的蛋白质之间存在的相互作用关系[2]，准确预测蛋白质之间未知相互作用可以帮助人们大幅降低实验成本并节省实验时间；在线上社交网络如微博中，通过用户现有的关注关系，链路预测能挖掘出可能认识的朋友或感兴趣的用户[3]。

目前，基于相似性的链路预测方法在实际应用中较为常见，其计算简单、精度较高并且对于同种类型结构的网络都具有普遍良好的效果。这种相似性指标主要分3类，第1类是局部信息指标，这类指标大多在CN(Common Neighbors)指标上进行进一步的挖掘，如Adamic-Adar(AA)指标[4]给共邻节点以度值对数倒数赋权，资源分配(Resource Allocation, RA)指标[5]也是以同样思想以度值倒数赋权，CCLP (Clustering Coefficient based Link Prediction)指标[6]以共邻的聚集系数之和表示出现链接的可能性等。第2类是路径指标，主要有LP(Local Path)[7]、Katz指标[8]等，分别计算节点间不同长度的路径。第3类是随机游走指标，这类指标主要计算2节点间随机游走所需步数或时间[9-11]，相比于局部信息和路径指标有着更好的预测精度，但同时计算复杂度也变高。这些链路预测指标的研究都是在静态无权网络上进行的，相关研究表明，在加权网络上结合网络权重信息能有效提高预测效果。郭景峰等[12]提出了加权网络上的多路径节点传输的相似性。白杨等[13]提出了局部图与可靠路径相结合的加权网络预测算法。Zhu等[14]提出了加权互信息模型，结合了结构属性和链接权重的优点。Wu等[15]提出了加权的局部朴素贝叶斯模型，引入加权聚集系数来表示角色函数，将局部朴素贝叶斯模型扩展到加权网络中。Xu等[16]基于路径的贡献提出了加权路径熵算法。这些研究都展示了结合网络权重信息的链路预测方法，都优于无权网络上的指标。上述加权预测算法都是基于网络的自然权重信息，部分学者提出了对于网络拓扑结构生成链接权重的链路预测算法。Wang等[17]在生物网络中利用链接聚集系数表示链接权重来增强网络的鲁棒性，Zhu等[18]采用余弦度量的归一化聚集系数构造加权网络链路预测，袁榕等[19]提出了一种利用边的聚集与扩散特性生成链接拓扑权重的WCD(Weight of Clustering and Diffusion)预测算法。这些研究都表明网络的结构权重可以代替自然权重信息来进一步提升链路预测精度。

本文提出一种基于资源分配与图嵌入加权的方法用于链路预测，由网络的局部结构与高阶结构信息生成结构权重。首先利用资源分配指标得到的相似性作为局部信息权重，再由DeepWalk算法得到的相似性作为高阶结构信息权重，将局部信息RA权重与高阶信息DeepWalk权重相结合表示网络的拓扑结构权重，以这个结构权重进行加权链路预测，与3种不同类型的基于相似性的链路预测算法以及基于边特性的WCD加权算法进行比较，在真实网络数据集上的实验结果表明，本文提出的加权算法能有效提高链路预测精度。

1 基本概念

1.1 问题描述

给定网络G=(V,E),V表示节点集合，E表示连边集合，若网络中节点数为|V|，则网络中最多有|V|(|V|-1)/2条连边。网络的邻接矩阵用A来表示，若节点i与节点j之间有连边，则aij=1，否则aij=0。ki表示节点i的度，Γ(i)表示节点i的邻居节点集合。链路预测是为了找寻网络中缺失的链接或者未来可能出现的链接，首先定义一个相似性指标，根据相似性指标分配给目标节点对(x,y)一个分数Sxy，分数大小与当前节点对存在缺失链接或未来出现链接的概率正相关。

1.2 基准指标

1)基于局部信息的共同邻居CN指标。

2个节点拥有的共同邻居数量越多，节点间出现链接的可能性越大，节点x与y之间的相似性定义为：

sxy=|Γ(x)∩Γ(y)|

(1)

其中，Γ(x)表示节点x的邻居节点集合。

CN指标加权形式：

(2)

其中，wxy表示节点x与y之间连边权重。

2)基于路径的局部路径LP指标[7]。

LP指标是在二阶邻居的基础上加入了三阶邻居的影响，LP指标定义为：

(3)

其中，ε为调节系数，A为网络的邻接矩阵。

LP指标加权形式[10]：

(4)

其中，lx→y是从节点x到节点y的三阶路径，a和b是路径lx→y上的节点。

3)基于随机游走的重启随机游走RWR指标[9]。

重启随机游走是一个基于随机游走定义的模型，选择一个起始节点，随机游走粒子在网络上的每一步游走会出现2种情况，以概率c移动到一个随机选择的邻点，或者以1-c的概率重新回到起始节点，粒子游走的公式如下：

πx(t+1)=cPTπx(t)+(1-c)ex

(5)

其中，P为粒子在网络节点间转移的概率矩阵，矩阵元素为Pxy=axy/kx，axy为网络邻接矩阵A中对应的元素，kx为节点x的度。ex为只有第x个元素为1的N维列向量，表示粒子的初始状态，可计算式(5)迭代达到平稳状态的解为：πx=(1-c)(I-cPT)-1ex，πx是一个列向量，则RWR指标定义为2节点间相互转移的概率之和：

(6)

2 链路预测算法

图嵌入方法也被称为网络表示学习方法，能通过学习网络拓扑结构特征，将网络中的节点嵌入低维空间，得到网络节点的低维稠密向量。图嵌入得到节点向量后可以做网络研究的一系列下游任务，如节点分类、链路预测等。常见的图嵌入算法有DeepWalk[20]、Node2vec[21]、LINE[22]等。DeepWalk算法是将自然语言处理中的Word2Vec模型[23]应用在网络上的一种图嵌入算法。在自然语言处理中，少部分单词作为常用单词出现频率高，大部分单词出现频率低，而在网络上进行随机游走时，一个节点在游走路径上出现的频率也与节点度相关，少部分度大的节点出现的频率高，大部分度小的节点出现的频率低。网络节点在游走序列中出现的频率与自然语言中单词在句子中出现频率都是服从相同的幂律分布特征的。基于这种相同的幂律分布特征，将Word2Vec模型应用到了网络上，下面介绍DeepWalk算法的详细步骤。先在网络上选取一个节点作为起始节点做游走长度为t的随机游走，得到一个节点序列，以这个节点为初始点重复采样γ次。将所有节点采样完成后，将节点序列作为输入，导入Word2Vec中的Skip-Gram模型中，给节点序列的窗口大小设置为w，对于生成的节点向量Φ(vi)，最大化窗口中节点邻居的概率，不断训练最终得到节点向量：

(7)

资源分配RA指标[5]是由复杂网络中发生信息流传递或资源分配的物理过程所驱动的，信息流与资源在网络节点对(x,y)上传递的过程中，它们的共同邻居节点作为传递媒介，将信息流及资源根据自身邻居个数平均分配，节点x到节点y的资源量定义为RA相似性：

(8)

资源分配指标很好地表示了2个节点间资源传递的过程，受此启发，考虑用2个节点的资源分配指标构造链接的结构权重。

然而若单纯以资源分配指标赋予目标节点对(x,y)间的连边结构权重，如图1所示，RA指标在网络结构上只考虑到了节点x与y的一阶共同邻居a和b的信息，没有计算网络结构的更高阶信息，例如节点c和d作为节点x与y的二阶邻居也会对x与y之间连边权重产生影响，f和g等节点虽然不是目标节点对的共同邻居，但作为目标节点对的三阶邻居也会对于结构权重有一定的影响，RA指标只能展示结构权重的部分信息，因此只将之作为局部结构权重。而DeepWalk算法生成的节点向量包含了上下文的节点信息，即包含了网络的高阶结构信息，将节点向量间的余弦相似性作为节点链接的高阶结构权重，可以有效弥补RA指标不能表示高阶结构信息的缺陷。因此本文将资源分配指标与DeepWalk相似性相结合表示网络的拓扑结构权重。

图1 网络结构图

由DeepWalk算法生成的节点向量计算节点x与节点y之间的余弦相似性：

(9)

将计算得到的余弦相似性映射到(0,1)区间，然后与RA指标相结合，那么网络2连边节点x与y之间的结构权重定义为：

(10)

在上式结构权重中，将前一项称为DeepWalk权重，后一项称为RA权重。其中参数α是调节DeepWalk权重与RA权重结合的比例，当α=0时，结构权重退化为RA权重，当α=1时，结构权重由DeepWalk加权。

在进行链路预测时，先将网络利用本文的算法对网络进行结构加权，之后再利用计算出的权重信息将无权网络转化为加权网络进行加权网络链路预测，通过对权重比例参数α的调整，确定在不同网络上的最优参数，以此有效提高链路预测效果。

基于资源分配与图嵌入加权的算法流程如下：

输入：网络G(V,E)

输出：节点相似度矩阵S

1)利用RA指标得到局部权重。

2)利用DeepWalk算法得到高阶权重。

3)根据式(10)计算网络的结构权重。

4)将权重信息应用到加权算法得到相似度矩阵S。

3 实验结果及分析

3.1 实验数据集

本实验采用了4个真实网络数据集进行链路预测实验,分别是美国政治博客网络PB、线虫神经网络Celegans、佛罗里达生态系统食物链网络FWFW、线虫新陈代谢网络Metabolic。4个网络数据集的拓扑结构性质如表1所示。其中，V表示节点数，E表示边数，D表示平均度，C表示平均聚集系数，R为同配系数。

表1 网络的拓扑性质

3.2 评价指标

本文利用AUC指标评估提出的结构加权算法的预测效果，采用随机抽样的方法从网络数据集中提取10%的节点对连边作为测试集EP，剩下连边作为训练集ET的同时保证原始网络结构不发生较大变化，即训练集连边网络具有连通性。设U(|U|=|V|(|V|-1)/2)为所有节点对组成的全集，计算时，首先计算出节点对全集U的相似性得分，然后从测试集EP中与不存在边U-E中各随机选取一条边，比较2条边的相似性得分，如果测试集连边相似性得分大于不存在边得分，则加1分，分数相等，则加0.5分。独立重复地比较n次，若测试集得分高的次数为n′次，得分相等的次数有n″次，则AUC指标定义为：

显然，若随机打分，则AUC值约为0.5，AUC值越高，算法精度越高。

3.3 实验结果

参数设置：DeepWalk模型参数窗口w=5，维数d=128，采样次数γ=10，步长t=10；LP指标的三阶贡献参数设置为ε=0.01；RWR指标重启概率设置为c=0.85。

实验结果分为3个部分，第1部分是利用AUC指标分析权重调节参数α的变化对预测精度的影响；第2部分是将在最优α下的W-CN、W-LP、W-RWR指标与无权的CN、LP、RWR指标以及基于WCD加权指标在4个真实网络数据集上的预测精度进行对比，观察融入RA与DeepWalk结构权重信息后的指标的预测效果。第3部分是观察在不同训练集比例下，预测结果的变化情况。

3.3.1 参数α对预测精度的影响

将本文的结构加权算法应用在4个真实网络数据集上，忽略原网络的连边方向，以CN、LP、RWR为基准指标，将加入结构权重信息之后进行加权链路预测的指标命名为W-CN、W-LP、W-RWR。对于4个真实网络，图2展示了不同网络中结构权重调节参数α变化对3个指标预测结果的影响，参数α的变化步长设置为0.1。

(a) PB

(b) Celegans

(c) FWFW

(d) Metabolic

在Celegans、Metabolic网络上，当α值由0到0.1的过程中，AUC值都有小幅提升，在α值由0.2增大到1的过程中，基本在α=0.5左右AUC趋近最大值，后续AUC值变化趋于平缓，说明在结构权重中加入DeepWalk权重对预测精度提升是有效的。在PB网络上，W-CN与W-LP都在α=0.1左右取得最优AUC值，α继续增大AUC值有所降低，W-RWR在α=0.5之后变化趋于平缓，同样说明RA权重与DeepWalk权重相结合能有效提高预测精度。在FWFW网络上，当α=0时，即仅由RA加权时，W-LP与W-CN指标都取得了最大AUC值，加入DeepWalk权重后预测精度反而降低，这是由FWFW网络的结构特性决定的，表明FWFW食物链网络更注重局部邻居信息，在FWFW网络上RA权重更能代表结构权重。

3.3.2 算法精度对比分析

将利用本文方法对网络结构加权后进行预测的W-CN、W-LP、W-RWR指标与无权的CN、LP、RWR指标以及基于边特性WCD加权的WCD-CN、WCD-LP、WCD-RWR指标在4个真实网络数据集上的预测精度进行对比，结果如表2所示，其中W-CN、W-LP、W-RWR指标的AUC值为随参数α变化取得的最优值。

表2 加权算法与基准算法AUC值对比

从表2可以看出，使用RA与DeepWalk加权的W-CN、W-LP、W-RWR指标相较于无权的CN、LP、RWR指标，预测精度都有所提高，而相较于WCD加权的指标也有着较好的效果。其中加权后的W-CN相较CN指标预测精度平均提升3.7%，W-LP相较LP指标预测精度平均提升2.65%，即使与在相似性指标中表现最好的RWR指标相比，W-RWR也有一定程度提升，平均提升0.2%。而且与基于边特性加权的WCD方法相比，本文的加权方法在大多数网络上都表现出更好的预测效果，而WCD方法由于在拓扑权重上融入了边的扩散特性，在一定程度上削弱了节点间粒子的游走概率，导致在加权随机游走指标上表现不佳。可以看出，本文所提出的资源分配与图嵌入加权的方法相比于无权算法是有较好效果的，且与已有的加权算法相比也有一定程度的提升。

3.3.3 预测精度随训练集大小的变化情况

在本实验中，将训练集比例从0.6增长至0.9，步长为0.1，得到本文的W-CN、W-LP、W-RWR以及对应的CN、LP、RWR的AUC值随训练集大小的变化情况，如图3所示。

在4个网络数据集上，AUC值都随训练集比例的增加而增大，在训练集比例为0.9时AUC值达到最大，且在不同训练集比例下W-CN、W-LP、W-RWR的AUC值都高于相应的CN、LP、RWR指标，表明本文的方法具有较强的稳定性和更好的预测精度。

(a) PB

(b) Celegans

(c) FWFW

(d) Metabolic

4 结束语

本文对无权网络提出了一种从网络结构中生成隐式结构权重的链路预测算法。分别计算RA权重和DeepWalk权重，并按照一定比例结合得到网络的结构权重，之后应用到加权链路预测算法上，通过调整RA权重与DeepWalk权重的融合参数α找到最优预测精度。实验结果表明，基于资源分配与图嵌入加权的方法相比于未加权指标以及已有的拓扑加权指标，预测精度得到有效提高且具有良好的稳定性。