基于结构加权网络的链接预测

李婷, 张海,2

(1.西北大学 数学学院, 陕西 西安　710127；2.中国科学院 数学与系统科学院应用数学所, 北京　100190)



基于结构加权网络的链接预测

李婷1, 张海1,2

(1.西北大学 数学学院, 陕西 西安710127；2.中国科学院 数学与系统科学院应用数学所, 北京100190)

摘要：研究社会网络中边的链接预测问题，试图根据网络中边的结构权重信息，将无权网络转换为加权网络进行研究。进而，对于一些加权网络，重新考虑其权重，分别以真实权重、结构权重以及将两者结合后的值作为网络中边的权重，研究resource allocation along local path(RALP)等指标、资源分配(RA)指标和局部路径(LP)指标在加权网络中的链接预测情况。实验结果表明，文中所提统计方法有着良好的预测效果，而且加权RALP指标的预测精度优于加权RA指标和加权LP指标。

关键词：链接预测；结构权重；统计方法

复杂系统通常都可以通过网络表示，其中节点表示系统中的个体或诸多对象，边则表示个体或对象间的关系[1-2]。随着互联网的快速发展，形成了诸如Facebook、人人网、微博等社交网络，使得人与人之间的交流变得更加便利。因此，开展此类数据分析，提取网络特征是一项非常有意义的工作。网络的社会分析也成为近年来统计学、计算机科学、物理学、社会科学等研究领域的一个热点，其中链接预测是网络分析中的一个基本问题。

链接预测是指通过网络已知的连接边及节点属性或网络结构等信息，预测未连接边的2个节点之间产生连接的可能性。近年来，基于网络结构和节点属性的链接预测方法受到广泛关注[3-4]，例如O′Madadhain等[5]利用节点属性以及网络的拓扑结构信息，建立了一个局部条件概率模型并以此进行预测；Bai等[6]通过结合RA指标和LP指标提出了一个半局部相似性指标(即RALP指标)，实验得出该指标在网络的链接预测中优于RA和LP指标。

链接预测的许多算法已被应用于很多真实的网络，但是这些学习算法很少考虑网络中边的权重信息。Murata和Moriyasu[7]提出了共同邻居(CN)、Adamic-Adar(AA)、偏好连接(PA)3个相似性指标及其加权形式，并将其应用于Question-AnswerBulletinBoardsSystem网络。结果显示，考虑权重信息提高了链接预测精度，但在共同作者网络和美国航空网络中加权指标预测结果反而比无权的差，即所谓的“弱连接”效应。Zhou等[8]研究了CN、AA、RA指标以及其加权形式等在3个真实网络中的预测效果，验证了链接预测问题中存在的“弱连接”效应。进而，Wang等[9]考虑了网络节点的邻域结构信息，提出了将网络中每条边的簇系数作为其权重的方法，研究了CN、AA、RA、LP4种相似性指标在8个真实网络中的链接预测情况，实验结果表明，当以边的簇系数作为权重时，可以有效提高加权网络的链接预测精度。一个很自然的问题是，能否将RALP指标应用于考虑结构权重或者同时考虑结构权重和真实权重信息时的网络链接预测情况呢？

本文中，我们将考虑网络的结构权重信息，研究RALP等指标在这些真实网络中的链接预测效果。通过研究，我们发现无论是无权网络还是加权网络，当其考虑结构权重信息时对于RALP、RA和LP指标都能有效提高网络的链接预测效果，同时RALP指标的预测结果优于RA指标和LP指标。

1基于加权网络的模型

我们考虑简单无向网络G(V,E)，其中V表示节点集，E表示边集合，并且忽略节点间多边信息和同一节点自连接信息。对于每一对节点x,y∈V，根据文中所提相似性指标计算数值Sxy，其中Sxy表示2个节点x和y间的相似性，值越高表示两节点越相似。

1)资源分配(RA)指标：Zhou等[10]提出了资源分配指标,其定义为

(1)

式中，k(z)表示节点z的度，Γ(x)表示节点x的邻居。

2)局部路径(LP)指标：Zhou等[10-11]提出基于局部路径的相似性指标。其定义为

(2)

式中，(A2)xy表示节点x和节点y之间长度为2的路径数目，(A3)xy表示节点x和节点y之间长度为3的路径数目，ε=0.001为可调参数。

3)沿局部路径的资源分配(RALP)指标：Bai等[6]提出了将资源分配过程结合到局部路径中得到了一个新的指标。其定义为

(3)

式中，lx→y表示从节点x到节点y的长度为3的路径，i和j是路径lx→y中的2个节点。

上述3个相似性指标都是基于无权网络定义的，然而在真实世界中，网络中的边通常都含有权重信息。因此当考虑权重信息时，上述3个相似性指标的加权形式可定义如下：

1)加权RA(WRA)指标：

(4)

2)加权LP(WLP)指标：

(5)

3)加权RALP(WRALP)指标：

(6)

本文结合RALP、RA和LP3个加权相似性指标与结构权重信息，推广了Zhou等[8]和Bai等[6]的工作，分别对4个无权网络和3个加权网络进行了研究。由于在真实世界中，一些网络中的边是不含权重信息的，所以为了研究和提高无权网络的链接预测精度，以结构权重作为网络中边的权重，研究RALP、RA和LP3个指标的链接预测问题。同时为了比较，也研究了无权网络在不考虑结构权重信息时的链接预测情况。其中结构权重(主要研究边的簇系数)[9]表示真实网络中边存在的概率，其定义为：

(7)

式中，Nij表示共同邻居的个数。

