《基于结构加权网络的链接预测-李婷.pdf》由会员分享，可在线阅读，更多相关《基于结构加权网络的链接预测-李婷.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2016年6月第34卷第3期西北工业大学学报Joumal of Northwestem Pol”echnical UniversityJune 2016V0134 No3基于结构加权网络的链接预测李婷1，张海12(1西北大学数学学院，陕西西安710127；2中国科学院数学与系统科学院应用数学所，北京100190)摘要：研究社会网络中边的链接预测问题，试图根据网络中边的结构权重信息，将无权网络转换为加权网络进行研究。进而，对于一些加权网络，重新考虑其权重，分别以真实权重、结构权重以及将两者结合后的值作为网络中边的权重，研究resource allocation along local path(
2、RALP)等指标、资源分配(RA)指标和局部路径(LP)指标在加权网络中的链接预测情况。实验结果表明，文中所提统计方法有着良好的预测效果，而且加权RALP指标的预测精度优于加权RA指标和加权LP指标。关键词：链接预测；结构权重；统计方法中图分类号：02121 文献标志码：A 文章编号：10002758(2016)03054404复杂系统通常都可以通过网络表示，其中节点表示系统中的个体或诸多对象，边则表示个体或对象问的关系之J。随着互联网的快速发展，形成了诸如Facebook、人人网、微博等社交网络，使得人与人之间的交流变得更加便利。因此，开展此类数据分析，提取网络特征是一项非常有意义的工作。网
3、络的社会分析也成为近年来统计学、计算机科学、物理学、社会科学等研究领域的一个热点，其中链接预测是网络分析中的一个基本问题。链接预测是指通过网络已知的连接边及节点属性或网络结构等信息，预测未连接边的2个节点之间产生连接的可能性。近年来，基于网络结构和节点属性的链接预测方法受到广泛关注圳，例如OMadadhain等1利用节点属性以及网络的拓扑结构信息，建立了一个局部条件概率模型并以此进行预测；Bai等o通过结合RA指标和LP指标提出了一个半局部相似性指标(即RALP指标)，实验得出该指标在网络的链接预测中优于RA和LP指标。链接预测的许多算法已被应用于很多真实的网络，但是这些学习算法很少考虑网络中
4、边的权重信息。Murata和Moriyasu1提出了共同邻居(CN)、AdamicAdar(AA)、偏好连接(PA)3个相似性指标及其加权形式，并将其应用于QuestionAnswerBulletin Boards system网络。结果显示，考虑权重信息提高了链接预测精度，但在共同作者网络和美国航空网络中加权指标预测结果反而比无权的差，即所谓的“弱连接”效应。zhou等o研究了CN、AA、RA指标以及其加权形式等在3个真实网络中的预测效果，验证了链接预测问题中存在的“弱连接”效应。进而，wang等o考虑了网络节点的邻域结构信息，提出了将网络中每条边的簇系数作为其权重的方法，研究了CN、AA、
5、RA、LP 4种相似性指标在8个真实网络中的链接预测情况，实验结果表明，当以边的簇系数作为权重时，可以有效提高加权网络的链接预测精度。一个很自然的问题是，能否将RALP指标应用于考虑结构权重或者同时考虑结构权重和真实权重信息时的网络链接预测情况呢?本文中，我们将考虑网络的结构权重信息，研究RALP等指标在这些真实网络中的链接预测效果。通过研究，我们发现无论是无权网络还是加权网络，当其考虑结构权重信息时对于RALP、RA和LP指标都能有效提高网络的链接预测效果，同时RALP指标的预测结果优于RA指标和LP指标。基于加权网络的模型我们考虑简单无向网络G(y，E)，其中y表示收稿日期：2015102
6、7 基金项目：国家自然科学基金(11571011)资助作者简介：李婷(199卜)，女，西北大学硕士研究生，主要从事机器学习研究。万方数据第3期 李婷，等：基于结构加权网络的链接预测节点集，E表示边集合，并且忽略节点间多边信息和同一节点自连接信息。对于每一对节点戈，)，矿，根据文中所提相似性指标计算数值s。其中S。，表示2个节点戈和y间的相似性，值越高表示两节点越相似。1)资源分配(RA)指标：zhou等叫提出了资源分配指标，其定义为s玎甜。蚤几，高 (1)；EJr(j)nJr(r)几、o，式中，后(z)表示节点z的度，厂(戈)表示节点z的邻居。2)局部路径(LP)指标：zhou等10川提出基于
7、局部路径的相似性指标。其定义为5，=(A2)：，+占(A3)， (2)式中，(A2)，表示节点戈和节点y之间长度为2的路径数目，(A3)。，表示节点z和节点y之间长度为3的路径数目，占=0001为可调参数。3)沿局部路径的资源分配(RALP)指标：Bai等61提出了将资源分配过程结合到局部路径中得到了一个新的指标。其定义为sV甜。再m，高乏，一而妨。)式中，f。一表示从节点x到节点y的长度为3的路径，i和_是路径Z，一中的2个节点。上述3个相似性指标都是基于无权网络定义的，然而在真实世界中，网络中的边通常都含有权重信息。因此当考虑权重信息时，上述3个相似性指标的加权形式可定义如下：1)加权RA
8、(wRA)指标：s=等导 (4)式中，甜。表示2个节点z和。之间边的权重，且伽。=叫。，s()=埘。为节点。的度。2)加权LP(wLP)指标：IS吖= (埘。+埘叫)+：E厂(#)n厂(y)s(埘，。+埘i)(埘g+) (5)(iJ)Efp“3)加权RALP(wRALP)指标：s矿甜赢，孚+ ：Er(z)n J(y) Jz，(6)本文结合RALP、RA和LP 3个加权相似性指标与结构权重信息，推广了zhou等伸。和Bai等Mo的工作，分别对4个无权网络和3个加权网络进行了研究。由于在真实世界中，一些网络中的边是不含权重信息的，所以为了研究和提高无权网络的链接预测精度，以结构权重作为网络中边的权
9、重，研究RALP、RA和LP 3个指标的链接预测问题。同时为了比较，也研究了无权网络在不考虑结构权重信息时的链接预测情况。其中结构权重(主要研究边的簇系数)。9 o表示真实网络中边存在的概率，其定义为：旷=嘉 式中，ii表示共同邻居的个数。当然，有些网络中的边是含有权重信息的。所以，为了研究和提高这些加权网络的链接预测效果，我们分别以网络的真实权重、结构权重、两者结合后的值作为边的权重，研究RALP、RA、LP 3个指标的预测情况。其中分别采用3种方式结合真实权重和结构权重：平均值法、最小值法、最大值法。2 实 验由于研究的是无向网络，所以相似性数值是对称的，即s。，=S，：。将所有未连接的边
10、根据它们的数值按降序排列，排在最前面的是最可能存在的边。对于网络，我们随机抽取观测边E的80作为训练集E，剩下的20作为测试集E，用于检验算法的有效性。显然，E：E，u E，且E，n E，=中。衡量链接预测算法精确度的指标包括AUC、精确度和排序分，这里我们利用Auc来衡量链接预测算法的精确度。在大样本情况下，可以采用抽样的方法得到近似值。事实上，Auc可以理解为在测试集中随机选择一条边的分数值比随机选择的一条不存在的边的分数值高的概率。在实验中，独立比较n次，如果有n 7次测试集中的边分数大于不存在的边分数，有凡”次分数值相等。那么AUC可定义为：AUC=n+n气n，二竺。如果分数都是随机产
11、生的，可取AucnO5。可见，AuC大于05的程度衡量了算法在多大程度上比随机选择的方法精确。选用UCI数据库中来自不同领域的7个网络，并忽略网络中边的方向。其中这7个网络分别为：产加一U羔，堕_川J占万方数据546 西北工业大学学报 第34卷空手道俱乐部、海豚社会网络、美国大学橄榄球、美国政治书籍网络、线虫的神经网络、孤星泪网络小说中的人物共性网络、国航空网络。研究了无权网络和加权网络。实验1中将网络结构权重作为无权网络的权重，作为比较，同时也研究在其不考虑结构权重信息时的链接预测能力，结果如表1所示。表l 4个无权网络在考虑结构权重时的链接预测结果比较表2 3个加权网络在考虑结构权重时的链
12、接预测结果比较参考文献：在实验2中，分别以网络的真实权重、结构权重、两者结合后的值作为边的权重，结果如表2所示。通过比较，发现以结构权重作为网络边的权重时，提高了网络的链接预测精度，且实验2中同时考虑结构权重和真实权重(尤其是取两者中最小值)时也提高了网络的链接预测效果，而且RALP指标的预测精度比RA指标和LP指标的高。其中，每个数值都是将数据随机独立分成训练集和测试集进行10次实验平均得到的，占=0001。“无权”、“结构权重”、“真实权重”、“最小值权重”分别表示不含权重时、以结构权重作为边的权重时、以网络本身含有的权重、取真实权重和结构权重两者中最小的值作为网络中边的权重时的链接预测。
13、3 结 论本文中，我们根据网络的结构权重(边的簇系数)，研究了3个相似性指标在7个真实网络中的链接预测情况。研究发现，当网络中考虑结构权重信息时，可有效提高网络的链接预测效果，而且RALP指标的预测精度优于RA和LP指标。当加权网络中同时考虑结构权重和真实权重(尤其是取两者中最小值)时也改善了网络的链接预测效果。从实验结果可知：结构权重在提高网络的链接预测过程中起了很重要的作用；而且加权RALP指标的预测效果也得到改善。1 Boccaletti s，L置tora V，Moreno Y，et a1complex Networks：stmcture and DynamicsJPhysics Rep
14、ons，2006，424(4)：1753082 costa L F，Rodrigues F A，7rravieso G，et a1chamcterization of complex Networks：A sunrey of MeasurementsJAdvancesin Physics，2007，56(1)：1672423 吕琳嫒复杂网路链接预测J电子科技大学学报，2010，39(5)：651661Ln LinyuaJlLink Prediction in Complex NetworksJJoumal of university of Electronic science and Tech
15、nolog)r，2010，39(5)：651-661(in Chinese)4 Ln L，zhou T“nk Prediction in Complex Networks：a surveyJPhysical A：statistical Machanics and Its Applications，20ll，290(6)：115011705 0 7Madadhain J，Hutchins J，smyth PPrediction and Ranking Algorithms for EventBased Network DataCPmceedings ofACM SIGKDD，2005：2330万
16、方数据第3期 李婷，等：基于结构加权网络的链接预测 5476 Bai M，Hu K，Tang YLink Prediction Based on a semiLocal Similaty IndexJChinese Physics B，2011，20(12)：1289027 Murata T，Moriyasu sLink Prediction of social Network Based on weighted Proximity MeasuresCProceeding IEEEwICACM Intemational Conference on Web Inteuigence，20078 L
17、n L，zhou TLink Prediction in weigllted Networks：，I11e Role of weak TiesJEurophysics Letters，2010，89(1)：1800l9 wang L，Hu K，Tang YRobustness of LjnkPrediction A190rithm Based on similarity and Application to Biolo百cal NetworksJcu兀nt Bioinf0册atics，2014，9(5)：1710zhou T，L，zhang Y cPredicting Missing“nks
18、Via kal I山珊ationJThe EumPeaIl PhysicaJ Jounlal B-condensedMatter and Complex System，2009，7l(4)：6236301 1Lii L，Jin C H，zhou Tsimilarity lndex Based on Local Paths fbr Link Prediction of Complex NetworksJPhysical ReviewE2009，80(4)：046122Link Prediction in Structure WeightBased NetworksLi Tin91，Zhang H
19、ail，2，1School of Matllematics，Northwest university，xian 710127，China 、2Institute of Applied Mathematics，Academy of Mathematics and system sciences，iL chinese Academy of sciences，Beijing l00190，china Abstract：In this paper，we try to study the link prediction problem of social network byeating the stl
20、llcture info卜mation as a transfo肿function and transfonTling un-weighted network to weighted oneFunher，for some weightednetworks，we rethink their weights，and consider the real weights、stIucture weights as welI as the combination ofthese two values as the weight of these networks respectiVely and stud
21、y the link prediction problem of resource aUo-ca“on along 10cal path、resource allocation index and 10cal path index in weighted networl(sThe experiments showthat statistical method in stnJcture weightbased networks has a well prediction efkctSimultaneously， weightedRALP also perfo咖s better than both the weighted RA and weighted LPKeywords：link prediction；stllJcture weight；statistical method万方数据