基于四阶模体的有向网络链路预测方法

常 圣 马 宏 刘树新 朱宇航

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

0 引 言

链路预测作为复杂网络研究的一个重要分支，是指通过已知的网络信息，预测网络中两个节点之间存在连边的可能性[1]。链路预测是从连边这个微观角度探究网络的结构特点以及演化规律。链路预测技术可以解决缺失信息的还原、错误信息的纠正、未来信息的预测等问题[2]。网络技术的发展使网络数据的获取变得越来越容易，同时门户网站、社交平台和网上购物等新兴事物的出现也使得对于推荐系统的需求变得更加迫切。如何吸引更多的用户、创造更多的流量、提高自己的知名度等一直是各大平台关注的焦点。通过链路预测技术，可以基于已有的用户信息和网络拓扑结构，发现用户潜在的朋友、兴趣圈子、感兴趣的商品等，将此类信息推送给用户。如果推荐内容与用户的兴趣一致性较高，将会极大地改善用户的使用体验并增加用户对于平台的忠诚度。

链路预测不仅在现实世界中有着广泛的应用价值，在理论研究中也具有重要的意义。预测效果较好的方法在一定程度上反映了网络的内在特性和演化机制，为网络演化理论提供思路，从而可以推动相关理论研究的进展。O’Madadhain等[3]曾使用链路预测方法对电话呼叫网络进行建模，进而模拟社区的形成。Leicht等[4]提出了刻画节点相似性的理论问题，而链路预测技术中基于相似性的指标[5]就是从不同角度刻画节点间的关系，这些方法可为该理论问题提供重要的研究依据。

1 相关研究

研究者们从不同的角度出发，对网络中的结构特征进行刻画，提出了丰富的链路预测算法。当前链路预测方法通常可以分为三类[6]：基于相似度的方法、概率和统计方法、分类器方法。基于相似度的方法仅利用网络的拓扑结构对连边进行预测，具有简单易懂，在集聚系数较高的网络上预测效果好的特点，因此受到了学者们的广泛关注。概率和统计方法通常根据已知的网络结构特点对网络进行建模。此类方法主要包括层次结构模型[7]和随机分块模型[8]等。这些方法虽然预测精度较好，但是计算复杂度较高，难以应用于规模较大的网络。最后一类是分类器方法，连边的存在与否可以看作为一个二分类问题，所以支持向量机(SVM)[9]、K近邻算法(KNN)[10]和多层感知器[11]等方法都可以应用到链路预测问题中。同时，节点的属性信息也可以作为特征向量应用到预测中，从而提高预测精确度，不过引入节点属性会带来复杂度增加和虚假信息等问题。此类方法预测效果通常较好，不过分类器本身的复杂性在一定程度上限制了其在现实场景中的广泛应用。

在链路预测领域的研究中，通常会把复杂网络作为无向无权的同质网络研究。抽象和简化便于我们在复杂多样的外表下捕捉到一些不变的性质，加深对系统的理解，加快研究的进程。但是，当前对于无向网络已经进行了较为充分的研究，提出了很多重要的研究成果和预测方法，然而对于有向网络的关注相对较少。现实世界中存在大量的有向关系，例如万维网(WWW)、细胞内化学反应网络、食物链网络、引文网络、微博网络和知识图谱等。以海洋生物的捕食关系为例(虎鲸→海豹→乌贼→鱼类→软体动物→浮游生物)，如果忽略捕食关系的方向性，将其作为无向网络处理，将无法知道是鱼类吃软体动物，还是软体动物吃鱼类，建模会出现较大的失真，仅预测连边的存在与否而忽略连边的方向性也会降低预测结果的意义。针对有向网络的特征，结合有向网络的连边机理和演化模型，提出符合有向网络内在特点的预测算法具有重要意义。

少数学者已经开始关注有向网络的链路预测问题。文献[12-13]曾把部分相似性指标直接应用于有向网络。Narayanan等[12]将局部随机游走推广到了有向网络，并取得了较好的预测效果。Lichtenwalter等[14]基于随机游走提出了PropFlow方法。Wang等[15]提出了有向局部路径指标。

