基于加权投影的二分网络的链路预测

张佳慧 张 婷 吕来水 张 娜

(南京理工大学计算机科学与工程学院 江苏 南京 210094)

0 引 言

网络科学一直受到科学界关注的领域，尤其是那些模拟复杂系统组织的科学研究。网络还可以很自然地描述各种社会结构。在这样的网络中，顶点表示实体，链接表示实体之间的通信或关系。社会网络反映了个人或社会组织及其关系，如伙伴关系或友谊。社会网络分析在社会学领域引起了越来越多的关注，它分析和探索社会对象之间的潜在关系。近年来，社交网络分析在电子商务分析、市场建模等诸多商业领域也引起了人们的高度关注。

根据复杂网络中已知节点的类型，可以将网络分为单分网络和二分网络[1](如图1所示)。单分网络也可称为单层网络，是一种普遍广泛研究的网络类型；而二分网络是指网络中存在两类节点，这两类节点通过边形成关联，节点类内部没有边相连。该网络形成的拓扑结构被称为二分图，现实生活中存在许多二分网络，例如演员-电影网[2]、科学家-合作网[3]等。这两类具有不同属性的节点类型中，一类节点是参与某类活动、事件的主导者，如演员、科学家等，另一类节点是这些主导者从事的活动或者事件，例如电影、文章等，这些都可以作为区分为二分网络中两类节点的依据。

图1 单分网络和二分网络

目前针对二分网络的研究主要分为：(1) 把二分网络投影到单层网络上再进行网络分析；(2) 直接基于原始二分网络进行网络研究。现在研究得比较多的是第一种，而针对二分网络的投影又分为无权投影和加权投影[4]。图2是简单的无权投影，无权投影虽然简便直接，但是却丢失了关于二分网络结构的信息，研究意义不大。而加权投影又分为很多种，各种加权投影的区别体现在对权重的设定不同，一种比较直接的投影方法是根据两个节点的共同邻居节点进行投影[5]，还有根据节点的贡献程度不同而设置具体的权值函数[6]。

图2 无权投影

链路测试[7]是网络分析[8]中的一个重要研究领域。链路测试的目的是从网络的现有拓扑特征中检测未观测到的链路，或者从网络的当前拓扑结构中预测未来链路。在社会保障网络中，链路测试用于发现恐怖分子或犯罪分子的地下组织[9]，而在人类行为网络中，链路预测用于识别和分类人的活动和移动[10]。链路预测在反映社会关系的无线网络中也有许多应用，如通信网络、电子邮件网络和传感器网络。在传感器网络中，利用链路预测来发现动态时间特性[11]，以保证信息传输保密[12]，实现最优路由[13]。

二分网络是目前比较热门的研究话题，基于二分网络的链路预测具有广泛的研究价值。针对单分网络而言，链路预测有基于节点对之间相似度来进行研究的，如吕琳嫒[14]通过基于网络结构的相似性得到很好的链路预测效果；基于拓扑结构展开的链路预测，如Liben-Nowell等[15]基于网络连接结构的链路预测理论进行拓扑链路预测；针对机器学习研究出的链路预测方法，如Pujari等[16]将监督秩聚合应用于复杂网络中的链路预测；运用概率学原理模型研究出的链路预测，如Lü等[17]基于可预测的模型机制来预测缺失链路的能力。针对二分网络而言，其实是对单分网络链路算法的一种提升、改进和创新。基于机器学习中监督学习的方法来训练预测模型，如Benchettara等[18]将二分网络中的链路预测看成是二类的分类问题，采用监督学习的方法来训练预测模型；引入新的拓扑特征来实现对二分网络中节点对的链路的概率的量化，如文献[19]；基于图模型来预测二分网络中节点对的链路，如文献[20]。二分网络中产生的链接属于不同类别，对应的邻居节点也属于不同类别，

本文主要通过一种基于资源分配的加权算法对二分网络进行投影，并且利用得到的权值矩阵，来得到同类节点之间的相似度度量，通过节点之间的相似度度量计算出两类节点未链接边之间资源分配比重的比较，得到节点之间链路最高的连边，从而达到链路预测的目的。最后利用AUC来对算法进行实验，验证本文算法的有效性和准确性。

1 投影相关知识

目前研究的技术中已存在许多关于投影方面的技术，有一些基于系数进行投影的技术，比如Eculidean、Pearson等。本节通过与其他技术进行比较的方法来体现本文算法的优势。在每一种技术中，二分图G的实体被认为是二元向量。假设有一个二分图由两类实体A={a1,a2,a3}和B={b1,b2,b3,b4,b5}组成。假设a1链接b1、b4和b5，那么a1={1,0,0,1,1}。在下面的介绍中，采用投影到类A上的做法。

1.1 基于Eculidean的投影

在数学中，欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”(即直线)距离[21]。使用这个距离，欧氏空间称为度量空间。基于Euclidean的投影技术利用了欧氏距离的概念。a1和a2向量被认为是B维空间中的点，则a1和a2之间的欧氏距离为：

