文摘

在过去的研究中,研究人员发现端点学位,h指数,和coreness可以量化端点链接预测的影响,特别是综合端点程度和h指数改善预测性能较传统的链接预测模型。然而,无论是端点学位还是h指数可以描述聚合程度的邻居,导致不准确的端点的影响强度的表达式。通过丰富的调查,我们发现研究者忽视的重要性coreness端点的影响。与此同时,我们也发现综合端点程度和coreness不仅可以准确地描述端点的最大连通子图,但是也表达了端点的影响强度。在本文中,我们提出了DCHI模型合成端点程度和coreness HCHI模型合成h指数和coreness SRW-based模型,分别。广泛的模拟在十二个真正的基准数据集显示,在大多数情况下,DCHI显示链接预测的预测性能优于HCHI和其他传统模型。

1。介绍

链接预测的研究旨在找到丢失的,假的,或可能通过观察到的网络结构和信息的链接(1- - - - - -5]。因此,链路预测算法已经应用于许多领域。例如,链路预测算法可以去除噪声的网络6]。此外,链路预测算法还可以应用于朋友的建议在在线社交网络7- - - - - -11)和产品对电子商务网站的推荐(12- - - - - -16]。此外,链路预测算法生物实验提供参考,从而降低实验成本的(17- - - - - -19]。此外,链路预测算法可以揭示网络演化机制和组织模式(20.- - - - - -22]。

为了揭示复杂网络的结构,研究人员提出大量的链接预测模型。具体来说,基于本地信息的模型已经获得了更多的关注。例如,Kossinets [23)发现,两个陌生人成为朋友,如果他们有更多的共同的朋友在社交网络。纽曼(24)发现,两位科学家更有可能在将来建立合作关系,如果他们有更多的共同的合作伙伴。基于这一现象,研究者提出共同邻居的模型(CN)。基于CN,一些研究人员提出改进模型,如沙顿(25]和LHN-I [26]。此外,根据不同的相似性共同邻居的贡献,亚当和阿达尔月提出AA模型(27]。周et al。28)提出了资源分配模型(RA)。此外,Cannistraci et al。29日CN]提出,AA,风湿性关节炎,和其他可以由当地社区信息加权算法,可进一步改善这些模型的性能。然而,模型基于共同邻居只考虑端点上一步的影响路径。尽管进一步研究,陆et al。30.]提出本地路径模型(LP)通过考虑端点在三步路径的影响。此外,一些模型考虑全球信息,如卡茨(31日)和层次结构模型(32]。此外,一些模型的考虑拟局部信息,它可以在本地信息补偿精度低的缺陷,在全球信息高昂计算复杂性。例如,当地的随机游走模型(LRW) [33walker)认为一个随机拟局部范围内,和叠加随机游走模型(SRW) (33)认为LRW不同路径长度的影响。基于SRW HSRW [34]和CSRW [34)模型考虑h指数的角色(35]和coreness [36分别与不同的路径长度,]。简单的混合影响模型(SHI) [37)综合考虑端点的作用程度和h指数作为混合的影响具有不同的路径长度。

目前,许多链接预测模型只考虑程度(33的端点,比如Sørensen [38],LHN [26],LRW [33],SRW [33]。这些模型说明源端点可以有效地传播影响到目标端点如果源端点有更多的邻居连接目标端点。通过丰富的研究中,陆et al。39)发现h指数显示出更好的性能量化的影响比学位和coreness端点。朱et al。37)发现端点拥有大型综合程度和h指数可以获得更广泛的最大连通子图,可以帮助吸引其他节点的端点。通过进一步的调查,我们发现端点聚合程度的影响可以表示的邻居。邻居的大聚合程度说明了端点有广泛的最大连通子图,从而吸引更多的节点。聚合程度的邻居只能coreness量化的端点。因此,我们合成的端点程度和coreness(或h指数和coreness)量化端点的影响力和建立新的链接预测模型。虽然史模型的基础上,综合程度和h指数一直在探索,综合端点程度和coreness(或综合h指数和coreness)尚未完全证实。

图1显示了一个明确的说明。在图1、端点b拥有学位= 6,h指数= 3,分别和coreness = 3。影响强度的端点b是大小6只考虑到学位。然而,只有程度不能表达的深度和范围的影响准确的端点。由于coreness在端点的影响的作用,综合程度和coreness或合成h指数和coreness可以更好的量化端点的最大连通子图和聚合程度的邻居。对端点b,产品的程度(h指数)和coreness 18(9)。显然,学位和h指数显示不同大小的最大连通子图属于端点b具有相同coreness,导致不同的端点的影响。因此,预测性能的影响端点基于不同的量化指标需要进一步探讨。