当然，有些网络中的边是含有权重信息的。所以，为了研究和提高这些加权网络的链接预测效果，我们分别以网络的真实权重、结构权重、两者结合后的值作为边的权重，研究RALP、RA、LP3个指标的预测情况。其中分别采用3种方式结合真实权重和结构权重：平均值法、最小值法、最大值法。

2实验

选用UCI数据库中来自不同领域的7个网络，并忽略网络中边的方向。其中这7个网络分别为：空手道俱乐部、海豚社会网络、美国大学橄榄球、美国政治书籍网络、线虫的神经网络、孤星泪网络小说中的人物共性网络、国航空网络。

研究了无权网络和加权网络。实验1中将网络结构权重作为无权网络的权重，作为比较，同时也研究在其不考虑结构权重信息时的链接预测能力，结果如表1所示。

表1　4个无权网络在考虑结构权重时的链接预测结果比较

表2　3个加权网络在考虑结构权重时的链接预测结果比较

在实验2中，分别以网络的真实权重、结构权重、两者结合后的值作为边的权重，结果如表2所示。

通过比较，发现以结构权重作为网络边的权重时，提高了网络的链接预测精度，且实验2中同时考虑结构权重和真实权重(尤其是取两者中最小值)时也提高了网络的链接预测效果，而且RALP指标的预测精度比RA指标和LP指标的高。

其中，每个数值都是将数据随机独立分成训练集和测试集进行10次实验平均得到的，ε=0.001。“无权”、“结构权重”、“真实权重”、“最小值权重”分别表示不含权重时、以结构权重作为边的权重时、以网络本身含有的权重、取真实权重和结构权重两者中最小的值作为网络中边的权重时的链接预测。

3结论

本文中，我们根据网络的结构权重(边的簇系数)，研究了3个相似性指标在7个真实网络中的链接预测情况。研究发现，当网络中考虑结构权重信息时，可有效提高网络的链接预测效果，而且RALP指标的预测精度优于RA和LP指标。当加权网络中同时考虑结构权重和真实权重(尤其是取两者中最小值)时也改善了网络的链接预测效果。从实验结果可知：结构权重在提高网络的链接预测过程中起了很重要的作用；而且加权RALP指标的预测效果也得到改善。

参考文献：

[1]BoccalettiS,LatoraV,MorenoY,etal.ComplexNetworks:StructureandDynamics[J].PhysicsReports, 2006, 424(4): 175-308

[2]CostaLF,RodriguesFA,TraviesoG,etal.CharacterizationofComplexNetworks:ASurveyofMeasurements[J].AdvancesinPhysics, 2007, 56(1): 167-242

[3]吕琳媛. 复杂网路链接预测[J]. 电子科技大学学报，2010, 39(5): 651-661

LüLinyuan.LinkPredictioninComplexNetworks[J].JournalofUniversityofElectronicScienceandTechnology, 2010, 39(5): 651-661 (inChinese)

[4]LüL,ZhouT.LinkPredictioninComplexNetworks:aSurvey[J].PhysicalA:StatisticalMachanicsandItsApplications, 2011, 290(6): 1150-1170

[5]O′MadadhainJ,HutchinsJ,SmythP.PredictionandRankingAlgorithmsforEvent-BasedNetworkData[C]∥ProceedingsofACMSIGKDD, 2005: 23-30

[6]BaiM,HuK,TangY.LinkPredictionBasedonaSemi-LocalSimilarityIndex[J].ChinesePhysicsB, 2011, 20(12): 128902

[7]MurataT,MoriyasuS.LinkPredictionofSocialNetworkBasedonWeightedProximityMeasures[C]∥ProceedingIEEE/WIC/ACMInternationalConferenceonWebIntelligence, 2007

[8]LüL,ZhouT.LinkPredictioninWeightedNetworks:TheRoleofWeakTies[J].EurophysicsLetters, 2010, 89(1): 18001

[9]WangL,HuK,TangY.RobustnessofLink-PredictionAlgorithmBasedonSimilarityandApplicationtoBiologicalNetworks[J].CurrentBioinformatics, 2014, 9(5): 1-7

[10]ZhouT,LüL,ZhangYC.PredictingMissingLinksViaLocalInformation[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystem, 2009, 71(4): 623-630

[11]LüL,JinCH,ZhouT.SimilarityIndexBasedonLocalPathsforLinkPredictionofComplexNetworks[J].PhysicalReviewE, 2009, 80 (4):046122

收稿日期：2015-10-27

基金项目：国家自然科学基金(11571011)资助

作者简介：李婷(1990—)，女，西北大学硕士研究生，主要从事机器学习研究。

中图分类号：O212.1

文献标志码：A

文章编号:1000-2758(2016)03-0544-04

LinkPredictioninStructureWeight-BasedNetworks

LiTing1,ZhangHai1,2

1.School of Mathematics, Northwest University, Xi′an 710127, China 2.Institute of Applied Mathematics, Academy of Mathematics and System Sciences,Chinese Academy of Sciences,Beijing 100190,China

Abstract:In this paper, we try to study the link prediction problem of social network by treating the structure information as a transform function and transforming un-weighted network to weighted one. Further, for some weighted networks, we rethink their weights, and consider the real weights、structure weights as well as the combination of these two values as the weight of these networks respectively and study the link prediction problem of resource allocation along local path、resource allocation index and local path index in weighted networks. The experiments show that statistical method in structure weight-based networks has a well prediction effect. Simultaneously, weighted RALP also performs better than both the weighted RA and weighted LP.

Keywords:link prediction; structure weight; statistical method