基于Eculidean的相似度与欧氏距离成反比，即s(a1,a2)=1/d(a1,a2)。基于Eculidean的相似度不仅强调了a1和a2中1的共存，而且还强调了0的数量。

1.2 基于Pearson的投影

Pearson相关系数是用来衡量两个数据集合是否在一条线上面，即衡量定距变量间的线性关系[22]。基于Pearson的二分网络投影技术，通过计算a1和a2向量的相关系数如下：

式中：cov(a1,a2)是a1和a2的协方差；σa1和σa2分别是a1和a2向量的方差。Pearson相似度也赋予了联系的共同缺失的重要性，而不仅仅是共同存在的重要性。

通过计算例子中的Pearson相似度，其中a1={1,0,0,1,1}和a2={1,0,1,0,1}，得到结果s(a1,a2)=0.05/(0.3×0.3)。

2 二分图相关知识

二分图G=(U,V,E)表示二分网络，其中U和V是G中节点的两部分。本文使用字母(如c、d)表示U部分节点，使用小写字母(如x、y)表示V部分节点。E是G中边的集合。在同一组U或V中，节点之间没有边缘；即每条边(c,x)∈E都满足c∈U,x∈V。

假设U有n个节点，V有m个节点，G的邻接矩阵采用非对角块形式：

式中：0n×n和0m×m分别是n×n和m×m的全零矩阵。

An×m为n×m的非零矩阵。由于邻接矩阵是对称的，可以简单地用矩阵An×m表示二分图G，其中每一行表示U集合中的一个节点，每一列表示V集合中的一个节点。

图3展示了演员-电影二分网络。在这个网络中，有两种节点，分别被标注成圆形和正方形。圆形节点代表演员，正方形节点代表电影。使用N(c)={x|x∈V,(c,x)∈E}来表示图G中的节点c的邻居节点的集合。

为了分析二分网络中的链路存在的可能性，首先将其映射到一个被称为投影图的单层网络上。

定义1投影图。给出一个二分图G=(U,V,E)，它的U投影图定义为单层网络GU=(U,EU)，其中边的集合是：

EU={(c,d)|c,d∈U,∃x∈V,x∈N(c)∩N(d)}

从定义1可以看出，如果二分图G中的U部分的节点c和d在V部分中至少有一个共同的邻居，那么在U部分的投影图中就存在一个链接(c,d)。同样，可以定义G中的V部分的投影图GV=(V,EV)，其中边的集合是：

EV={(x,y)|x,y∈V,∃c∈U,x∈N(x)∩N(y)}

3 主要方法

本文采用相似性度量获得顶点之间的相似度得分，通过利用二部图中的信息，根据二部图中U部分和V部分节点是否存在共同邻居，将二部图投影到单部图中。并采用基于资源的均匀分配加权算法，得到同类节点之间的资源分配权重。通过考虑复杂网络的整体结构，利用资源分配比重的大小进行链路预测。由此，可以克服传统相似性度量的大部分问题。

为了预测二分网络中可能存在的链接，需要根据其投影图定义其候选边。

定义2候选边。设二分图G=(U,V,E)，c∈U,x∈V是图中的两个节点，(c,x)∉E。图中U部分的投影图为GU=(U,EU)，通过对图G添加一个新的链接(c,x)∈U×V，可以构建一个新的二分网络G′=(U,V,E′)，其中E′=E∪{(c,x)}。G′U=(U,E′U)是图G′的投影图，把(c,x)称为图G在U部分投影的候选对(Candidate Pair，CP)。同样地，也可以定义出V部分投影的候选对。

(c,x)是G=(U,V,E)中的一对节点，c∈U,x∈V且(c,x)∉E。GU=(U,EU)是图G中U部分的投影图表示。图GU中节点c∈U的邻居节点的集合是NU(c)={d|d∈U,(c,d)∈EU}，同样地,节点x∈V的邻居节点的集合是NV(x)={c|c∈U,(c,x)∈E}。

也就是说，节点对(c,x)是U投影图的候选节点，当且仅当：

NU(c)∩N(x)≠∅且c∉N(x)

如果(c,x)是图G中的候选对，那么对于每个满足NU(c)∩N(x)的节点D，在投影图GU中就有一个链接(c,d)。既然(c,x)是图G中的候选对，则c∉N(x)，并且图G中不存在边(c,x)。如果向二分图中添加边(c,x)，那么对于每个满足d∈NU(c)∩N(x)的节点，在GU中就会有一条新的连边(c,d)，并且在图G中c和d都与节点x有链接。既然GU中包含(c,d)，所以把(c,d)作为投影图GU被候选对(c,x)覆盖的一种模式。

通过网络中资源分配过程的启发，本文将资源分配的加权进行如下分解：

(1) 初始化V部分节点资源f(vx)=axc。