网络模体是复杂网络演化的重要拓扑结构，是指出现频次较高的子图模式[16]。模体代表了复杂系统中的重要功能单元或者某种特定的组织结构，反映了复杂网络中子图形成的偏好性。近些年，部分学者开始尝试基于子图模式的方法来解决有向网络中的链路预测问题。Brzozowski等[17]统计了社交网络中三阶子图的闭合比例，并基于此进行了好友推荐。Zhang等[18]提出了势理论，筛选出了预测精度较高的双风扇模体(Bifan[19])。文献[20]提出了三阶子图相似度指标(TS)，其主要思想是计算13个三阶子图在整个网络中出现的频次，以此来计算节点间的相似性。Bütün等[21]分别计算9个非闭合三阶子图的相似性，而后将其组成一个9维特征向量作为机器学习的输入。

四阶模体作为复杂网络的基础结构单元之一，普遍存在于各种类型的复杂系统中。当前的方法通常忽略四阶模体在相似性计算中的作用。针对上述现状，本文提出一种基于四阶模体的有向网络链路预测方法。该方法首先提出了限定条件，对四阶子图进行简化，而后使用Z-score对四阶子图组进行筛选，使用胜出的四阶模体构造预测算法。通过在9个不同性质的真实数据集上进行实验，并与基准方法进行比较，证明该方法预测精度更高。

2 基于四阶模体的链路预测方法

非同构子图在有向网络和无向网络上的数量如表1所示。一些学者已经基于三阶模体进行了链接预测的相关研究，但是很少有学者将四阶模体应用到链路预测中去，常见的相似性方法通常忽略了四阶子图在相似性中的贡献。从表1可以看出，有向网络中三阶子图仅有13个，而四阶子图则多达199个。如果计算所有的四阶子图，一方面计算复杂度很高，另一方面不同子图之间的权重比不好衡量。所以要提出一个基于四阶模体的预测方法，首要的事情是通过约束条件对四阶子图进行筛选和简化。

表1 无向和有向网络中的非同构子图的数量[22]

2.1 四阶模体筛选

首先，这里给出了闭合四阶子图、非闭合四阶子图和非交叉闭合四阶子图在有向网络中的定义。考虑有向网络G(V，E)，其中：V是节点的集合；E代表连边的集合。exy表示由节点x指向节点y的有向边。以x为源节点的邻居集合记为Γout(x)，x的出度记为|Γout(x)|(简记为kout(x))。以x为目的节点的邻居集合记为Γin(x)，x的入度表示为|Γin(x)|(简记为kin(x))，x节点的所有邻居集合记为Γin(x)∪Γout(x)(简记为kall(x))。闭合四阶子图和非闭合四阶子图如图1所示。

图1 闭合四阶子图和非闭合四阶子图

定义1闭合四阶子图：对于一个给定的四阶子图Qabcd，如果存在eab,ebc,ecd,ead∈E，则称Qabcd为闭合四阶子图。

定义2非闭合四阶子图：对于一个给定的四阶子图Qabcd，如果存在eab,ebc,ecd∈E并且ead∉E，则称Qabcd为非闭合四阶子图。

当某个闭合四阶子图比较显著的时候，其对应的非闭合四阶子图可用于计算节点间的相似性。如果两个节点之间存在的非闭合结构数量越多，那么这两个节点间产生连边的可能性就越高。但是对于非闭合四阶子图，如图2所示，无法计算非闭合子图对应结构中节点x和y之间的相似性，因为从相似的角度出发，两个节点没有直接或间接的联系，不存在结构相似性。所以在本文中将闭合四阶子图作为分析对象。

图2 为何选择闭合模体

定义3非交叉闭合四阶子图：对于一个给定的四阶子图Qabcd，如果存在eab,ebc,ecd,ead∈E，并且eac,ebd∉E，则称Qabcd为非交叉闭合四阶子图。交叉四阶模体和非交叉四阶模体如图3所示。