在现实世界中,我们发现许多现象来证实我们的想法。例如,在微博上,一个普通的个体拥有有限的影响力,因为他/她只有许多个人追随者的同事,同学,亲戚,或朋友,这表明他/她只有很大程度上。然而,公众人物拥有广泛而强大的影响力,因为他们有大量的粉丝俱乐部,这表明他们有大型coreness加强他们的影响力。科学家的合作网络,如果一个科学家只与许多学者合作,这意味着他/她已经很大程度上但coreness小,不能被更多的研究人员和科学家很难进一步吸引他们合作。在电子商务网络,产品的适用性取决于购买组具有类似身份,如男性/女性群体、学生群体,和老师组,显示聚合度的重要性。在论文引证网络中,一篇论文的价值取决于研究人员在同一个字段的引用,而不是引用在不同领域的研究。

总之,在本文中,我们定义的混合影响综合程度和coreness(综合h指数和coreness)重新定义SRW并提出两种改进模型DCHI和HCHI进一步探索链接预测的准确性。十二个真实网络实验结果表明DCHI展品更好的链接预测性能。

本文的其余部分组织如下。节2我们建立两个模型的基础上,综合程度和coreness综合h指数和coreness,分别。节3介绍了十三个基准实验数据集。节4链接预测指标和八个主流基线,分别。节5,实验结果进行了讨论。节6描述的结论。

2。基于混合模型的影响端点

首先,我们研究链接在一个无向简单网络预测模型 ,在哪里是一组链接(表示所有的边缘。)的数量和是指节点的集合。多个链接和self-connections消除。每对节点, ,一个分数, ,给出的概率来计算他们的未来连接。在这篇文章中,我们设置相似值直接作为一个分数,和一个更大的分数说明潜在的链接有更多的可能性。

其次,我们将展示两个模型基于程度(SRW [33])和综合程度和h指数(SHI [37)分别如下。

2.1。SRW模型

刘等人。33使用随机游走构建相似性模型,发现所有中间节点在两个端点之间顺序根据马尔可夫链有一步传输概率的 ,在哪里表示节点的程度和 如果节点成功连接和 如果不是。节点的顺序 - - - - - -一步之间和表示为 。因此, - - - - - -步传输概率的来用 和 。重要的是,刘等人考虑的程度和量化端点和定义SRW的影响 在哪里和表示程度的端点和 ,分别为,表示网络中链接的数量。 和 描述端点的影响和 ,分别。

2.2。史模型

朱et al。37发现h指数可以代表端点的最大连通子图和描述强度的影响。因此,朱镕基等人只是综合程度和h指数作为端点和取代的混合影响学位SRW定义一个简单的混合影响模型(SHI) 在哪里 和 表示节点的混合影响和分别基于综合程度和h指数。

尽管端点程度和h指数可以量化的端点的影响,他们只代表邻居和最大连通子图的数量分开的端点,忽视端点的影响强度。端点可以表达的影响强度的coreness端点,因为coreness可以量化邻居代表端点的聚合程度的影响强度。因此,我们考虑为端点coreness的作用影响。最后,我们建立两个模型基于综合程度和coreness (DCHI)和综合h指数和coreness (HCHI)分别如下。

2.3。DCHI模型

通过部分的解释1说明图1,我们综合程度和coreness量化端点和取代度的影响在SRW DCHI为建立一个新的模型 在哪里 和 表示节点的混合影响和分别基于综合程度和coreness。

2.4。HCHI模型

此外,我们合成h指数和coreness量化影响和取代学位SRW HCHI建立一个新的模型 在哪里 和 表示节点的混合影响和分别基于综合h指数和coreness。

3所示。实验数据

在本节中,我们介绍12个真实网络数据集准备下面的实验。(1)我们Air97 (USAir) [40)代表美国航空网络。(2)酵母PPI(酵母)41)代表了酵母的蛋白质关系网络。(3)食物网(食品)42]代表碳交易所的关系在佛罗里达柏树湿地的生态系统。(4)电网(权力)43代表了美国西部的电力传输网络。(5)NetScience (NS) [44)代表科学家之间的合作发表论文关于网络的话题。(6)爵士(45)代表了网络的爵士音乐家。(7)电子邮件网络(电子邮件)46代表电子邮件通信网络大学·罗维拉我在西班牙Virgili (URV)。(8)Slavko [47)代表了友谊网络Slavko Zitnik在Facebook上。(9)加州大学欧文分校处理社交网络(UCsocial) [48)代表一个在线社交网络由加州大学的学生。(10)传染性(Infec) [49)代表了离线接触网络的游客在展览名为“传染性:远离”科学画廊在都柏林,2009。(11)EuroSiS web (EuroSiS) [50)代表之间的交互网络科学在社会演员从12个欧洲国家。(12)秀丽隐杆线虫(CE) [43)代表的秀丽隐杆线虫线虫神经元网络。表1提到网络的基本拓扑特性列表。

