融合多元影响力节点识别指标MPR的链接预测

伍杰华,熊云艳,张 顶,陈嘉志

(1.广东工贸职业技术学院 计算机与信息工程学院,广州 510510; 2.华南理工大学 计算机科学与工程学院,广州 510641)

0 概述

在现实生活中,各类实体之间的复杂关系均可表示为网络结构,而节点之间的链接是该结构的基础和核心组成部分[1]。因此,对链接形成规律进行挖掘和分析具有重大意义,链接预测是其中一个重要的研究方向[2]。

链接预测技术基于已观察到的复杂网络结构属性预测节点之间是否存在链接[3],或者通过挖掘网络的历史结构信息预测节点之间未来发生链接的可能性[4]。该技术能够帮助研究人员分析知识图谱实体之间的关联[5],理解科研合作者之间的合作关系变化,剖析生物蛋白质功能网络中蛋白质之间的隐含功能关系[6]等。此外,该技术还能够从理论层面帮助研究者划分社交网络圈,把握用户影响的演化规律[7],为网络表示学习提供评估指标[8]。随着网络复杂性的提高和规模的扩大,链接预测的研究热点从同质网络转移到异质多元网络。本文结合影响节点识别技术,提出一种适用于多元复杂网络的链接预测算法。

1 相关工作

链接预测算法一般分为基于网络结构相似度的学习与预测和基于网络特征的学习与预测2类[3]。基于网络特征的学习与预测算法的相关工作可参考文献[3-4],此处不再叙述。对于基于网络结构相似度的学习与预测算法,其基本思想是结合统计学、社会学、图论和拓扑学等领域的概念,挖掘网络的结构信息,计算2个潜在节点对之间的链接概率(相似度得分)。一般来讲,2个潜在节点对的相似度越大,其产生链接的可能性越高。由于网络的结构信息可以表示为不同的类型,因此链接预测算法可以分为基于邻接节点相似度、基于共邻节点相似度、基于路径信息相似度、基于随机游走相似度、基于社交结构信息相似度等。同时,由于网络结构信息的表示方式有无限可能,因此目前仍有许多工作围绕如何挖掘网络的结构信息展开。

随着网络结构的不断变化,其节点也变得更加复杂,出现了链接属于不同类型或者存在多元关系的网络,称为多元(多维度、多维)网络[9],每一个维度的网络称为子网络。以实验数据集Student为例[10],该数据集利用本-古里安大学的必修课程“计算机与网络安全”收集的数据,构建多元社交网络。该网络包含以下3个维度的关系:

1)Partner链接关系,定义为学生作为合作伙伴一起完成理论或编码的作业任务。

2)Computer链接关系,定义为2名学生使用同一台电脑完成在线作业。

3)Time链接关系,其为学生之间的第2个隐式连接,定义为学生通过不同的计算机共同提交解决方案。

上述3个维度的关系不仅在逻辑上存在关联,在显式结构上也有关系,因此,在多元网络中,传统的基于单一维度网络(或称同构网络)的相似度算法并不能反映这种多元属性。图1展示了Student数据集中的2个维度(A,B)的局部网络结构,其中,虚线表示不同维度之间节点的链接关系,实线表示单一维度子网络内部的链接关系。可以看出,一个维度节点(A子网络的实心节点)的属性不仅受其所处维度子网络中其他节点(A子网络的空心节点)的影响,也受其他维度子网络节点(B子网络的实心节点)的影响。因此,在设计相似度链接预测算法时,应该把多元属性考虑进去。同时,由于链接的2个相同节点之间的多样化关系会产生多个互相影响的子网络,即一个子网络的拓扑属性变化通常会影响其他网络的属性变化,因此一种类型的子网络可以成为另一类型子网络关系变化的约束或推动力量[11]。图2和图3给出Querylog数据集的度和聚类系数分布关系,可以看出,不同子网络的结构存在相似性,可以充分利用多元属性各维度的相似性结构设计预测指标,这在单一同构网络中是无法实现的。

图1 多元网络局部结构示意图Fig.1 Schematic diagram of local structure inmultiplex network

图2 Querylog数据集的度分布Fig.2 Degree distribution of Querylog dataset

图3 Querylog数据集的聚类系数分布Fig.3 Clustering coefficient distribution of Querylog dataset

