端点活跃度对链接预测的影响研究
2019-06-06杨凯凯钱宇华马国帅
杨凯凯,钱宇华,马国帅,艾 科
(山西大学 大数据科学与产业研究院,太原 030006) (山西大学 计算智能与中文信息处理教育部重点实验室,太原 030006) (山西大学 计算机与信息技术学院,太原 030006)
1 引 言
现实生活中,许多复杂系统都可以建模成复杂网络进行分析,复杂网络的重要节点和链接的挖掘[1]、社区发现[2]、链路预测[3]等研究得到了越来越多的国内外研究学者的关注.链路预测(Link Prediction)[4]旨在通过已知的网络结构信息和节点属性信息预测网络中尚未产生链接的两个节点之间是否可能产生链接,主要用于还原缺失信息和预测未知信息,在社交网络推荐[5]、生物信息分析[6]、交通网络设计等领域具有巨大的实际应用价值.
基于相似性的链路预测的基本假设是:两个节点之间的相似性越大,它们之间存在链接的可能性就越大.本文将两个目标节点称为端点,以区分邻居节点、路径中间节点等其他节点.研究学者从两个角度刻画端点间的相似性:一种是基于网络的拓扑结构信息[7],根据端点间的连接关系进行预测;另一种是基于网络节点的真实属性信息[3],结合机器学习[8]的方法进行链接的预测.但是由于节点属性信息不易获取且常伴随着大量噪音,相比而言,网络的结构信息容易获取且比较可靠;同时基于拓扑结构的预测方法对于结构相似的网络具有普适性.因此,本文主要研究基于网络拓扑结构的链路预测算法,它主要分为三类相似性指标,一种是共同邻居指标CN[9],通过节点间共同邻居的个数来估计节点之间的相似性,随后研究者又从不同的角度对其进行改进[10].第二种是基于路径的相似性指标,如LP指标[11]、Katz指标[12],它们认为两端点间可以通信的路径条数越多、长度越短,其产生链接的可能性越大.第三种是基于随机游走的相似性指标:RWR指标[12],SRW指标[14].
现有的链路预测指标仅考虑两端点间的连接关系,忽略了端点自身活跃性对链接产生的不同影响.例如在社交网络中名人更容易交到更多的朋友;交通网络中新线路多是与枢纽节点相连;万维网中,网页中的新链接多是指向权威网站,由此可见往往越是活跃的端点,其产生链接的可能性更大.本文从度中心性[15]、介数中心性[16]、接近中心性[17]、Pagerank[13]四个角度刻画端点的活跃度,研究不同的端点活跃度对链接产生的不同影响.通过大量的实证分析发现,端点的活跃度越强,其产生链接的可能性越大,其中又以度中心性,Pagerank表现更为显著.因此,本文在基于端点间连接关系的基础上考虑端点自身活跃程度,提出了一类基于端点活跃度的链路预测方法,并在8个真实网络数据上进行实验,预测精度比原有的指标有较大的提高.
本文其它章节内容安排如下:第二节中介绍了四种刻画端点活跃度的方法;链路预测实验设计方法;几种经典的链路预测指标和本文中用到的8个真实数据.第三节分析讨论了端点活跃性对链接产生的影响.第四节介绍了利用端点活跃度对传统链路预测指标进行改进,并比较原有指标和改进后的指标的预测精度.第五节对本研究的总结与展望.
2 相关工作
2.1 节点中心性
网络中端点的活跃度越大,其可能更容易产生新的链接.本文从度中心性[15]、介数中心性[16]、接近中心性[17]、Pagerank[13]四个角度刻画端点的活跃度.
1)度中心性(Degree Centrality,DC)[15]
度中心性通过端点可直接交互的邻居数量来刻画端点的活跃度,其定义为:
(1)
其中ki为节点的度值,N为网络节点个数.
2)介数中心性(Betweeness Centrality,BC)[16]
网络中经过某端点传递信息的路径越多,它就越活跃,这就是介数中心性,其定义为:
(2)
3)接近中心性(Closeness Centrality,CC)[17]
接近中心性表明了端点与其他节点交互的便利程度,该端点到其他节点的平均路径越短,它就越活跃.其定义为:
(3)
其中,dij表示节点i到节点j的距离.
4)Pagerank(PR)[13]
端点能交互的节点越多,这些节点越重要,该节点就越活跃,这种活跃度称为Pagerank,其定义为:
(4)
2.2 链路预测
定义G(V,E)为一个无向网络,其中V为节点集合,E为边集合.网络总的节点数为N,边数为M.此网络共有N(N-1)/2个节点对,即全集U.将已知的链接E分为两部分,训练集ET和测试集EP.在训练集中计算节点对的相似性,在测试集中,通过AUC来衡量链路预测算法精确度.AUC 可以理解为在测试集中的边的分数值比随机选择的一个不存在的边的分数值高的概率,其大于0.5的程度衡量了算法在多大程度上比随机选择的方法精确.
基于网络拓扑结构的链路预测方法主要分为三类:共同邻居方法,基于路径的方法,和基于随机游走的方法.下面分别介绍这几种方法的代表性指标.
1)共同邻居(CN)[9]
对于网络中的节点x,定义其邻居集合为Γ(x),则两个节点x和y的相似性定义为他们共同邻居数(CN),即:
(5)
CN指标只考虑共同邻居的个数,后来,陈嘉颖[18]等人考虑共同邻居节点的重要性提出了CN-DC,CN-BC,CN-CC,CN-PR等方法,其定义为:
(6)
其中Cz表示节点z不同的中心性指标(DC,BC,CC,PR).
2)局部路径指标(LP)[11]
LP指标是一种基于路径的局部性指标,该指标只考虑二阶路径和三阶路径对链接产生的影响.其定义为:
(7)
其中α为可调参数,A为邻接矩阵,A2,A3分别表示节点x与节点y之间长度为2,3的路径数目.
3)全局路径指标(Katz)[12]
Katz指数是一种基于所有路径的全局性指标,定义为:
(8)
其中,β>0为控制路径权重的可调参数.
4)有重启的全局随机游走指标(RWR)[12]
RWR指标是一种基于全局信息的随机游走指标,它假设随机游走粒子在每走一步的时候都以一定的概率返回初始位置.若某一粒子初始时刻在节点x处,那么时刻该粒子到达网络各个节点的概率向量为:
(9)
(10)
5)局部随机游走指标(SRW)[14]
基于全局的随机游走指标计算复杂度比较高,刘伟平和吕琳媛提出有叠加效应的局部随机游走的相似性指标SRW.一个粒子t时刻从节点x出发,定义为t+1时刻这个粒子正好走到节点y的概率:
πx(t+1)=PTπx(t),t≥0
(11)
(12)
将t步及其以前的结果加总便得到的值,即:
(13)
2.3 数据集
本文采用了8个真实的网络数据,涉及社会网络、生物网络和技术网络等领域. 在表1中罗列出刻画网络特征常用的7个统计量符号及其含义,表2中将8个真实网络的7个统计量值呈现出来.
表1 统计符号及含义
Table 1 Statistical symbols and meaning
符号含 义符号含 义N网络的节点数M网络的边数
表2 8个真实网络的统计量
Table 2 Statistical measure of eight real networks
网络NM
3 端点活跃度对链接的影响
以上介绍的各项基于网络拓扑结构的链路预测指标仅考虑两端点间的连接关系,忽略了端点活跃度对链接的不同影响,往往端点越活跃,其更容易产生新的链接.本文为研究端点活跃度对链接的影响进行了三项分析:
1.活跃度对链接的影响分析:计算不同活跃值下,端点平均产生链接的条数.
2.不同活跃度对链接的影响程度分析:计算基于链接的活跃度均值与端点的活跃度均值的大小关系,以及其在活跃度分布中的位置.
3.活跃度对链接的影响验证:假设端点间产生链接的概率只与端点活跃度成正比,进行链路预测,验证不同活跃度对链接的不同影响.
通过上述方法研究在不同活跃度下,端点对链接产生的不同影响.图1是分析过程.
3.1 活跃度对链接的影响分析
本文从度中心性DC、介数中心性BC、接近中心性CC、Pagerank(PR)四个角度来刻画端点的活跃程度,计算基于不同中心性的活跃度下,端点产生链接的情况.图2展示了在8个真实网络中,不同活跃值下,端点平均产生链接的条数.图2中,横坐标表示不同的活跃值区间,即不同的活跃度c;纵坐端点活跃度对链接影响的分析过程
输入:网络G=(V,E),其中V和E分别表示G的节点集和边集.
输出:在基于不同中心性的活跃度下,端点对链接产生的不同影响.
过程:
1.将网络分为训练集和测试集,保证训练集的连通性.
2.在训练集中,计算网络的各种中心性指标(包含DC,BC,CC, PR)C={C1,C2,C3,…,Cn},其中(1,2,3,…,n)∈V.
3.在测试集中,计算活跃值为c的端点平均产生链接的条数:
4.计算基于链接的中心性均值与节点中心性差值的大小关系:
6.利用端点活跃度进行链路预测:sim(x,y)=CxCy.
7.分析不同活跃度对链接产生的不同影响.
图1 端点活跃度对链接影响的分析过程
Fig.1 Analysis method about the impact of endpoint
activity on links
标表示产生链接的条数R(c);柱状图中,灰色柱、黑色柱、白色柱、o型填充柱(从左到右)分别表示基于DC,BC,CC,PR的活跃值c下,端点平均产生链接的条数R(c).
图2 端点的活跃程度对链接的影响Fig.2 Impact of endpoint activity of on links
从图2中分析可得,在基于DC,BC,CC,PR的各种活跃性下,端点的活跃值较小时,其产生的链接也比较少,随着活跃值的增大,其产生链接的条数也在增多.因此可得:端点越活跃,其产生链接的条数越多.
3.2 不同活跃度对链接的影响程度分析
·当d< 0时,说明活跃端点之间并不会更容易产生链接.
表3 不同中心性下的d值
Table 3dbased different centralities
网络d(DC)d(BC)d(CC)d(PR)adjnoun1.0731-0.0603-0.06164.9458ucforum1.8691-0.1342 -0.022039.8743brain1.11400.31801.001414.5652router12.5038-0.4711-0.024042.3130foodweb 0.62480.14480.181015.0712 florida0.49890.00180.017912.3591karate0.4153-0.00840.34640.8566polblogs1.7513-0.17930.001136.6757
表3中,DC,PR的d值均为正值且较大,其中PR中心性表现尤为明显,而在BC,CC中心性中,d值的负值较多,且正值较小,由此可见节点的Pagerank中心性越大,产生链接的可能性越大,DC次之,CC,BC表现效果差,其中BC指标可能起相反的作用.
通过大量的实证分析得出:端点越活跃,其产生链接的可能性越大,其中DC和Pagerank大的端点可能更容易产生新的链接.
3.3 活跃度对链接的影响验证
根据上述结论,假设两个端点是否产生链接只与两个端点的活跃度有关,即端点产生新链接的概率正比于该端点的活跃值,定义相似性指标.
sim(x,y)=CxCy
(14)
来进行链路预测(其中Cx表示节点x的中心值).基于不同的活跃度产生不同的相似性指标,计算不同活跃性下的链接预测结果,如表5所示(括号中表示不同活跃度下预测算法的预测结果排序,黑体是预测效果最好的相似性指标).
网络pos(cl)(DC)pos(cl)(BC)pos(cl)(CC)pos(cl)(PR)adjnoun0.81230.47160.69240.6129ucforum0.96290.46380.69770.6499brain0.87100.87690.88540.8377router0.99680.46540.67450.9223foodweb 0.76510.62070.84480.6725florida0.72900.52130.72260.5572karate0.68760.63060.67740.6912polblogs0.88730.46120.76240.6960
表5 不同中心性下的预测结果AUC
Table 5 AUC based different centralities
数据DCBCCCPRadjnoun0.7620(1)0.7362(4)0.7446(3)0.7604(2)ucforum0.8578(1)0.8412(4)0.8469(3)0.8548(2)brain0.9784(2)0.8516(4)0.9783(3)0.9842(1)router0.9544(1)0.9206(3)0.6986(4)0.9429(2)foodweb 0.8324(2)0.8100(3)0.7981(4)0.8415(1)florida0.7311(1)0.6985(4)0.7281(2)0.7258(3)karate0.7365(2)0.6420(4)0.6937(3)0.7654(1)polblogs0.9101(1)0.8818(4)0.8830(3)0.9093(2)
从以上的验证分析中可以得出:在网络中,端点基于度中心性和Pagerank的活跃度越强,其产生链接的可能性更大,因此本文在基于端点间连接关系的基础上考虑端点的活跃度,提出一类基于端点活跃度的链路预测方法.
4 一类基于端点活跃度的链路预测方法
传统的链路预测算法仅仅考虑网络中两端点的连接关系,并未考虑端点自身活跃度对链接产生的影响,从第三节的实证分析中可以得出:在真实网络中,端点基于度中心性和Pagerank的活跃度越强,产生链接的可能性越大.因此,本文在基于两端点间连接关系的基础上考虑端点的活跃度,提出了一类基于端点活跃度(Endpoint Activity,EA)的链路预测方法:
EAsim(x,y)=CxCysim(x,y)
(15)
其中,Cx表示节点的中心值,sim(x,y)表示原有的相似性算法.本文选取了原始指标是共同邻居CN指标,局部路径指标LP、全局性指标Katz(分别取参数值0.01,0.001),全局性随机游走指标RWR(分别取参数值0.85,0.95)和局部性指标SRW(分别取参数值3,4,5).
实验结果如图3和图4所示:图中横坐标表示不同的链路预测指标;纵坐标表示AUC预测精度;在柱状图中,浅色柱代表原有指标的预测精度,灰色柱代表基于度中心性的端点活跃度预测指标,深灰色柱代表基于PageRank的端点活跃度预测指标.
图3 不同相似性指标下的AUC预测结果Fig.3 AUC results for different similarity indexes
从图3中可以看出考虑两个端点基于度中心性和Pagerank活跃度指标的预测精度比原指标有极大改进,其中在adjnoun,ucforum数据中改进效果明显,在brain,router数据中,在原有指标预测精度已经高达0.90以上后,活跃度指标仍能使预测精度有一定的提升.
图4 不同相似性指标下的AUC预测结果Fig.4 AUC results for different similarity indexes
在foodweb,florida数据中,除RWR指标外,对其他指标均有改进.在karate数据中,DC对原有指标的改进效果并不理想,PR中心性除RWR指标外,对其他指标均有改进.在polblog数据中,虽然对原有指标改进效果并不理想,但是可以通过改进得到预测效果最佳的新指标.
随后,本文在已经考虑了共同邻居的节点中心性指标的CN-DC,CN-PR的基础上增加考虑端点的活跃度,按照公式(15)形成新的链路预测指标EA_CNDC,EA_CNPR.
观察表6可得,除了polblogs数据外,其他数据的他预测精度均有提升,并且提升幅度较大.即便是在polblogs数据上,其预测精度与原有指标的预测进度相差无几.因此可以得出,增加考虑端点活跃度可以提高预测精度.
由上述实验可得,对原有链路预测指标加入端点基于度中心性和Pagerank中心性的活跃性后,其预测精度得到有效提升.因此在链路预测过程中考虑端点活跃度是一种有效的提升策略.
表6 不同相似性指标下的AUC预测结果
Table 6 AUC for different similarity indexes
数据CN-DCEA_CNDCCN-PREA_CNPRadjnoun0.68130.70140.69260.7007ucforum0.73810.74980.74590.7494brain0.73990.96040.79650.9615router0.65470.65520.65590.6563foodweb 0.75670.78840.76360.7803florida0.6080.65030.61870.6473karate0.70960.75130.70480.7542polblogs0.92280.92180.92380.9223
5 总结与展望
在基于网络拓扑结构的链路预测算法中,主要关注两端点之间的连接关系,忽略了端点的活跃度对链接的影响.本文选取了四种常用的节点中心性指标来刻画节点的活跃程度.通过实验分析可得端点越活跃,其产生链接的可能性也就越大,其中度中心性和Pagerank对链接产生的影响更为显著.基于此现象,本文将基于度中心性和Pagerank的端点活跃度增加到现有的指标中,提出了一类基于端点活跃性的链路预测方法,并在8个真实网络数据上进行实验,发现此类方法的预测精度比原有指标有较大的提高.
本文通过研究了四种不同的端点活跃度对链接产生的不同影响,未来将融合端点活跃度与具体的网络结构,根据实际情况有针对性地改进预测算法.另外,节点真实属性也是影响链路预测的重要因素,如何将节点的真实属性运用到链路预测中是未来研究的重点.
