文摘
各种复杂网络的快速增长,链接预测变得越来越重要,因为它可以发现丢失的信息和预测未来网络中节点之间的相互作用。最近,汽车和CCLP索引链接预测提出了通过不同的三角形结构信息。然而,索引可能会失去一些共享邻居的贡献。我们在这项工作中提出的一个新的索引来弥补弱点然后提高链路预测的准确性。该指数关注新的三角形结构,即。,the triangle formed by one seed node, one common neighbor, and one other node. It emphasizes the importance of these triangles but does not ignore the contribution of any common neighbor. In addition, the proposed index adopts the theory of resource allocation by penalizing large-degree neighbors. The results of comparison with CN, AA, RA, ADP, CAR, CAA, CRA, and CCLP on 12 real-world networks show that the proposed index outperforms the compared methods in terms of AUC and ranking score.
1。介绍
作为基础研究热点在复杂网络分析中,链接预测已广泛应用在理论和现实中,如网络演化的分析(1,2),推荐系统(3),检查潜在的蛋白质之间的相互作用在生物网络4,5]。链接预测的基本任务是估计缺失或潜在存在的独立网络中节点之间的联系(6,7]。到目前为止,大量的算法和模型提出了链接预测(6,8,9]。文献[8组织他们分为两种方式:相似性的方法和上优于方法。无关的节点之间的相似性的方法计算相似性得分基于已知的信息。然后,降序排名列表节点对根据其相似性分数获得和顶部的节点对被认为最有可能有联系。学习型方法正式链接预测问题转化为一个二进制分类任务(10),使用机器学习的方法来解决这个问题。在学习型的工作方法的关键是构造节点对的特征向量。一般来说,上优于比相似性的方法更复杂。
相似性方法背后的假设越相似,两个节点,它们之间可能存在的联系(8]。这个想法很简单和直观的。因此,这种方法的研究已经成为主流的(6,9]。共同的邻居(CN)指数11),顾名思义,只需计算两个节点之间的共同邻居的数量。Adamic-Adar (AA) [12)和资源分配(RA) (13]索引两种变体的CN指数;他们惩罚的贡献很大程度上常见的邻居。这些索引被称为本地方法,因为他们只使用局部结构信息。此外,一些全球和quasilocal方法也被研究人员提出,如Katz (14],SimRank [15与重启[],随机漫步16),本地路径(17)、链接(18),和当地的随机游走19]。
尺寸的复杂网络的不断增长,当地的方法仍然是优秀的候选人,因为它们更有效的比全球和quasilocal方法运行时间。因此,我们在本研究中关注本地方法。最近,Cannistraci等。提出了汽车指数(20.),这表明共同邻居之间的联系,也就是说,local-community-links(拼箱),比常见的邻居链接预测更有价值。在汽车指数当地社区通过两个常见的邻居是一个三角形和一个种子节点。在这个例子中网络图所示1(一个),有一个种子的共同邻居节点之间的拼箱和(见图1(b))。因此,汽车索引分配四个节点的相似性得分和 。然而,如果我们去除之间的联系和 ,汽车将分配一个零相似性得分和 ,即使他们有四个共同的邻居。此外,拼箱的想法也插入AA, RA和Jaccard索引(20.]。之后,吴et al。提出了CCLP指数基于共同邻居的聚类系数。这个索引考虑所有三角形通过一个共同的邻居。例如网络图1(a),有三角形通过节点 , ,和 ,分别(见图1(c))。因此,积累CCLP索引节点的聚类系数 , ,和当计算相似性和 ,但完全忽略了节点的贡献 。在实际网络中,可能没有三角形通过部分甚至全部共享邻居的一个节点。因此,汽车和CCLP索引可能会分配一个非常低甚至零相似性分数的节点对,即使它有很多共同的邻居。
在本文中,我们定义了一个新类型的三角形结构,称为TRA-triangle,由一个种子节点,形成一个共同的邻居,和另一个节点(见图1(d))。基于TRA-triangle,一个新的相似性指数,即交易指数,提出了链路预测。这个指数表明,可以形成共同邻居TRA-triangles种子节点比其他更重要。此外,该指数也惩罚了很大程度上的邻居,在类风湿性关节炎指数(13]。尽管所有的交易,汽车,CCLP索引是基于三角形结构,背后的直觉是不同的。轿车索引相信拼箱是比普通的邻居更有价值。CCLP指数受汽车指数但雇佣所有三角形通过共同的邻居,而交易指数,只使用TRA-triangles,罢工之间的平衡车,CCLP。此外,正如上面提到的,轿车和CCLP索引失去共同邻居的贡献没有通过三角形,而交易指数计数的贡献各种常见的邻居。因此,交易指数可以达到更好的预测精度比轿车索引和CCLP指数。12日交易指数的准确性评估实际的网络从各领域。实验结果表明,我们的指标远远优于轿车索引和CCLP指数。玫瑰的网络为例,这是一个非常稀疏的网络,汽车和CCLP改进由交易,AUC的度量下,分别高达26.9%和4.2%。
剩下的论文结构如下。节2,我们给的描述链接预测问题和评价指标,对比方法和网络列表,描绘了Wilcoxon signed-ranks测试。部分3介绍了该方法。节4,该方法的实验结果和性能分析。最后,部分5总结这项工作。
2。预赛
2.1。问题描述和度量
给定一个无向和未加权的网络 ,在这和分别是节点集和链接设置,在这项研究中,多链路和self-loops是不允许的。让 网络中节点的数量,让是通用可能联系集,其中包含可能的链接。然后,nonobserved链接或nonexisting链接的集合 。假设有一些丢失的链接 ,链接预测的任务是找到这些链接。相似性的方法对每个节点分配一个相似性得分 一对节点和假定得分高,越有可能它们之间有联系。
测试性能的相似性指数,我们随机将链接设置分为两部分:训练集和测试集 ,这样 和 。 应该是观察到的信息,然后呢是用于测试。两个parameter-free指标是用来量化链路预测算法的准确性:AUC [6)和排名分数(21,22]。在这种情况下,AUC得分的概率可以被解释为一个随机选择的缺失的环节(即。一个链接, )给出更高的分数比(即随机选择不存在联系。一个链接, )。实现时,如果我们执行独立的比较时报》,具有较高的得分和那个缺失的环节时报》表示,他们有相同的分数。然后计算AUC值
排名得分(RS)的链接在测试组根据他们的相似性得分排序后下订单要考虑进去。让 nonobserved链接的集合。让是一个缺失的环节和是它的排名。的分数排名被定义为 ,链接的排名分数预测结果如下:
注意,AUC值越高越好,而排名分数是越小越好。
2.2。当地的相似性指数
到目前为止,许多相似性指数提出了预测[链接6,8,9]。在这里,我们一些地方相似索引列表将用于我们的实验比较的目的。
常见的邻居(CN)指数(11)定义了相似之处和他们的共同邻居的数量, 在哪里表示的一组节点的邻居 。
Adamic-Adar (AA)指数(12CN指数)是一种变体,相信小邻居的贡献大于计算相似度时很大程度上的邻居。它的定义如下: 在哪里节点的程度吗 。
资源分配(RA)指数(13)定义了相似之处和资源的数量收到通过他们共同的邻居
自适应程度处罚(ADP)指数(23]惩罚一个共同邻居根据其程度和网络的平均聚类系数。因此,它可以自动适应网络。ADP指数的定义如下: 在哪里是一个常数,是网络的平均聚类系数。我们设置 ,作者所建议的。
汽车指数(20.)表明,两个种子节点更容易联系在一起共同邻居之间是否有联系,这被定义为 在哪里之间的联系的数量吗和其他常见的邻居和 。
创新艺人经纪公司和CRA索引(20.)是由插车指数的概念到AA和RA索引,分别定义为
CCLP指数(24计算相似性和采用聚类系数共同邻居的, 在哪里表示节点的聚类系数 ,这是 在这通过节点是三角形的数量 。
2.3。网络
在这项研究中,我们使用12实际网络来自各领域的评估链接预测方法的有效性。(1)Advogato(副词):一个社交网络的用户主要是自由与开源软件开发人员(25]。(2)C。线虫(CE):线虫线虫的神经网络(26]。(3)海豚:社交网络社区中的62只海豚为生怀疑声音,新西兰(27]。(4)电子邮件:电子邮件交换网络成员之间的一所大学28]。(5)Foodweb (FW):食物链在佛罗里达湾在雨季(29日]。(6)仓鼠:友谊网络用户在hamsterster.com[之间30.]。(7)玫瑰:coauthorships网络的科学家发布预印本高能理论档案从1995年到1999年(31日]。(8)空手道:社交网络的一个空手道俱乐部(美国大学32]。(9)政治博客(PB):一个网络博客关于美国政治33]。(10)USAir:美国航空运输网络系统(6]。(11)词:邻接的网络小说中常见的形容词和名词由查尔斯·狄更斯《大卫。科波菲尔》(34]。(12)酵母:出芽酵母的蛋白质相互作用网络35]。
在这个工作中,所有上述网络被视为无向和未加权的网络,并且只使用每个网络的巨大的分量。表1列出了这些网络的巨大组成部分的基本统计数据。
考虑到网络 ,假设 , 两个种子节点。 被称为一双种子节点与普通的邻居如果他们至少有一个共同的邻居。表示一组种子与常见的邻居节点对,正式 让 , 两个种子节点,是他们共同的邻居之一。如果 ,我们称之为是一个zero-triangle-neighbor;否则,是一个triangle-neighbor。如果 , 被称为CAR-triangle-neighbor如果 (见(18)),被称为TRA-triangle-neighbor。让triangle-neighbors的集合, , 分别表示汽车的集——和TRA-triangle-neighbors。很明显, 。让和是两个子集 。对于任何一对 ,至少有一个共同的邻居不是triangle-neighbor,任何一对 ,他们所有的邻居不是triangle-neighbors共享。更明确, 同样,我们定义 , , ,和 ,这是 相应地,这些子集的比率分别定义为 表2列出这些比率超过12个网络。
2.4。Wilcoxon Signed-Ranks测试
的Wilcoxon signed-ranks测试是一种非参数统计假设测试用于检查两种方法是否同样表现在多个网络(38,39]。让考试成绩差的两个链接预测的方法th网络。不同的排名,是按照他们的绝对值;在关系的情况下,平均分配。让的秩和第二种方法比第一的网络,和相反的军衔的总和。大量的网络数据 通常是分布式大约[39]。在(16), 和是网络的数量。
与 ,如果比-1.96小,我们拒绝零假设,即这两种方法都同样执行。
3所示。该指数
链路预测问题有一个熟悉的关系网络演化机制(2,40]。最近提议的三角形生长机制表明,各种关键特性观察到在大多数实际网络可以在模拟生成网络(41]。因此,三角形结构信息链接形成有着重要的影响。
在这项工作中,我们专注于一个新的三角形结构,即TRA-triangle。TRA-triangle穿过一个种子节点,一个共同的邻居,和另一个节点。在我们看来,共同邻居能够形成TRA-triangles比其他人更重要。给定两个节点和 ,我们表示三角形通过它们的数量 ,这是
例如网络图1(一)、三角形用于种子节点 , 如图1(d)。显然, 和 。因此,节点在更多的亲密接触吗比 。鉴于种子节点和 , 是他们共同的邻居之一。函数 总结TRA-triangles由的数量 , ,和 , ,这是
在本文中,我们提出一种新的相似性指数,结合上述三角形结构和类风湿性关节炎指数的概念13]。为方便声明,我们名字的新方法交易索引。它的定义是
在(19),分子是 。因此,交易指数不会错过任何共同邻居的影响。如果所有常见的邻居是zero-triangle-neighbors、交易退化RA。例如网络图1(一), 。
4所示。实验结果
表3列出了不同方法的预测结果的AUC的12个网络。结果得到的平均50多个独立的实现为每个网络测试设备包含10%的链接。最高的AUC值为每个网络以粗体突出显示。显然,交易指数得到九12网络效果最好。创新艺人经纪公司,与此同时,交易指数优于汽车CRA, CCLP索引所有网络。我们可以看到从表2大多数的网络上,存在不同程度的这样的种子节点对属于常见的邻居和/或 。所介绍,CCLP指数将给那些对或零相似的得分越低。此外,这两个值和在大多数的网络非常高。尤其是,海豚,电子邮件、仓鼠、玫瑰,和酵母,相应的值大于0.8。这一现象表明,只有很小一部分的种子与常见的邻居节点对这些网络可以分配的相似性得分轿车索引。虽然有一些对属于种子节点和/或 ,交易指数还可以分配合理的相似性得分。因此,交易的结果索引表3比他们的汽车,创新艺人经纪公司,CRA, CCLP索引。CN, AA, RA和ADP索引,ADP指数表现最好的,因为它可以惩罚共同邻居通过自动适应网络。海豚,玫瑰,USAir ADP指数获得最好的准确性;我们的指数接近最好的的性能。此外,交易指数达到更好的AUC分数比其他弗兰克-威廉姆斯和空手道。这个结果表明TRA-triangles发挥重要作用在这两个网络。从表1,网络都是密集的。大致说来,的概率存在TRA-triangle-neighbors种子节点之间在密集网络不仅仅是稀疏的。
检查是否该指数与方法相比明显不同,我们应用Wilcoxon signed-ranks测试(39根据表中的结果)3。成对测试结果呈现在图2。从统计的角度来看,我们的指数明显比其他除了ADP指数,因为ADP指数的能力自动适应网络的结构。虽然没有统计学差异指数和ADP指数据Wilcoxon signed-ranks测试,我们的索引执行比ADP的AUC索引。
图3展品AUC 12日网络的变化的比例在从10%增加到20%。从图很明显3所有索引的AUC值显示下降趋势比例从10%增加到20%时除了弗兰克-威廉姆斯。增加的原因是将减少训练集的大小然后将导致种子之间的共同邻居节点的数量变得越来越小。因此,链路预测的难度将会提高。弗兰克-威廉姆斯网络,具有平均程度高,平均最短的距离小,低程度的异质性,是一个非常密集的网络。因此,训练集的减少使轻微的准确性对弗兰克-威廉姆斯的影响。此外,我们可以观察到从图3演出的所有索引之至,CE、海豚、电子邮件、仓鼠、玫瑰、空手道,单词,和酵母是非常相似的。在这些九网络,轿车的AUC值指标明显低于其他人。网络上的弗兰克-威廉姆斯,轿车的结果指标优于CN, AA,风湿性关节炎,和ADP索引,因为弗兰克-威廉姆斯是一个非常密集的网络,CAR-triangle-neighbor的比例是很高的(见表2)。PB和USAir轿车的性能指标是比不上其他九个网络。原因是两个网络平均度高,小平均最短的距离,CAR-triangle-neighbors的比例高。
此外,我们的AUC值列表12网络不同的方法 在表4。我们索引的结果比其他八12网络中,而CCLP指数达到CE的最高价值。
表5给出了结果的排名得分。这些结果类似于那些在表3。交易指数的排名得分优于其他人除了海豚,玫瑰,USAir。成对的Wilcoxon signed-ranks测试结果如图4。类似于测试图2相比,交易指数明显优于方法除了ADP指数。如上所示,ADP具有自适应能力,因此比其他方法相比性能更好。
图5描述了12日排名得分的变化网络时 从10%增加到20%。显然,所有索引收益率更高的排名分数的增加 。不要忘记,更高的排名分数意味着精度下降。正如上面分析的,弗兰克-威廉姆斯很密集。因此,弗兰克-威廉姆斯AUC非常轻微的变化(见图3)。然而,排名分数FW的变化更明显,尤其是对创新艺人经纪公司和CRA索引。原因是排名得分的计算考虑所有丢失的链接。此外,见图5创新艺人经纪公司和CRA索引执行比汽车指数根据分数排名。从这三个指标的定义,我们发现创新艺人经纪公司和CRA索引都可以得到更多的负面影响比汽车从zero-triangle-neighbors指数。
最后,分数排名12网络上的所有方法 表中列出6。我们指数优于其他指标除了玫瑰和USAir排名得分。这些结果与他们的AUC是一致的。相比之下,弗兰克-威廉姆斯,TRA-triangles对玫瑰和USAir的影响很小。
从上面的结果,我们可以得出结论,交易指数优于轿车索引和CCLP指数和执行比common-neighbor-based方法在大多数的网络。
5。结论和讨论
链接预测复杂网络分析的一个重要研究课题,并在各领域的广泛应用。灵感来自于三角形生长机制在网络发展41),本文提出了链接预测交易指数。当计算两个种子节点之间的相似性,提出了指数不仅计数的贡献所有常见的邻居还强调的重要性可以形成TRA-triangles的邻居。在某种程度上,TRA-triangles反映了邻居和种子节点之间的亲密关系。此外,该指数还采用理论的资源配置(13)由于其有效性。
交易指数实验评估的准确性超过12实际网络从各领域的AUC和排名得分。实验结果表明,该指数表现远比轿车索引。与此同时,我们的指数优于CCLP指数,因为上级策略的指数。common-neighbor-based方法,提出了指数收益率的准确性在大多数网络的一些改进。这些结果表明,结合TRA-triangles的信息和资源分配理论的相似性指数是一个有用的链接预测。
有一些改进的研究为我们的指数在未来。其中之一是分析TRA-triangles的程度的影响在不同的网络,并进一步自适应设定的重量TRA-triangles在不同的网络上。二是研究交易指数的应用程序在其他话题,比如社区检测和异常检测。此外,对于上优于链路预测方法,可以使用交易指数作为一对节点的一个特性。
数据可用性
在这项研究中使用的网络是可用的http://deim.urv.cat/ alexandre.arenas /数据/ welcome.htm,http://www-personal.umich.edu/ mejn / netdata /,http://vlado.fmf.uni-lj.si/pub/networks/data/,http://noesis.ikor.org/datasets/link-prediction,http://konect.uni-koblenz.de/networks/。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是由中国国家自然科学基金(没有。61602225)和基础研究基金为中央大学(没有。lzujbky - 2017 - 192)。