多元链接预测算法主要通过对维度之间的关联关系进行建模实现。文献[12]通过引入多元网络维度之间的相关性构建度相关、边相关等属性,拓展了CN、AA、RA等传统的相似度度量,设计了一系列新的预测指标。文献[13]定义了影响力传播和时序信息2种多维度特性,并由此构造出多维度链接预测指标MRIP(Multi-Relational Influence Propagation)和MRT(Multi-Relational Temporal Link Prediction)。文献[14]采用隐含空间网络模型提取子网络的低维因子,通过似然比来检验因子的相关性,并建立了一个冷启动的多维网络链接预测模型。但是,由于异构网络节点和链接的类型较为复杂,直接采用相似度计算方式进行链接预测比较困难。文献[15]模型虽然基于局部指标提供了快速的解决方案并取得了可接受的结果,但它并没有在多元网络全局视角下确定不同共同邻居各自的贡献度。此外,该模型利用路径和随机游走指标,根据节点之间较长的链接属性进行预测,其优点在于可从网络的准局部/全局视角构建,缺点是可能会忽略共同邻居的局部结构。一些基于邻接矩阵的全局指标能够充分利用网络全局属性,但是此类算法运行速度慢,难以平衡预测性能和计算效率。

影响节点识别(Influential Node Identification,INI)[16]是网络分析的一个重要方向。本文针对多元网络链接预测任务,提出一种基于多元PageRank(Multiplex PageRank,MPR)[17]的链接预测算法。该算法给出MPR指标详细的定义和计算方法,通过MPR为每个节点定义一个多元排名函数并分配一个评分来量化节点的重要性,然后把该全局得分集成到微观层面的基于共邻节点的相似框架中,从而得到预测结果。

2 问题描述

2.1 问题定义

给定一个多元网络G=(V,E)。其中,G={G1,G2,…,GL}表示该多元网络共有L个维度的子网络,称为L个层,V定义为节点集合,|V|=N,E={E1,E2,…,EL}表示每个维度子网络的链接集合。第个维度的子网络定义为G=(V,E),=1,2,…,L。同时,G的邻接矩阵可定义为A,其中每一项或者分别表示在该子网络中的链接是否存在。

2.2 预测过程

链接预测算法首先随机选取其中一个层次的子网络G,按照比例r把其划分为训练网络和预测网络其中,且然后,结合其他层次子网络的关联影响以及所处子网络的结构属性,对中所有潜在节点对计算相似度得分,实现如下映射:

3 基于PageRank的链接预测算法

3.1 PageRank算法

PageRank[18]算法由Google的两位创始人于1998年4月举行的第七届国际万维网会议上提出。该算法的初始目的是对网站进行排名,通过计算页面链接的数量和质量粗略估计和确定网站的重要性,并把相关排序结果应用在Google的搜索引擎中。随着研究的不断深入,PageRank算法及其变体已被广泛应用于挖掘具备互联结构的信息网络的重要性节点[16]。

给定一个节点i,该节点的得分xi可表示为如下形式:

(1)

其中,N(j)表示节点j的邻接节点集合,αA是一个阻尼因子,即一个随机游走节点j跳到其任意一个邻居节点的概率是αA,而其随机均匀选择跳跃到其他任意节点的概率为1-αA。因此,PageRank可以理解为具有额外随机跳跃能力的静止分布。

3.2 基于PageRank的链接预测指标

网络拓扑结构对基于相似度的链接预测方法至关重要。局部的、准局部/全局的和全局的链接预测算法的目的,是为每个相关的邻接节点赋予一个量化的区别性的影响力(贡献)。例如,经典的RA指标使用1/|N(ω)|确定共邻节点ω的不同影响力。其中,1/|N(ω)|表示如果邻接节点度较大,那么其对链接生成的影响力较小。在微博社交网络中,共同朋友的影响力大小在用户关系预测问题上具有重要的作用,度越大的节点表示影响力越大的用户(权威用户)[16]。假设存在2对尚未存在关系的用户有相同数目的共同朋友,其中一对用户的共同朋友权威用户多,另一对用户的共同朋友权威用户少。实验结果表明,后一对朋友产生关系的可能性要比前一对高,即共同朋友影响力大小对关系的产生起反作用。根据上述讨论,任意2个节点u和v,其基于PageRank的相似度得分PR(u,v)计算过程如下:

(2)

式(2)的核心思想是一个共邻节点的影响力越大,潜在预测节点对提供的贡献就越小,即两者成反比关系。虽然现有的研究把一些重要性节点发现指标引入链接预测问题中[2],但其基本思想是不同的。本文将影响力放在分母上,可更直观地表示上述反比关系。节点影响力排名得分的优势主要体现在以下2个方面:

1)判别性。影响力节点识别方法已成功应用于各种基于信息网络结构的实际分析任务,如控制疾病和谣言动态、跟踪意见传输和促进信息传播等,其可以有效地衡量一个共同邻居如何影响潜在节点。

2)全局性。许多重要性节点发现指标均考虑了路径或扩散信息的影响,同时对网络中节点的扩展能力进行排序,从而更准确快速地捕捉共同邻居的整体贡献。

4 基于MPR的链接预测方案

由于基于PageRank的链接预测算法仅针对单一维度的同构网络,因此当其应用于多元网络的链接预测场景时,也仅考虑其中一个维度的子网络。根据前文所述,当同一对节点可以通过链接连接不同维度的子网络时,扩展PageRank以捕获一个层中节点的排名,可以影响并受其他层中相同节点的排名影响的程度,即定义一个考虑网络多元关系的节点影响力鉴定指标MPR[19]。

为了将PageRank影响力节点度量扩展到多元网络,本文假设节点在一个维度的子网络中具有的中心性影响节点在另一维度中也具备中心性。各维度子网络之间的这种相互作用具有双重性质[19]。首先,一个子网络中节点的重要性可能会增加该节点在另一子网络中的重要性。其次,节点在一个子网络中的重要性能够放大节点的能力,并从另一子网络中指向它的节点的重要性中获益。例如,在YouTube社交网络中,网络数据集包含朋友、订阅和视频3个子维度的网络。如果2个用户在朋友子网络中是朋友,他们很有可能在订阅子网络中也存在订阅关系,即如果一个用户在朋友子网络中是中心节点,其影响力大,则该用户在订阅子网络中也有可能是核心传播用户。因此,如何充分挖掘不同子网络之间的隐含关联,并定义多元PageRank得分是设计多元网络链接预测算法的核心。

针对上述问题,本文基于一个子网络中节点的中心性可能受到另一个子网络中同一节点的中心性的影响这一特点,提出一种融合多元影响力节点指标的链接预测算法。为简便起见,本文首先将多元网络分为子网络A和子网络B。定义Aij和Bij分别是子网络A和子网络B的邻接矩阵,并通过式(1)计算子网络A所有节点在参数αA>0时的PageRank值pr={x1,x2,…,xN}。然后根据该值将多元PageRank中心性[20],即X={X1,X2,…,XN}赋值给子网络B的各节点。因此,节点i的MPR得分如下:

(3)

1)式(3)的第1部分表示节点i的中心性贡献,它来自子网络B中指向节点i的节点的中心性。与单维度PageRank度量相同,该贡献与节点i的邻居出入度成反比。不同于PageRank,式(3)使得该贡献得分受到子网络B中的节点i及其邻居在子网络A中的中心性影响。两个网络之间的相互作用对节点的中心性具有双重影响。首先,随着子网络A中节点i的中心性变大,其可以从子网络B中邻居的中心性获得某些优势,并使其自身的中心性变大。其在一个子网络中中心性越大,节点就越有可能吸引另一子网络中的其他重要节点,提高相似性得分。其次,每个邻接节点j对子网络B中节点i的中心性贡献,通过将节点j的中心性除以子网络B中节点j的邻居在子网络A中的中心性总和得到。换句话说,节点i的相似度得分来源于子网络B中任何邻接节点j的中心性,且该中心性被稀释到与子网络A中的高中心性相关联的许多其他节点中。综上所述,一个子网络中的重要节点可以吸引不同子网络中的重要节点,但是如果存在许多具有相似吸引能力的其他节点,则会削弱其优势。

2)式(3)中的第2部分反映了子网络B中节点i的中心性贡献,它来源于子网络A中节点i的中心性。这一部分内容可以使那些不能吸引子网络B中重要邻接节点的节点通过在子网络A中的重要性获得优势。在极端情况下,如果节点在子网络A中具有非零中心性,则子网络B中具有零度数的节点仍然可以与非零中心性值相关联。该中心性组成部分的假设是不管节点吸引前一子网络中其他重要节点的能力如何,其重要性受到同一节点在另一子网络中的重要性的正面影响。