图3 交叉四阶模体和非交叉四阶模体

交叉四阶子图在结构上包含三阶子图，面对交叉四阶子图，可以用三阶子图的方法来进行相似度计算。基于以上考虑，199个四阶子图中只有15个闭合且非交叉子图，如图4所示。

图4 15个闭合非交叉四阶子图

Milo等[19]对有向网络中的模体重要性进行了分析，并提出了Z-score方法。该方法统计有向网络中某一子图的数目以及随机网络中该子图的数目。在随机网络中，网络的规模和连边总数与现实网络是一样的，同时每个节点的出入度和原网络保持一致。子图显著程度可以表示为：

(1)

子图遍历和Z-score的计算成本是非常高昂的，学者们对如何降低其复杂度做出了许多努力：从最初的ESU[23]全遍历，到RAND-ESU部分遍历，以及提高内存使用率的Kavosh[24]等。在这个过程中，学者们不仅不断改进已有的算法、提出新的算法，并提供了很多实用的模体识别工具，例如MFinder[25]、Mavisto[26]、FANMOD[27]和Kavosh等等。FANMOD虽然提出得较早，但是其简单易用，遍历的效率也较高，是被普遍认可的一款工具，本文使用FANMOD来实现显著模体的筛选。

图5显示了9个网络上15个四阶子图的平均Z-score结果，横坐标表示四阶子图，纵坐标表示Z-score的值。为了使结果更加清晰明了，仅将两个最为显著的模体进行了标注，其余的子图并未具体指出。可以清楚地看出，有两个模体比其他子图显著程度要高出很多，这意味着这两个模体在实际网络出现得更加频繁。

图5 9个网络中15个子图的Z-score结果

2.2 方法设计

模体的Z-score值越高，在现实网络中出现的频次就越高。两个节点之间的相似性可以通过四阶模体对应的非闭合结构的数量来计算：如果一条连边的出现可以产生更多的显著模体，那么这条边出现的概率就越大。如图6所示，从两个最为显著的四阶模体中各去除一条边，得到其对应的非闭合子图，即三个预测器：P1、P2和F1。

图6 预测器的构造

其中基于P1结构的相似性可表示为：

(2)

预测器P2和F1的相似度公式可以参照式(2)。

函数g(z1,z2)表示特定共同邻居节点对于相似度的贡献。如果忽略节点的度数，不考虑度数对相似度的影响，可以定义g(z1,z2)=1。本文将使用邻居节点的局部信息对相似度计算进行进一步优化。如图6所示，在两个模体的非闭合结构中，有3种不同类型的节点。对于P1中的节点z1，模体的结构仅与该节点的出度有关，而与其入度无关，所以以该节点的出度的倒数为相似度的权重。类似地，对于P2中节点z2，以该节点的入度的倒数作为权重。而对于P1中的节点z2来说，模体的频次与该节点的出度和入度均有关，同时为了与其他两种节点的权重保持一致性，则以该节点出入度之和的一半的倒数作为计算相似度。基于以上考虑，g(z1,z2)的表达式表示为：

(3)

Z-score从统计的角度量化了模体的重要程度，但是对于链路预测问题，新连边出现的概率和Z-score的值并不一定是线性关系，所以难以直接确定两个模体之间的关系。这里引入了一个可变参数α，后续会通过实验来探讨其最优的取值。预测器P1和P2是由同一个模体衍生出来的，其地位是相等的，给它们分配相同的权重。QMI(Quad Motifs Index)可以由P1、P2和F1三个预测器的相似性函数之和的形式表示。基于四阶模体的相似性函数可以表示为：

(4)

根据前面的论述，最终的相似度计算可以展开为：

(5)

3 仿真实验

3.1 基准方法

为了了解基于四阶模体的预测方法QMI的实际预测效果，本文选取了8个经典预测指标与QMI的预测结果进行对比，简介如下：

(1) 共同邻居指标(CN)：该方法认为如果两个节点的共同邻居越多，则它们之间存在连边的可能性就越大。