(2) 将V部分中每个节点得到的资源平均分配给与它相连的U部分的节点(二分网络本身是不加权的)，则U部分的节点得到的资源是来自于每个与它相连的V部分节点通过平均分配得到的资源之和f(uc)：

式中：k(vx)表示在二分网络中υx节点的度。

(3) 将U部分节点得到的资源再次平均分配到V部分节点中与它相连的节点上，与步骤(2)中类似，得到基于投影实现的V部分节点的资源分配值即得到关于候选对(c,x)的评分估计值S(ucvx)：

(4)wxy表示V部分节点中x希望分配给y的资源的比例。根据理解可得，S(ucvx)还可以写成：

(5) 根据步骤(3)-步骤(4)可以计算出wxy：

wxy可以表示为V部分投影中，节点y对节点x的连边的权值，并且wxy≠wyx,x和y的度决定了这两个值的区别，根据节点生成的度和节点对之间的共同邻居数可以看出，节点之间的权值是不对称的。因此W={wxy}m×m表示经过基于资源分配的加权算法得到的加权投影矩阵。

(6) 根据步骤(4)得到的投影之后V部分分配到的资源值，可以预测U部分中每个节点c与V部分中未链接的节点x之间是否会产生链接。计算U部分中每个节点c与V部分中未链接节点x的S(ucvx)值：

(7) 根据每个节点c得到的所有S(ucvx)值，并对这些值进行降序排列，值最大的S(ucvx)所对应的节点x即为与节点c最有可能产生链接的节点，即完成一次链路预测，要预测每个U部分的节点c，需要对步骤(6)中的式子重复计算n次，完成整个链路预测。

本文方法也可以采用随机游走的观点来解释。通过随机漫步游走在二分网络上的顺序过两类节点，那么S(ucvx)记录了还有多久候选节点对(c,x)会在二分网络中出现链接的概率。

4 实 验

本文实验采用了Southern Women、MovieLens两个数据集来进行实验验证，并对实验结果进行分析。实验过程要采用Python来完成代码设计，并进行结果分析图的绘制。为了验证算法的精确度，将本文算法(WLP)与基于Euclidean的相似度预测算法(ELP)和基于Pearson的相似度预测算法(PLP)进行比较。

4.1 Southern Women数据集实验分析

Southern Women数据集由Davis在1930年收集，是二分网络中被广泛用来测试的数据集，其主要结构如下：18位妇女和14个由这些妇女形成的社会活动。在二分网络中，把18位妇女当作一类节点，14个社会活动当作另一类节点。如果一个妇女参与了一类活动，那么该妇女与该活动之间就有一条连边，而妇女节点之间不存在连边。该数据集的网络结构组成如图4所示。该数据集的详细数据信息如表1所示。

图4 Southern Women网络结构

表1 Southern Women数据结构

为了测试本文提出的算法，将该数据集的93条边随机分为两部分：训练集包含83条边，测试集包含10条边。训练集作为已知信息处理，测试集用来评估算法的准确性。在该数据集上分别对算法WLP、ELP和PLP进行10次实验，每次随机抽取10%的数据作为测试集，剩下90%的数据作为训练集。实验结果如表2所示。

表2 Southern Women上的三种方法实验结果(AUC)比较

可以看出，虽然三种方法的准确性有些时候很相似，但是在整体上来看，WLP算法能够取得足够高的准确性，说明本文算法具有有效性。

4.2 MovieLens数据集实验分析

MovieLens数据集本身比较庞大，涵盖了多个用户对多部电影的评级数据，也包括电影详细数据信息和用户个人属性信息。由于该数据集很大，通过整理该数据集，提取用户的ID和电影的ID，如果用户喜欢该电影，则用户和该电影之间就有一条连边，用户和电影分别属于二分网络的两类节点。该数据集对应有943个用户节点和1 682个电影节点，由这两类节点组成一个二分网络。

为了测试本文算法，将该数据集的所有链边分为训练集和测试集，在该数据集上分别对算法WLP、ELP和PLP进行10次实验，训练集占90%，测试集占10%。训练集作为已知信息处理，测试集用来评估算法的准确性。结果如表3所示。

表3 Movielens上的三种方法实验结果(AUC)比较

大部分情况下，WLP的精确度高于ELP和PLP，10次实验中分别有2次和1次结果低于ELP和PLP，可见WLP算法可以保持高精度准确性，说明本文算法具有一定的有效性。

5 结 语

本文提出一个基于资源分配加权投影的二分网络链路预测算法。该算法通过将二分网络图投影到一个图上，并通过资源分配得到投影图的权值，根据所得权值可以得到两个不同类节点之间的相似性度量，根据节点的相似性度量预测链路存在的可能性。本文将算法WLP与ELP和PLP进行实验比较，得出本文算法略优于其他两种算法的性能。当然，本文算法还有可以改进的地方，比如资源分配的初始值是否可以定义为其他值或者针对加权二分网络的资源分配研究，这些都是下一步需要进行研究的内容。