根据式(3)中的参数变化,本文给出以下2个极限情况下的MPR指标:

1)MPR(β=1,γ=0)

(4)

2)MPR(β=1,γ=1)

(5)

(6)

(7)

通过上述步骤可获得每一个节点在各个维度子网络中的多元影响力得分。对于第维度子网络中的任意2个节点u和v,其基于MPR的相似度得分如下:

(8)

5 实验结果与分析

5.1 实验设置

根据第2节的问题定义,本文把比例r设置为90%,然后对Gα进行10次划分并取平均值。本文选用Precision作为评价度量。Precision表示如果给定候选的预测链接数目为N,且在其预测结果中有M个正确或者存在(即M条边属于集合E),则Precision=M/N。该指标主要侧重于衡量相似度排序前N个结果的命中比率。在实验中,Precision有时称为Prec或者Prec@N。

5.2 数据集

本文实验采用以下2个数据集:

1)Student数据集[10]。利用本-古里安大学的计算机与网络安全课程收集的数据,构建学生合作社交网络。这个社交网络包含来自2个部门的185名学生的数据。课程的社交网络通过分析学生在做家庭作业时的内隐合作关系和外显合作关系而建立。学生合作图包含185个节点、360个链接和3种链接类型。

2)QueryLog数据集[21]。这是一个共同查询的网络,其节点表示查询术语(字段),如果2个节点在同一查询中同时使用,则它们之间存在链接。该数据集共有6个维度,每个维度表示用户从查询结果中单击的排名,具体关系如下:排名(维度)1 → 1,排名2～3 → 2,排名4～6 → 3,排名7～10 → 4,排名11～58 → 5,排名59～500 → 6。为了简化操作,本文实验取前3个维度开展。

上述2个数据集的具体信息如表1所示。

表1 多元网络结构属性Table 1 Structure attributes of multiplex network

5.3 对比方法

实验采用基于以下3类指标的链接预测算法与本文基于2种MPR指标的算法进行对比:

1)单维度局部或者半全局指标,主要包括基于聚类系数的预测算法Cluster Coefficient Link Prediction(CC)[22]、基于共邻节点影响的朴素贝叶斯链接预测算法Local Naïve Bayes based on Common Neighbors(LNBCN)[23]和基于局部随机游走的预测算法Local Random Walk(LRW)[24]。

2)多源局部指标[12],主要包括基于边维度链接度的预测算法Edge Dimension Connectivity(EDC)和基于平均度关联的预测算法Average Node Correlation(ANC)。

3)影响力节点指标,本文选用单维度的节点影响力算法PageRank(PR)进行对比。

5.4 实验结果

表2给出在不同训练集规模下(r=0.7、0.8、0.9),各种算法在2个真实多元数据集中的预测效果,最优结果加粗表示。可以看出,最优结果基本都出现在MPR算法中。例如,在r=0.9时,与CC、LNBCN、EDC和ANC算法相比,MPR算法在Student数据集上的Precision值分别提高106.592%、69.033%、69.033%和69.033%,在QueryLog数据集上分别提高17.965%、16.758%、13.978%和14.329%。上述结果表明,MPR算法对于多元网络链接预测的效果更好。同时,在该规模训练集下,MPR算法在两个数据集上的Precision值比PR算法分别提高37.728%和16.575%,表明本文算法充分考虑了多个维度子网络之间的关联,能够有效地把单维度的PR拓展到多元网络的应用场景。同时,从表2可以看出,部分指标(尤其是LRW算法)在Student数据集上没有效果,部分算法(例如EDC和ANC)效果一致。这是因为该数据集过于稀疏,共邻节点过少,节点之间的链接不能实现随机游走和形成局部三角形结构。例如,在Student的各个维度中,平均有95%以上的节点对没有共邻节点,因此,LRW算法、EDC算法和ANC算法的预测效果不理想。然而,MPR算法能保持最优性能,表明该算法具备在网络非常稀疏的情况下进行预测的能力。随着训练集规模不断下降,各种算法的预测效果逐渐提高,这是因为候选的集合变少,使得精确度的判断更加容易。值得注意的是,在不同的训练集规模下,MPR算法均取得最优结果,进一步证明了该算法的稳定性和鲁棒性。