实现预处理、弧没有方向的修改链接,和循环和multiedges消除,确保网络没有过秤和无向。随后,最大的有关简化网络子图提取,以确保连接。

一开始,网络链接的集合分为训练集包含链接以随机的方式,和测试集包含链接,连接的是保证1]。此外,30个部门分别是相同的,在网络上进行。接下来,实验过程执行30分开训练集和测试集,平均精度达到统计的方式,实现和度量召回超过30倍。

4所示。实验方法

4.1。度规

(36),一个度量的准确性,可以解释为一个潜在的概率链接(链接 )排名得分高于一个不存在的链接(链接 ,在哪里U表示通用链接集)。在具体实现中,n独立比较如果潜在链接排名更高次,一样的不存在的链接次,总分数积累和 。在那之后,所表达的平均分数n-比较像

全球评估模型的性能。如果所有成绩源自一个独立的和相同的分布,值应该等于0.5。因此,准确性的程度超过0.5显示多少比纯粹的机会更好的执行模型。

4.2。基线

比较,我们介绍八个基本模型如下:(1)常见的邻居(CN) (24)描述端点之间的相似性计算共同邻居的数量,定义为 在哪里 ,代表一组端点的邻居和 是指共同邻居端点的数量和 。(2)亚当的达/ (AA) (27),基于CN,抑制共同邻居的贡献与大程度运用逆对数,这被定义为 在哪里表示节点的程度 。(3)资源分配(RA) (28),类似于AA,抑制共同邻居的很大程度上通过应用共同邻居的度的倒数,这被定义为 (4)本地路径指数(LP) (30.)认为端点之间的相似性两步、三步路径同时与两步路径优先,这被定义为 在哪里代表了邻接矩阵是一个惩罚参数。(5)叠加随机漫步(SRW) (33]介绍了部分2。(6)CSRW [34]利用coreness量化端点和替换的影响程度在SRW的影响力,这被定义为 在哪里和代表的coreness节点和 ,分别。(7)HSRW [34)利用h指数量化的影响端点和替换在SRW的影响程度,定义为 在哪里和代表节点的h指数和 ,分别。(8)简单的混合影响(SHI) (33]介绍了部分2。

5。结果与讨论

探索该模型的预测性能,广泛的模拟真实数据集12日进行。通过比较几种主要基线精度指标,我们获得模型的实验结果和讨论的结果。

施、HCHI DCHI模型主要考虑两个方面:随机行走路径和混合的影响端点。通过模拟实验,实验结果表明,端点之间的随机行走的步数会影响链接预测的准确性。为说明预测精度的变化的数量的步骤t,我们绘制关系曲线如图2。

在图2史(综合程度和h指数),HCHI(综合程度和coreness)和DCHI(综合h指数和coreness)模型显示的预测表现随机步骤t,他们表现出不同的最佳精度在一定数量的步骤t,分别。具体来说,史显示最佳AUC值t= 15在食品、电力、NS、电子邮件,UCsocial, Eurosis,t= 5 USAir和CE、t在酵母= 3,t在爵士乐= 2,t在Slavko = 6,t在Infec = 9。显然,最优的步骤施主要出现在漫长的道路t= 15,说明长路径可以进一步促进混合传播基于程度和h指数的影响。然而,HCHI DCHI所有显示最佳AUC值t在USAir = 5,食物、Slavko Infec, Eurosis, CE,说明拟局部路径可以进一步促进混合动力影响传播基于h指数和coreness或学位,coreness。重要的是,我们发现影响有关coreness随机游走过程中很容易泄漏在长路径,导致削弱的强度影响端点之间传播。然而,在权力,HCHI预测性能和DCHI达到最优值t= 15因为电网包括大量的长路径平均距离 更长的时间比其他数据集(指表1)。此外,DCHI,与史和HCHI相比,有较大的最大连通子图的大小和多路径传播的混合影响端点。因此,DCHI显示十个最好的预测性能数据集(黑色马克在每个数据集)除了酵母和CE。