s(x,y)=|Γout(x)∩Γin(y)|

(6)

(2) Adamic-Adar指标(AA)[28]：该方法在CN的基础上，加入了对于节点度数的考虑，认为低度数节点对于相似度贡献较大。

(7)

(3) 资源分配指标(RA)[29]：该指标受到资源分配过程的启发，给高度数节点较少的权重。

(8)

(4) Sørensen指标(SO)[30]：该指标常用于生态系统的数据集中。

(9)

(5) Leicht-Holme-Newman指标(LHN)[31]：该方法在CN的基础上加入了对节点度数的考虑。

(10)

(6) 全路径指标(Katz)[32]：Katz计算整个网络中所有路径的长度，并根据路径的长度给予不同的权重，路径越长分配的权重越低。Katz的相似度矩阵可以写为：

S=(I-αA)-1-I

(11)

式中：A表示网络的邻接矩阵；I表示单位矩阵；α为可调参数，控制不同路径的权重。

(7) 局部路径指标(LP)[33]：该方法与Katz指标类似，但是只考虑有限长度的路径。LP的相似度可以表示为：

S=A2+αA3

(12)

(8) 矩阵森林指数(MFI)[34]：该方法基于矩阵森林理论，其相似性矩阵可表示为：

S=(I+L)-1

(13)

式中：L表示网络的拉普拉斯矩阵。

3.2 数据集

本文选择的9个公开网络数据集如下。

(1) 医生网络(Physicians)[35]：这个有向网络描述的是4个城镇中246名医生之间创新思想的传播关系。

(2) 电子邮件网络(Email)[36]：欧洲研究机构的电子邮件网络，节点代表用户，有向边代表用户发送过的邮件。

(3) 邮件网络(DNC)[37]：这是民主党全国委员会(DNC)的电子邮件网络。有向边表示人员之间的邮件往来。

(4) 食物链网络(FWMW)[38]:雨季的食物链网络，节点表示物种，有向边代表捕食关系。

(5) 线虫代谢网络(CElegans)[39]：该数据集是秀丽隐杆线虫的代谢网络。节点是代谢物(如蛋白质)，连边是代谢物之间的相互作用。

(6) 象棋比赛网络(Chess)[37]：该网络是国际象棋比赛的结果。每个节点是国际象棋棋手，有向边代表棋手之间的比赛。

(7) 政治博客网络(PB)[40]：这是美国政治博客之间的超链接网络。对于博客A和博客B，由A指向B的有向边表示同方向的超链接。原网络是含有自环和多连边的，本文会忽略这些特殊情况。

(8) 青少年网络(Adolescent)[41]：节点代表学生，两个学生之间的有向边表明左边的学生选择了右边的学生作为朋友。

(9) 维基百科(Wikivote)[42]：这是维基百科中的用户选举管理员的投票网络。节点代表用户，边代表投票。原网络的连边是有正负边两种情况的，本文也对其进行归一化处理。

每个网络的统计特征如表2所示。其中：|V|是整个网络中节点数目，|E|表示有向边的数量，Kout是最大出度，Kin是最大入度，k是平均度数，d代表网络直径，C为聚集系数。

表2 数据集的统计特征

3.3 评价指标

实验度量指标采用AUC[43]和Precision[44]对预测效果进行评价。AUC是坐标图中ROC曲线以下的面积，其具体含义是正确预测测试集中边的分数值大于不存在边的概率。AUC的计算通常采用随机抽样的方式进行。每次随机从测试集中选取一条边，并随机选一条不存在的边，如果测试集中的边分数值较大，就加1分，相等就加0.5分。AUC的计算为：

(14)

式中：n1表示测试集中的边的分数大于不存在的边的分数的次数；n2代表分数值相等的次数。

Precision表示排名靠前的L个预测边中，正确预测的比例。如果在前L个预测边中，有m条边是正确的预测，则：

(15)

3.4 预测结果