表2 在多元网络3个维度下的预测性能Table 2 Prediction performance in three dimensions of the multivariate network

5.5 结果分析

Precision指标是对潜在预测节点对的相似度评分,然后进行排序并取前TopN个潜在节点对,判断链接是否存在并考虑命中率。在本文实验中,取不同的N值,输出结果也会存在区别。需要注意的是,由于对比算法太多,图4仅给出QueryLog数据集上每一类算法的最优指标。同时,由于Student数据集上的预测效果差别较大,且部分指标没有Precision值,曲线图不清晰,因此通过表3给出不同N值下的预测效果。从图4和表3可以看出,TopN值越大,对应的预测准确率越高。由图4可知,MPR算法的准确率在每一个TopN步长上几乎都高于对比算法。由表3可知,无论TopN的值如何变化,最优的结果基本都出现在MPR算法中。上述结果均表明,本文算法的整体性能优于其他对比算法。此外,MPR算法在网络结构稀疏、缺乏共邻节点结构的情况下,其优势更明显。例如,对于Student数据集的Time子网络,其聚类系数只有0.012 8,链接数目只有23,潜在节点对的共邻节点非常少,且很多共邻节点是孤立的。在这种情况下,不能发挥基于共邻节点结构指标的优势,因此对应算法的预测准确率不理想,而MPR算法的预测性能是对比算法的近10倍,原因在于MPR算法把共邻节点的贡献定义为该节点在整个网络全局的排序得分,该得分不受制于网络的稀疏性,因此可以获得较优的预测性能。

图4 QueryLog数据集中各维度的Top N预测性能Fig.4 Top N prediction performance in each dimension on the QueryLog dataset

表3 Student数据集中各维度的Top N预测效果Table 3 Top N prediction performance in each dimension on the Student dataset

为揭示基于多元网络的MPR算法和基于同构网络的PR算法的敏感性和特异性关系,同时验证MPR算法的优越性,图5给出MPR算法和PR算法在QueryLog数据集的3个维度子网络上的接受者工作特性(Receiver Operating Characteristic Curve,ROC)曲线。ROC曲线以敏感性(真正率)为纵坐标、特异性(假正率)为横坐标,曲线下面积越大表明预测性能越好。由图5可以看出,尽管2条曲线比较接近,但是MPR算法始终优于PR算法,该结果表明,在多元网络结构下从PR算法拓展到MPR算法是合理的。

图5 QueryLog数据集各维度的ROC曲线Fig.5 ROC curves in each dimension of QueryLog dataset

为验证本文算法的可扩展性和稳定性,对QueryLog数据集进行不同规模的采样,并输出节点数目在2 500、3 000、3 500和4 000时不同算法的性能对比,如图6所示。其中,Best-Baseline表示除MPR算法和PR算法外,效果最优的对比算法。从图6结果可以看出,在Bin2、Bin3子网络的全部节点规模和Bin1子网络的3 000、3 500节点规模下,MPR算法的预测结果最优。上述结果表明,从整体上看,本文算法独立于数据规模,即对数据规模的变化不敏感,是可扩展的。同时,随着采样规模的增大,各子网络中MPR算法的性能表现比较稳定,不是线性变化的,从而证明本文默认节点规模2 000能够反映算法的性能。

图6 QueryLog数据集中不同采样规模下的性能对比Fig.6 Performance comparison at different sampling sizes on the QueryLog dataset

6 结束语

多元网络链接预测对于真实应用场景下的知识图谱关系推断、社交网络朋友推荐等具有重要的应用价值。本文提出一种基于多元影响力节点识别指标MPR的链接预测算法。给出多维度节点影响力排序指标的定义和计算方法,通过该指标为每个节点定义多元排名函数并给出量化节点重要性的评分。在此基础上,将全局得分融入基于共邻节点的相似度计算框架中,得到链接预测结果。实验结果表明,该算法的预测准确率高于PR、EDC、ANC等对比算法。下一步将把其他节点影响力鉴定指标纳入到多元网络链接预测算法中,并在超大规模的多元网络中进行实验,验证本文算法的可扩展性。