此外,我们比较HCHI和DCHI有八个链接预测模型CN, AA,风湿性关节炎,LP SRW, CSRW HSRW,史。展示实验结果,我们展示了30多个模拟表平均AUC值2对所有模型。突显出大胆的字体表示最好的AUC值在每个数据集和括号中的数字表示的最优随机漫步的步骤t,HCHI和DCHI获得最优AUC值在八个数据集。

从表可以看出2,7个数据集存在最佳值DCHI与权力,NS,爵士乐、电子邮件、Slavko Infec, Eurosis。相比之下,当地模型CN、AA和RA显示最糟糕的预测性能,因为他们只考虑本地路径的影响,忽略端点。然后,最优值在三个数据集存在与酵母LP,食物,和UCsocial,说明拟局部路径可以限制促进预测性能。SRW, CSRW, HSRW也显示最糟糕的表现,因为他们只考虑单独的贡献程度,coreness,和h指数,即学位,coreness和h指数不能量化的影响全面端点。最后,我们专注于史的表演,HCHI, DCHI。在十二个数据集,有七个DCHI最佳表演。DCHI,与史和HCHI相比,显示了有效的影响端点的端点(例如,广泛的最大连通子图和聚合程度的邻居),发现足够的路径无关的两个端点之间。因此,由于综合程度和coreness混合的影响可以是一个很好的量化指数,DCHI可以更好地提高预测精度比史和HCHI在许多情况下的链接预测。

此外,低计算复杂度是链接预测的必要条件。两个产品的时间复杂度 矩阵 。根据基线模型的定义,CN, AA, RA拥有的时间复杂度LP, SRW CSRW HSRW,史 与系数 。尽管HCHI和DCHI有相同的时间复杂度 ,两个提出模型,特别是DCHI,显示更大的性能提升。因此,该模型显示一个更好的性能没有增加复杂性。

6。结论

目前,研究人员关注的贡献的影响基于本地端点链接预测,拟局部或全局相似性。量化端点的影响,研究人员考虑的程度,h指数,或单独coreness,都不能全面评价端点的影响。具体来说,端点学位只代表端点的数量的邻居,但不能描述最大连通子图。h指数可以表达端点的最大连通子图量化的影响范围。然而,端点程度和h指数无法量化的影响强度端点和导致不完整的影响表达。我们发现coreness可以代表聚合程度的端点,可以准确量化的影响强度的端点。

通过丰富的调查,我们发现综合程度和coreness综合h指数和coreness可以量化端点准确、全面的影响。因此,我们合成学位(h指数)和coreness端点和取代度的混合影响SRW建立两个模型DCHI HCHI。

我们探索DCHI的预测性能和HCHI CN之间比较,AA,风湿性关节炎,LP SRW, CSRW,施HSRW,十二个真实的数据集。因此,我们表明,DCHI明显优于其他模型度量AUC,不增加计算复杂度。突出改善精度说明了综合程度和coreness混合影响可以描述端点的端点影响强度准确、可以吸引更多的节点产生联系。

虽然我们的模型验证数据集,端点之间的模型只做一个简单的综合程度,h指数,coreness。我们在不同的网络找到度不同,所以做H-indices和coreness。网络异质性特点是异构度,H-indices, coreness直接导致异构的影响。我们发现端点在网络异构影响较小的可以相互吸引的可能性更大。这样的特点,我们将进一步开展研究异构模型基于DCHI和HCHI混合影响。在未来的研究,异构的复杂网络的影响将成为一个至关重要的问题。

此外,我们的研究可能提供有关新发现链接预测基于相似性。我们的研究结果可以应用到朋友的推荐,产品的建议,科学家们合作,生物实验,等等。

数据可用性

使用的数据来支持这个研究的发现是可用的http://vlado.fmf.uni-lj.si/pub/networks/data/和http://snap.stanford.edu/data/index.html。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是由中国国家自然科学基金(没有。61471060)和北京大学的帖子和Telecommunications-China移动研究所联合创新中心。