为了衡量基于四阶模体的预测方法QMI的实际表现，本节以AUC和Precision两个指标作为评价标准，在9个不同性质的真实数据集上进行100次独立实验(每次实验都会重新划分训练集和预测集，从而保证结果的可靠性)，并对实验结果的平均值进行比较分析。具体包括：① QMI在不同局部信息情况下的预测效果； ② QMI在不同α取值条件下的预测结果；③ QMI与经典相似性方法结果对比。

(1) 局部信息的影响。首先，给出QMI在考虑不同的节点度信息情况下的预测结果之间的差异，从而验证本文提出的对于节点度的考虑能否提高预测的效果。QMI0表示忽略共同邻居节点的度信息，此时g(z1,z2)=1。QIMIM代表考虑共同邻居节点的出度和入度信息，但是不考虑不同模体间的区别，对所有模体同等对待，此时g()定义为：

(16)

图7展示了在不同局部信息的情况下QMI的AUC结果。横坐标表示9个数据集，纵坐标表示AUC的结果。可以看出，QMI的AUC值在所有数据集中都是最高的。部分数据集，例如CElegans对于共同邻居的度信息更加敏感，AUC的差异稍大，而剩余网络的预测结果较为接近。具体到个别网络又表现出不同的特点。对于Email来说，QMIM和QMI0的AUC结果差异很小，但是和QMI的差异较大，这说明不加区分地考虑度信息对于预测是没有实质性提升的。在PB中，QMI和QMI0又比较接近，QMIM表现较差一些，这意味着不区分入度和出度对于预测甚至是有反作用的。

图7 QMI在不同局部信息下的AUC结果对比

图8展示的是在考虑不同的局部信息情况下QMI的Precision结果。总体上看，QMI和QMI0在9个网络中的有着类似的走势，而QMIM的Precision一直处于较低水平，这再次说明了入度和出度在有向网络中有着不同的地位和作用。在FWMW网络中，QMI的Precision高于0.8，而QMIM不到0.2，提升0.6以上。在大多数网络中，QMI的预测精度相对于QMIM提升都达到了2倍以上。CElegans网络是个例外，在这一网络中QMIM的预测精度最高，达到了0.233，但是QMI的预测结果与QMIM相差不大。

图8 QMI在不同局部信息下的Precision结果对比

总的来说，对于不同情况的共同邻居，加以区分对待，考虑其出度和入度与所在模体之间的具体关系，可以提高预测的准确度。

(2)α取值的影响。首先分析QMI在不同α取值条件下的AUC结果。如图9所示，每幅子图表示一个数据集。在所有数据集中，α=0或α=1时，AUC均没有达到最大值，这表明两个模体都是不可或缺的，它们对于相似度结果的影响都很大。此时需要考虑的问题是如何确定两者之间的比例。在不同的数据集中，AUC曲线的走势有较大的差异。在Email网络中，AUC结果出现了一定程度的震荡，其余网络AUC曲线的走势较为清晰。在FWMW、CElegans和PB中，AUC值随着α的增大稳定增长，在α=0附近增速稍快，后续相对平缓，说明这些网络对于P1和P2结构的敏感性不强。CElegans网络在α达到0.7以后有小幅下降。当α在0到0.1的区间时，Wikivote和DNC的AUC曲线非常陡峭，这说明预测器P1在这些网络中起到了明显的作用。在Physicians网络中，AUC曲线在α取0和1附近均有大幅度的变化，而其余情况相对稳定，说明预测效果同时依赖两个模体，但是它们之间的比例关系对于预测影响有限。纵观所有数据集，α在0.4到0.8之间时，AUC都达到了最优值。同时在该区域，AUC值是较为稳定的，浮动很小。因此，在进行预测时，最好将α的取值限定在0.4～0.8范围内。

图9 不同α取值条件下QMI指标的AUC结果

图10是QMI在不同α取值条件下的Precision结果，每幅子图表示一个数据集。除了Chess之外，其他网络的Precision在α=0附近都有明显的提高，这意味着预测器F1在Precision方面发挥着重要作用。在Email、Physicians、Adolescent和Chess中，Precision在达到峰值后都有一定程度的回落，回落的速率代表了对于P1和P2结构的敏感程度。在FWMW、CElegans和Wikivote中，Precision曲线走势稳定，预测精度随着α的增大稳定增长，到达最优值之后趋于稳定，说明F1在这几个网络中作用更加重要。Adolescent和Chess在α取0.3 达到最高精度，Physicians在α约为0.6时获得最好预测结果，其余网络的都在α大于0.8之后达到峰值。不同于AUC，Precision曲线随着α的变化浮动较大。在FWMW中，Precision的最大值和最小值之间存在差异高达0.7，其余网络的曲线相对稳定许多。

图10 不同α取值条件下QMI指标的Precision结果

根据实验结果，并兼顾所有数据集的AUC和Precision，建议α取0.6。

(3) 与基准方法的对比。为了进一步了解QMI的预测效果，本文选取了8个经典预测指标与其进行对比分析。表3中给出了QMI和基准方法在9个数据集中的AUC结果。可以看出，在大多数数据集中，本文方法QMI的预测效果都是优于其他方法的。除了Physicians和Adolescent，QMI在剩余的网络中均取得了最高的AUC值。即使在这两个网络中，QMI的AUC值也非常接近最佳值，在Adolescent中与最高预测结果仅相差0.003，Physicians中相差0.02。除FWMW 和Adolescent网络之外，大多数网络中QMI的AUC值均高于0.91，由此可以看出该方法的预测效果较好。由于考虑了更多信息，全局方法Katz效果通常好于局部方法CN等，半局部方法略差于全局方法，但是相对于局部方法也有所提升。在局部性方法中，RA方法比CN多了对节点度数的考虑之后，预测精度有小幅提升，这说明节点的度数对相似度是有影响的。同样考虑的是节点度数，但是RA考虑的是共同邻居节点的度数信息，SO和LHN等考虑的是被预测节点的度数信息，相比而言，RA的效果是好于SO和LHN的，可以推测，共同邻居节点的度数与相似度的关系更加紧密。在有些网络中，SO和LHN甚至还略差于CN，这说明被预测节点的度数并不总能提升预测效果，在计算相似度时，最好是考虑共同邻居节点的度数。

表3 QMI与基准方法的AUC结果对比(可调参数α=0.6)

续表3

表4给出了QMI与基准方法在9个数据集中Precision的比较结果。对比可知，基于四阶模体方法的预测精度在7个数据集中达到了最优。在PB和Email网络中，QMI的效果与最优值也比较接近。全局方法虽然考虑了更多的拓扑信息，但是其Precision效果并不理想。在一半的网络中，局部方法CN的预测精度高于全局方法Katz，这可能是因为Katz对于AUC的关注更多。在局部方法中，RA等方法比CN多了对节点度数的考虑之后，Precision反而有所下降，而AA的预测结果有所提升，这说明AA指标对于度数的处理(取对数)更契合Precision。与其他指标相比，MFI的预测结果在不同网络中浮动较大。在FWMW和CElegans中，MFI接近最高的Precision值，但在其他网络中，MFI的精度又异常低。

表4 QMI与基准方法的Precision结果对比(可调参数α=0.6)

4 结 语

为了从为数众多的四阶子图中选出显著模体，从而提出一个预测效果较好的方法，本文在闭合四阶子图和非交叉四阶子图两个条件下，过滤了大量的四阶子图，在此基础上又使用FANMOD计算了四阶子图在9个不同性质网络中的显著程度，从中选取了2个最为显著的模体。以显著模体对应的非闭合结构作为相似度计算的依据，讨论了共同邻居节点的度信息在预测中的作用，通过实验确定了可调参数建议的取值区间。通过与8个经典预测指标的对比，结果表明本文方法可以同时提高AUC和Precision的结果。

除了四阶模体以外，还存在很多高阶模体，高阶模体在相似性计算中起到何种作用还有待研究，不同阶模体之间的关系如何衡量等都是今后值得研究的问题。