W-Index:索引链接预测评价只考虑胜利的作用

文摘

随着大量的链路预测方法的出现,如何准确地评价和选择适当的已成为一个关键问题是不容忽视的。AUC以来在2008年首次用于链接预测评估,它可以说是最首选的指标,因为它平衡的角色赢得(测试链接得分高于无法链接)和吸引的作用(它们有相同的分数)。然而,在许多情况下,AUC没有显示出足够的歧视在评估链接预测方法,尤其是基于局部相似。因此,我们提出一种新的衡量标准,叫做W-index,只考虑胜而不是平的效果。我们广泛的各种网络实验表明,W-index使链接预测方法的准确性分数更多的区分,它不仅可以扩大当地的这些方法也扩大其全球的距离。我们进一步证明的可靠性W-index排名变化分析和相关分析。特别是一些以社区为基础的方法,被认为是有效的,我们重新评估后不显示任何优势。我们的研究结果表明,W-index链接预测是一个有前途的指标评价,能够提供令人信服的歧视。

1。介绍

链接预测复杂网络的最基本问题之一,旨在推断网络链接形成过程预测了基于目前观察到的链接(或未来的关系1]。能够有效地预测未来我未被注意的链接将使我们能够在社交网络成员之间的交互(2,3[],进行成功的推荐user-item由两部分构成的网络4,5),为基础设施系统的规划过程提供指导6在股票市场,优化资产配置(7),发现药物的相互作用或确定新的target-candidate蛋白靶向给药8,9,节约成本和制造企业降低运营风险10,11]。到现在为止,已经提出了各种方法链接预测(12- - - - - -16),其中大部分可分为基于heuristic-based方法和学习方法(17]。然而,有很多长期挑战链接预测的评价方法。

许多定量评价指标用于链接预测采用从二进制分类任务18]。他们可以分为两大类:固定阈值指标和阈值曲线(19,20.]。作为一个典型的固定阈值指标,精度(21)通常用于链接预测文学研究。但是,像其他固定阈值指标,它受到限制,很难选择一个合适的阈值的分数空间。换句话说,精度只关注l与高层或最高分数。因此,链接的准确性预测不同的选择l。此外,Clauset et al。22]提出了使用精度评估预测算法有很大的劣势。这意味着精度较高,考虑到上面l与得分最高,而一个算法的总体性能是不满意的,因为一些丢失的连接是比其他人更容易预测。例如,如果一个网络重尾分布程度,的可能性就会很大,两个顶点高度丢失的连接,和这样一个连接可以很容易地预测。

由于这些问题与固定阈值指标,推荐使用阈值曲线作为替代(19,23]。阈值曲线特别适合类不平衡任务,因此使用越来越普遍在链接预测评价24- - - - - -26]。AUC,接受者操作特征(ROC)曲线下的面积(27),是一个标准的指标评价的链接预测。AUC评估方法的性能根据整个的所有未被注意的链接的列表和测试链接。它相当于的概率随机选择测试链接上面出现一个随机选择的分数空间未被注意的环节。AUC指标的使用,严重的类不平衡问题链接预测很大程度上减轻,即。,测试链接的数量远远小于未被注意的链接的数量。

尽管AUC是一个很好的衡量链接预测评价(28),它有一定的缺点。在文献中数据挖掘和机器学习的29日- - - - - -31日],AUC测量的一个重要缺点是忽略了大量的实例和只考虑他们的排名顺序。结果是不可靠的,因为分数差异的实例将被忽略。另一个后果是AUC分数变化的预测可以保持不变,只要实例的排名是相同的。更重要的是,它已经发现,当使用的AUC链接预测评估,一些方法之间的歧视穷人,尤其是对那些于社区的预测因子,如常见的邻居(CN), Jaccard, Sørensen (Sor) [1,32]。在这里,我们认为贫穷的AUC的歧视是一个固有的缺陷,因为吸引了被认为是在AUC的计算。根据AUC指数,如果测试链接和一个未被注意的链接相同的分数,他们在一场平局,得分为0.5分,但是吸引,当然,比赢更重要和损失进行评估,将意味着不加区别的。因此,一个直观的想法是,我们应该更加注意成功与失败,而不是吸引。即使分数的差异很小,分配不同的分数的方法测试链接和一个未被注意的链接比给他们相同的分数。

简单来说,我们认为是胜而不是平计数。本文的目的是提出一种新的衡量标准,称为W-index,只关心谁赢得更多的测试链接和未被注意的链接,而不是多少次他们画,获得有识别力的链路预测方法的评价。

本文的其余部分组织如下。节2,我们简要回顾常用评价指标的链接预测和细节提出W-index度量。链接预测问题和各种预测第三节。第四节提出了六个真实网络实验结果讨论的W-index紧随其后第五节。最后,我们得出结论的工作第六节。

2。W-Index

在本节中,我们首先介绍两个广泛使用的评价指标,即。精度和AUC。然后,我们提出一个新颖的评价指标名叫W-index只考虑获得的数量的测试链接得分高于未被注意的链接。

2.1。精度

鉴于所有未被注意的链接的排名和测试链接,精度定义为相关的链接选择比选择链接的数量。也就是说,如果我们把-和预测的数据链接,其中米(即链接是正确的。,有链接测试集 ),然后的精确值

更高的精度就意味着更高的预测精度。

2.2。AUC

鉴于所有未被注意的链接的排名和测试链接,AUC值的概率可以看作是一个随机选择的测试链接(链接 )给出更高的分数比随机选择未被注意的链接(链接 )。考虑到大规模网络的计算复杂度,我们通常实施抽样实验来计算这个值。如果,在 - - - - - -次独立实验次测试链接比未被注意的链接,有更高的分数他们有相同的分数,AUC值是由

更高的精度就意味着更高的预测精度。如果所有成绩都来自独立且相同的分布,然后AUC值应该是大约0.5。因此,AUC值超过0.5的程度表明比纯粹的更好的一个算法执行的机会。精度和AUC指标被认为是在最近的研究中由于他们不同的焦点。如果两个链接预测方法有相同的AUC得分,一个精度更高的得分被认为是更好的。

2.3。W-Index

链接预测评价,是常见的。我们考虑了作为副产品的“退化”的问题,由陆发现et al。32,33),在许多链接预测算法,尤其是上述于社区的预测因子。美国的“简并”问题是,两个节点对的高概率分配相同的相似性得分。这是因为结构信息的状态是有限和不区分,尤其是对未被注意的联系少的信息,所以无法链接极有可能获得相同的相似性得分。至于一些测试两个低度节点连接的链接,他们也没有信息。因此,区别分数的测试链接和未被注意的链接是不明显,并将并不少见。在代谢网络(34作为一个例子,有超过未被注意的节点对,其中62%被分配得分0的CN算法。所有未被注意的节点对分数高于0,得分1 68%,得分2 21%。和测试与分数为0,1,2占3%,12%,和28%的总测试链接,分别。因此,当比较随机选择测试的分数与随机选择的未被注意的环节,平局的可能性超过7%。实际上,在实验中实现第四节10000年,有超过750的独立实验。因此,评价结果,绘制问题。

在这里,我们考虑了图的副作用1在三个案例。在以下的分析中,这应该是一个预测优于B AUC指标预测。案例1表明,获胜的数量和吸引的预测的数量远远超过相应数量的预测。在这种情况下,忽略了可能会扩大或缩小两者之间的性能差异预测,根据两者之间的差异吸引了数量的预测。

2,吸引的B预测的数量远远大于预测,但获胜的B的数量低于A。如果我们不奖励0.5分画,它得到一个更好的区分两个预测因子。因此,吸引的一个副作用是它缩小两者之间的精度预测的差异,使预测的更少。在大多数应用程序中,找出一个执行明显比其他人更好的预测也是不容忽视的。以蛋白质交互网络为例,他们可以降低实验成本和速度的步伐揭露真相(35,36]。因此,一个好的链接预测评价指标需要不仅有效,而且歧视。

更糟的是,可能会误导人,如例3所示。预测更多的画被认为是比预测B与清晰的成功与失败。假设在一个案例中,使用预测,的次数的相似性得分高于测试链接,等于,和低于未被注意的链接占88%,6%,和6%的总时间,分别。相应的三个比例B预测是90%,0.8%,和9.2%,分别。预测的AUC得分是0.91,和预测B是0.90,这意味着比B .然而,预测B赢得多次预测A .怀疑预测是否真的比预测B。

缓解两个吸引的副作用,我们提出一个新的指标,称为W-index,评估链接预测,它只取决于数量的赢了,不管画的数量。它被定义为

显然,W-index范围从0到1的值。新的评分标准可以减少“简并的州”的影响,使成绩更有识别力的准确性。

3所示。链接预测方法

在本节中,我们主要描述关于链路预测问题的基本定义和相关的概念,然后介绍十个链接预测预测工作。

3.1。定义

考虑一个无向网络 ,在哪里组节点和吗是链接的集合。多个链接和self-connections是不允许的。考虑到通用集,用 ,包含所有 这一对节点之间的联系 ,在哪里表示节点的数量 。链接预测的基本任务是找出丢失的链接(或将出现在未来的链接)在未被注意的集中 。

一般来说,我们不知道哪些链接丢失的或未来的链接;否则,我们不需要做预测。因此,测试算法的准确性,观察到的链接, ,随机分为两个部分:训练集, ,被当作已知信息,测试集, ,是用于测试,不允许信息在这个集合中用于预测。未被注意的链接的集合 ,等于一组吗 。的链接进行验证 。很明显, 和 和 和 。

每个链接的集合 ,说(x,y)∈ ,在哪里 是一对的断开连接的顶点,分配一个分数吗量化它的存在可能由一个链接预测方法,即。,得分测量节点之间的相似性和 。因此,连接节点的可能性随着分数提高,反之亦然。

3.2。基准预测算法

最简单的链路预测算法的框架是相似性算法。由于计算复杂度较高的全球相似性预测(32),我们只选择预测基于本地和拟局部相似性在我们的实验。这些预测的定义如表所示1在细节。

3.2.1之上。当地的相似性预测

在这里,我们考虑三个经典预测基于本地信息:常见的邻居(CN), Leicht-Holme-Newman (LHN)指数37],和资源分配(RA) [38]。让节点的程度 , 是你的邻居节点集 , 是集的基数 是一组常见的一双无关的节点的邻居 。

考虑到每一个普通的邻居不同有助于连接的可能性,提出了一些预测基于社区的信息。因此,我们必须应用集群方案图之前计算这些预测。在这里,我们选择五个地方相似预测基于社区信息预测:WIC [39)举行,intracommunity-based资源分配(“国际机器人与自动化会议”(40),和其他三个是W-forms CN, LHN, RA (41),也就是说,他们是CN-W, LNH-W, RA-W。请注意,是顶点x∈V属于一个集群与标签 , 是集within-cluster (W)共同的邻居, 是intercluster的集合(IC)共同的邻居,然后呢是一个小值常数接近于零。

3.2.2。拟局部相似性预测

拟局部相似性预测需要考虑当地的路径比当地提供一点信息。在这里,我们考虑两个因素:本地路径(LP) [33,38)和地方随机漫步(LRW) [41]。请注意,邻接矩阵,是一个免费的参数, ,在哪里 和是过渡矩阵 如果和连接, ,否则,和初始配置功能;在这里,我们应用一个简单的形式由节点度,即 。

4所示。实验和结果

在本节中,我们实现的实验来验证该W-index指标六个真实网络从不同的领域。首先,我们探讨每个AUC和W-index下预测的预测精度。接下来,我们检查的准确性和稳定性W-index通过排名变化分析和典型相关分析。第三,我们分析了局部和全局预测性能之间的距离。我们进一步反思链接预测方法的选择从W-index的角度评价。最后,我们算出网络结构和训练集长度的影响在这些预测的性能W-index和AUC。

4.1。数据集

我们考虑六个代表真实世界网络从典型的网络科学领域,包括协作、交通、生物网络和社会网络。

注意,这里所有的相似性预测认为会给评分0到一对节点位于两个断开连接的组件。因此,我们并不认为这些孤立节点,strong-connected所有上面的网络。这些现实网络的具体结构特点如表所示2,在那里边的数量,网络的平均度,网络的平均路径长度短,是网络的聚类系数,是网络的assortativity系数的程度。

(1)爵士:爵士音乐家之间的协作网络。每个节点都是一个爵士音乐家,一条边表示两个音乐家一起玩在一个乐队42]。(2)USAir:网络在商业机场的航班在美国(43]。(3)代谢:线虫的代谢网络秀丽隐杆线虫(35]。(4)PB:美国政治博客的网络在2004年美国大选。一个节点代表一个博客,边代表两个博客之间的超链接。最初的边缘是导演;在这里,我们把他们当作无向的(44]。(5)Tvshow:社交网络Facebook页面的电视节目。节点代表的页面和边缘之间的相互喜欢他们(45]。(6)酵母:生物学网络成千上万的蛋白质之间的相互作用(46]。

4.2。实验设置

评估的有效性评价指标,观察到边的集合, ,在每个部门随机分为两个部分:训练集吗和测试组 ; 。对于每一个网络,我们使用训练集生成社区使用鲁汶社区检测算法47]。然后,我们使用W-index, AUC,精度指标来衡量这些预测的预测精度中提到的表2。在我们的实验中,我们继续 在W-index和AUC次独立实验 在所有网络的精度指标。每个值与独立随机获得的平均超过20实现部门的训练集和测试集。注意,我们选择 根据陆LP和周(32), 对于LRW由于运行时间的限制。

4.3。预测精度

在表3,我们现在预测精度结果衡量AUC和W-index六网络。条目对应于每个网络的最高精度被标记为粗体。然后,我们为每个预测计算准确性的差异下AUC W-index,如图所示2。总体来说,表3和图2显示,使用W-index度量并影响这些预测的性能,和所有预测的准确性分数降低。然而,同样的准确性预测在不同网络千差万别。我们发现网络是稀疏的,W-index精度评估的越低,表明预测的性能在很大程度上是受网络结构的影响。例如,平均度和聚类系数Tvshow非常小,所以所有预测的准确性分数极低,而爵士网络是相反的。

4.4。W-Index的可靠性

W-index是否在不同的上下文中可以维护可靠性是一个重要的问题。我们利用基于经验数据的两种常见方法比较分析来验证W-index的准确性和稳定性。首先,图2表明,在W-index指标下,这些预测在每个网络的性能排名几乎是一样的AUC度量下的排名。这意味着如果AUC被认为是能够有效地评估预测的优缺点,W-index具有相同的能力。接下来,我们比较W-index和精度之间的相关系数(见图3与AUC)和精密六网络。从表4之间的相关系数,可以看出W-index和精度密切相似的AUC和精确的所有六个网络。此外,如果我们不考虑CN-W LHN-W, RA-W,和WIC预测由于表现不佳,W-index和精度之间的相关系数是几乎一样的AUC和精度(见表5)。相关系数的变化在不同的上下文的一致性表明,AUC W-index也有类似的评价效果。上面的两个比较分析可以证明W-index的可靠性。

4.5。W-Index的性能

在链接预测,我们认为评价有两个目的。一是量化算法的性能,也就是绝对的评价。另一种是量化的程度,一个因素比另一个叫做相对评价。在这里,我们使用预测精度作为绝对的评价得分,例如,1分的AUC意味着一个完美的预测,和0.5分的AUC意味着预测不是比纯粹的机会。此外,我们使用两种预测的预测精度差异相对评价得分,例如,AUC指标下,RA的准确性是CN的0.97和0.95,然后是相对评价得分是0.02。

一般来说,使用W-index度规,之间有一个较大的可分性评估方法比使用AUC度量这六个真实的网络,这是由以下两个原因造成的。首先,衡量W-index时,绝对评价得分最高的为每个网络仍然是足够高的精度。换句话说,没有明显降低得分最高的衡量了AUC W-index相比之下。具体来说,最高精度的差异不超过0.01的四个六网络。其次,衡量W-index时,相对评价得分最高的为每个网络变得更高的精度。也就是说,不同预测的预测精度差异的AUC W-index都要比其他测量。例如,预测精度0.018 RA和CN的区别是爵士乐AUC,虽然0.024 W-index下。因此,W-index度量可以更好的区分这些链接的性能预测方法。

此外,我们讨论之间的总距离预测性能,给出的 在哪里预测分析和数量吗是一个距离度量。我们选择两个标准距离度量:曼哈顿距离和欧几里得距离。之间的总距离预测性能衡量W-index始终比这大得多的AUC的所有数据集,如图4。根据上述讨论,W-index度量评估方法之间明确鼓励更大的可分性。

4.6。链接预测方法的重新评价

自从W-index鼓励歧视链接预测评价方法,它提供了另一个角度来观察预测的性能。具体来说,我们使用CN和LP的评价分数的比较。与LP相比,它使用高阶路径信息,CN只考虑其二阶路径。因此,其状态也一般限于告诉测试链接和未被注意的链接之间的差异,和更容易画。因此,一个自然的猜测是,CN的性能可能不准确的资讯。不过,我们可以在图中找到2AUC指标下,CN比LP在爵士和代谢。虽然它不如LP在其他四个网络,差距是可以接受的。这是不同的从我们的假设,但根据W-index,除了类似的性能在爵士乐、CN总是比LP,更大的区别。特别值得注意的,在这两个评价指标、性能的CN和LP代谢和USAir逆转。这表明LP确实可以缓解“简并的国家的问题。“通过减少许多吸引来获得更多的成功或失败,LP比CN提供了更细粒度的分数。

从我们W-index的定义第二节,预测精度的差异在于吸引。根据我们的假设,即胜更令人信服的比平评估方法的优越性,差异越小,更可靠的方法。我们可以在图中找到2LP最小的差异在5 6。举行网络LRW和“国际机器人与自动化会议”相反,WIC, CN-W LHN-W, RA-W最大的区别在所有六个网络。与此同时,从表的结果3,平均预测精度差异地方相似措施及其W-forms W-index测量的这六个网络测量的AUC 3.76倍。此外,平均预测精度CN和LP的区别,CN和LRW W-index测量举行CN和“国际机器人与自动化会议”的是2.55,2.41和2.21倍,AUC的测量。例如,平均预测精度CN和CN-W是0.127和0.238的区别在爵士乐的AUC W-index,分别;因此,衡量的差异W-index比衡量AUC的1.869倍。

因此,通过使用W-index,我们可以明确地指出,LP LRW,总体预测性能优越,举行,“国际机器人与自动化会议”而CN-W LHN-W RA-W, WIC表现不佳。正如我们所料,在W-index指标下,拟局部相似性预测显示更明显优于局部相似性预测。令我们吃惊的是,社区信息不一定提高链路预测的准确性。例如,W-form CN并不显示性能优良在先前的研究中,但性能没有显著差异,举行的“国际机器人与自动化会议”这表明引入社区信息的方法对预测的性能有很大的影响。更直观地,我们显示的性能预测的统计分布来衡量AUC和W-index六网络图5。显然,根据W-index,更容易区分之间的性能的方法。杰出的性能得分的方法,如LP和LRW,将有更大的均值和方差小,明显优于他人。

4.7。不同的网络结构

所4.3节,预测的性能在很大程度上是受网络结构,如网络规模(节点数)、网络密度、平均最短路径长度、平均中心,聚类系数和网络直径。澄清W-index和网络结构之间的关系,我们进行实验调查这个广泛的具有不同结构的网络。

Watts-Strogatz (WS)是一种常见的网络小世界网络模型,通常用来描述现实世界的社交网络。改变网络结构,一系列WS小世界构造图如下。首先,一枚戒指n创建节点,然后环中的每个节点加入它k最近的邻居。接下来,执行一系列的重组:每条边(u, )在底层”n撕咬和k最近的邻居”的概率p,代之以一个新的边缘(u, )与均匀随机选择现有的节点 。

表6显示了WS小世界网络的网络结构的六组用于以下实验,即WS-Group1 WS-Group6。由于网络特征密切相关,一个特点的变化会引起另一个变化。例如,随着网络规模变得较小,网络的平均最短路径将不可避免地变得更小。因此,我们只列出每个集团的独立变量的波动范围的网络和忽略因变量的变化,由“标记-。“注意,节点的数量,边的数量,网络的平均度,是网络的密度,网络的平均最短路径长度,的平均中间性中心网络,是网络的平均聚类系数,是网络的直径。

4.7.1。网络规模

我们建造十网络平均10度,但不同节点的数目从100年到1000年,如WS-Group1表所示6。图6显示了每个WS-Group1预测对不同网络的性能。

可以看出,AUC指标下,随着节点数的增加,最初的以社区为基础的局部相似性预测性能显著增加,然后略有增长。图6显示的转折点是600节点。其他的性能预测篮板后温和下降,最终网络规模超过400后一个狭窄的范围内波动。同样,W-index下,以社区为基础的地方相似的性能预测激增,然后稳步上升后,网络规模超过600。与此同时,其他地方相似的趋势预测是一致的,在AUC度规,但变化范围更大。异常,拟局部相似性预测的性能逐渐下降随着网络规模的增加。

4.7.2。网络密度

网络密度描述了所有潜在的部分连接网络的实际连接。我们建造8包含1000个节点的网络,网络的密度变化从0.002到0.05,如WS-Group2表所示6。我们可以看到在图7,当密度非常小,预测的性能有一个巨大的飞跃随着密度的增加来衡量是否AUC度量或W-index。然而,网络密度达到一定值后,预测的表现显示了网络密度不同的趋势继续上升。具体来说,根据AUC度量,以社区为基础的局部相似性预测的性能略有下降,而其他的性能预测是相同的。W-index下,以社区为基础的地方相似的趋势预测是一致的,在AUC度规,但变化范围更大。不同于之前的趋势,其他的性能预测,特别是拟局部相似性预测,逐渐增加。

4.7.3。平均最短路径长度

两个节点之间的最短路径的定义是最小的路径长度。网络的平均最短路径长度定义为平均最短路径的所有成对的节点。我们建造十网络与1000个节点和5000个边缘。这些网络的平均最短路径长度变化从3.26到50.45,如WS-Group3表所示6。

图8表明,无论它是衡量AUC度量或W-index,这些预测的性能会很快达到峰值随着平均最短路径长度的增加。从那时起,这些预测的性能处于稳定的状态。唯一的区别是,根据W-index,这些预测的性能变化范围大于下AUC度量。

4.7.4。中心

中心表达的程度一个节点是整个网络的核心,它可以帮助识别的重要节点。有几种常见的中心算法;在这里,我们以中间性中心为例。中间性中心措施通过节点最短路径的一部分。我们建造十网络与2000个节点和10000个边缘。这些网络的平均中间性中心变化从0.001到0.008,如WS-Group4表所示6。它可以显示在图9AUC,当测量的度量和W-index的性能预测显示了一个快速、指数增加的平均中间性中心增加了平整。同样,W-index下的性能变化范围大于下AUC度量。

4.7.5。聚类系数

聚类系数是一个系数用来描述程度的集群节点之间的一个图表。具体地说,它是节点的相邻节点的连接。图的平均聚类系数的算术平均当地所有节点聚类系数的值,衡量的集聚程度图。我们建造十网络与1000个节点和5000个边缘。这些网络变化的平均聚类系数从0.09到0.67,如WS-Group5表所示6。图10表明,在AUC W-index,预测性能的增加成比例的平均聚类系数网络,但平均聚类系数超过一定值后,增长率下降。这意味着网络的平均聚类系数有一个非常重要的对这些预测的性能的影响。

4.7.6。直径

图的直径被定义为所有成对的节点之间的最大距离。我们建造十网络与1000个节点和5000个边缘。这些网络的直径变化从5到100年,如WS-Group6表所示6。图11表明,在最初的范围,是否衡量AUC W-index,与网络的直径的增加,预测的性能,这一点后,增长可以忽略不计。此外,W-index比下的性能变化范围大,AUC度量。

4.7.7。总结

从上面的分析可以看出,除了节点的数量,其他网络结构产生更大影响的性能预测。由于这些网络结构是高度相关,例如,网络直径越大,越大网络聚类系数和边介数越大,所以实验结果在这些网络看起来很相似,显示的趋势逐步改善性能。当然,由于W-index本身的特点,其范围的变化会比AUC。此外,虽然不是很明显,可以看出,只有三行中可以清楚地看到这10个曲线。这表明这些预测几乎是分为三个类别,即当地的相似性预测)举行(包括“国际机器人与自动化会议”,当地的相似性预测基于社区信息预测)举行(除了“国际机器人与自动化会议”,并拟局部相似性预测。差距在W-index大于下AUC的差距,这是类似于我们之前的结论。

4.8。不同比例的测试集

我们都知道,在机器学习和深入学习社区,重要的是要合理划分训练集和测试集,和链接预测问题也是如此。在这里,我们进行实验研究的性能预测在不同比例下的训练集时使用W-index和AUC进行评估。在实验中使用的数据集是相同的4.1节和实验设置规定的各项条款相同4.2节,除了训练集的比例测试组这不是固定的吗 。我们评估的性能预测的6个网络当训练集的比例的链接范围从50%到90%,如图12。图中的值为每个预测准确性的差异在AUC W-index。

可以看出,随着训练集的比例增加,预测性能的变化与网络结构有关。例如,在Tvshow,所有预测的性能显著提高,增长速度是降低随着训练集的比例增加。同样发生在代谢和酵母,除了LHN预测值。然而,在USAir, AUC和W-index指标下,所有的性能预测波动随着训练集的比例增加,到达最高峰当训练集的比例是0.7。除了LHN预测,爵士乐。PB网络结合了上述两种情况。LHN的性能、LHN-W LRW,和LP预测震荡作为训练集的比例变化,而剩下的预测性能的提高随着训练集的比例增加,增长率逐渐下降。此外,预测性能的改善下W-index大于AUC下评价。

通过以上的观察,不难发现,预测网络适应性;是否可以提高预测性能随着训练集的长度的增加也与预测的性质有关。例如,在大多数情况下,LHN指数的变化不同于其他地方相似预测。此外,拟局部相似性的性能预测是不太敏感的抽样比率比当地的相似性预测。

5。讨论

5.1。W-Index的属性

W-index的属性比较与AUC在以下:(1)所第二节,W-index的范围是0到1,而AUC值的范围从0.5到1。这意味着限制W-index的值大于AUC。然而,AUC得分的链接预测方法也可能低于0.5 (48),这表明该方法未能预测丢失的链接和无法解释网络的演化机制。(2)随机预测(纯机会)是判断的基准链接预测方法的优点和缺点。然而,随机预测的W-index分数不再是一个固定值,像AUC得分0.5分。具体来说,随机预测的分数随生成一个随机的方式得分。例如,如果所有的测试链接和未被注意的链接得到相同的分数,随机预测的W-index分数是0。另外,如果随机分布的分数是正常的,随机预测的W-index分数接近0.5,或者从离散均匀分布随机生成分数,W-index分数随机预测是一个正数小于0.5。简而言之,随机预测的W-index分数范围从0到0.5。(3)0.5点仍然是一个基准W-index分数,但它的意思已经改变。AUC指标下,0.5分意味着相同数量的成功与失败,也就是说,给分数由纯粹的机会。这意味着一个链接预测的性能比机会只有当其AUC大于0.5。与这个不同,根据W-index,纯机会的分数不再是一个固定值,但其上限是0.5分。因此,一个链接预测方法得分高于0.5必须比纯粹的机会。此外,当赢的数量等于平,损失的总和,W-index值是0.5分。很明显,竞争方法应该更胜比平,损失。综上所述,只有一个链接得分在0.5以上预测方法是有效的。度超过0.5,越大越好算法执行。

5.2。一般W-Index的解释

事实上,提出W-index厂商是一种特殊情况下的评价指标。在无向和未加权的图,我们可以作为链接预测二元分类问题,对所有节点分为观察边缘和未被注意的边缘。分类结果包括三种情况。第一个是正确的分类,即测试链接得分高于或未被注意的环节,即获胜。第二个是错误的分类结果,即损失,可以进一步细化为以下两个。一个是治疗观察边缘未被注意的边缘,命名L1,另一种是治疗未被注意的边观察边,命名L2。第三是它不能被分类,也就是说,有相同的分数的测试链接未被注意的链接,或者,即画。其中,后两个是分类的结果L1,L2和画会带来成本。

以蛋白质交互网络为例,我们来执行大量的昂贵和耗时的实验发现未知的交互。在L1小姐,我们实验我们应该执行和无法获得发现。在L2,我们做无用的实验,发现。在画中,我们需要执行所有实验,但这需要大量的时间和金钱。

W-index下,我们有相同的处罚这三个成本,也就是说,我们在平,得到0分的损失。然而,在不同的环境,不同的分类结果常常带来不同的成本。此外,我们可以专注于成本很高的情况下,使用分类结果的总成本作为评价标准。例如,我们给−10分L1。这样,虽然一个链接预测方法精度最高的AUC度量下可能被遗弃,在应用程序中具有重要的现实意义。

6。结论

在本文中,我们讨论两个副作用AUC的吸引并提出W-index,只关心谁获胜,获得有识别力的链路预测方法的评价。介绍了一系列的工具测量的可靠性和性能的新指标。基于经验数据,两种方法,即,ranking change and correlation analysis, are applied for comparative analysis to verify the reliability of the W-index. To evaluate the performance of the W-index, we utilize local and global distances to measure the differences between link prediction methods. Moreover, the impact of the network structure and training set length on the performance of predictors is clarified under W-index and AUC. These tools may shed light on the study of new evaluation metrics.

从我们的实验主要观察各种网络总结如下。首先,W-index能够有效评估的性能预测和AUC相比,这是由以下参数。链接预测方法的性能排名当使用W-index和AUC变化不明显,分别和相关性分析的结果W-precision和AUC-precision(见表4和5)也高度一致。下一个重要的观察是,使用W-index代替AUC评估链接预测的性能,这些方法之间的区别更明显,在本地和全球。然后,我们的结果显示社区信息的使用并不一定提高预测的性能。是否有效取决于它是如何利用。例如,W-form算法(即的性能。,CN-W,LHN-W,RA-W,和每各月) is not good, while ICRA always performs well. In addition, the performance of a link predictor is affected by the network structure, and our results in4.7节表明,网络的平均聚类系数的主要因素。

最后,我们要提醒读者,在1995年,足球联赛增加胜利的奖励从两到三分,这条规则变化的主要目标是鼓励更多的很让她兴奋和吸引她的比赛。此后,经验数据证明三点系统的引入减少了足球比赛的吸引和产生一个更正确的排名的团队49]。此外,每场比赛的进球总数也增加。灵感来自这个,我们希望我们的工作将有助于进一步研究和探索的链路预测方法更具竞争力。

数据可用性

在这项研究中使用的网络是可用的http://konect.uni-koblenz.de/networks/,http://networkrepository.com/,http://snap.stanford.edu/data/,http://vlado.fmf.uni-lj.si/pub/networks/data/,https://icon.colorado.edu/ # ! /。

的利益冲突

作者宣称没有利益冲突有关的出版。

作者的贡献

云元,精卫王同样贡献了这项工作。

确认

这项工作是支持部分由中国国家重点研发项目(批准号2019 yfb1704700),中国国家自然科学基金(批准号。61573257,71690234,71690234,61973237),和上海市科学技术委员会(批准号。19 jg0500700和20 jg0500200)。

引用

1. 诉马丁内斯、f . Berzal和j . c . Cubero“复杂网络链路预测的调查”,ACM计算调查卷,49号4、2017。视图:出版商的网站|谷歌学术搜索
2. j . Tang s . Chang c . Aggarwal h·刘,“负面的社交媒体链接预测,”WSDM ACM国际会议,第96 - 87页,上海,中国,2015年2月。视图:谷歌学术搜索
3. w .元,j .彭日成d关,y, a . Al-Dhelaan和m . Al-Dhelaan”信号预测标记学习社交网络使用分支界限法优化传输,”复杂性卷,2019篇文章ID 4906903, 11页,2019年。视图:出版商的网站|谷歌学术搜索
4. r . j . McAuley Pandey, j . Leskovec“推断的替代和互补产品,网络”21 ACM SIGKDD学报》国际会议上知识发现和数据Mining-KDD 15澳大利亚悉尼,页785 - 794,,2015年8月。视图:出版商的网站|谷歌学术搜索
5. 黄y, z沙j .索菲亚傅et al .,“一个基于网络的建模方法和预测产品coconsideration关系,“复杂性ID 2753638条,卷。2018年,14页,2018。视图:出版商的网站|谷歌学术搜索
6. w·l·梅·d·唐、t . Wang Du, y,和曹x”预测基础设施网络的演化过程与NSIPA链接预测方法,”IEEE电路和系统II:表达内裤,卷66,不。11日,第1899 - 1895页,2019年。视图:出版商的网站|谷歌学术搜索
7. t·t·p·苏萨和t .身上花费预测未来股票市场结构结合社会和金融网络信息,“自然史答:统计力学及其应用,535卷,2019年。视图:出版商的网站|谷歌学术搜索
8. j。梅,C.-K。Kwoh X.-L p . Yang。李,j .郑”药物相互作用预测通过学习从当地信息和邻居,”生物信息学卷,29号2、238 - 245年,2013页。视图:出版商的网站|谷歌学术搜索
9. 周赵x, y罗j . et al .,“网络集成方法对药物相互作用预测和计算药物从异构信息,重新定位”自然通讯,8卷,不。1,2017。视图:出版商的网站|谷歌学术搜索
10. 毛和f·肖,”一个新颖的方法,预测工程造价指数基于复杂网络,”自然史答:统计力学及其应用,527卷,2019年。视图:谷歌学术搜索
11. a . Brintrup p . Wichmann·伍德奥d·麦克法兰e .缺口和w·Krechel“预测供应网络中隐藏的链接,复杂性卷,2018篇文章ID 9104387, 12页,2018。视图:出版商的网站|谷歌学术搜索
12. j . Wang Q.-M。张,t·周“Tag-aware在复杂网络链路预测算法,”自然史答:统计力学及其应用卷,523年,第111 - 105页,2019年。视图:出版商的网站|谷歌学术搜索
13. 美国巴姨,l . Li j . Cheng徐,和陈x,“预测失踪链接基于新的三角形结构,”复杂性卷,2018篇文章ID 7312603, 11页,2018年。视图:出版商的网站|谷歌学术搜索
14. s . l . Li呗,m .愣,l . Wang和x陈,“寻找失落的环节在复杂网络:一个多属性决策方法,”复杂性卷,2018篇文章ID 3579758, 16页,2018年。视图:出版商的网站|谷歌学术搜索
15. M.-Y。周,h .廖W.-M。熊,X.-Y。吴,z。魏”,连接模式激励在复杂网络链路预测,“复杂性卷,2017篇文章ID 8581365, 12页,2017。视图:出版商的网站|谷歌学术搜索
16. Chowdhury s . n、d . Ghosh和c .母鸡”排斥链接对挫折吸引力耦合网络的影响,“物理评论E,卷101,不。2、2020。视图:出版商的网站|谷歌学术搜索
17. Haghani和m . r . Keyvanpour“系统性分析社交网络的链路预测”人工智能审查,52卷,不。3、1961 - 1995年,2019页。视图:出版商的网站|谷歌学术搜索
18. r . r . Junuthula k . s .徐,v . k . Devabhaktuni”评估链接预测精度在动态网络中添加和删除边”学报BDCloud IEEE国际会议,页377 - 384年,亚特兰大,乔治亚州,美国,2016年9月。视图:出版商的网站|谷歌学术搜索
19. y, r . n . Lichtenwalter n v·乔,“评估链接预测方法,”知识和信息系统,45卷,不。3、751 - 782年,2015页。视图:出版商的网站|谷歌学术搜索
20. r . Lichtenwalter n v·乔,”链接预测:公平、有效的评价,”学报ASONAM ACM国际会议土耳其伊斯坦布尔,页376 - 383年,2012年8月。视图:谷歌学术搜索
21. j . Herlocker j . Konstan l . Terveen, t . Riedl“评估协同过滤推荐系统,”ACM交易信息系统卷。22日,5-53,2004页。视图:谷歌学术搜索
22. a . Clauset c·摩尔,m·e·纽曼”层次结构和失踪链接网络的预测,”自然,卷453,不。7191年,第101 - 98页,2008年。视图:出版商的网站|谷歌学术搜索
23. j·戴维斯和m . Goadrich“precision-recall和ROC曲线之间的关系,”ACM国际会议的程序进行系列加拿大安大略省,第240 - 233页,2006年10月。视图:谷歌学术搜索
24. 诉Satuluri c . Wang,美国的高“本地链接预测概率模型”诉讼IEEE国际会议上的数据挖掘奥马哈,页322 - 331年,东北,美国,2007年10月。视图:谷歌学术搜索
25. r . n . Lichtenwalter j·t·西尔和n v·乔,“链接预测,新的视角和方法”第16届ACM SIGKDD学报》国际会议对知识发现和数据mining-KDD 10华盛顿特区,页243 - 252,美国2010年7月。视图:出版商的网站|谷歌学术搜索
26. d·戴维斯、r . Lichtenwalter和n v·乔,“Multi-relational链接预测在异构信息网络,”学报ASONAM ACM国际会议,页281 - 288,高雄,台湾,2011年7月。视图:谷歌学术搜索
27. j·a·汉利和b·j·麦克尼尔公司”的意义和使用接受者操作特征(roc)曲线下面积,“放射学,卷143,不。1,29-36,1982页。视图:出版商的网站|谷歌学术搜索
28. h·金和c x凌,“使用AUC和准确性评估学习算法,”IEEE工程知识和数据,17卷,不。3、299 - 310年,2005页。视图:谷歌学术搜索
29. s, p . Flach和c·费里,AUC的改进模型选择启发式,”机器学习:ECML 2007施普林格,页478 - 489年,柏林,德国,2007年。视图:谷歌学术搜索
30. c·费里·Flach j . Hernandez-Orallo, a . Senad“修改ROC曲线将预测概率,”学报第二车间机器学习的ROC分析德国波恩,页33-40,2005年9月。视图:谷歌学术搜索
31. t·考尔德和美国Jaroszewicz,“有效的分类、AUC优化”在数据库知识发现:PKDD 2007页42-53 Springer,柏林,德国,2007年。视图:谷歌学术搜索
32. l . y . Lu和t .周”,在复杂网络链路预测:一项调查,”自然史一,卷390,不。6,1150 - 1170年,2011页。视图:谷歌学术搜索
33. l, c·h·金,t·周“相似性指数基于局部路径复杂网络链路预测,“物理评论E,卷80,不。4 p。046122年,2009年。视图:出版商的网站|谷歌学术搜索
34. j .杜赫,a .竞技场。”在使用极值优化复杂网络社区探测物理评论E,第72卷,第027104页,2005年。视图:出版商的网站|谷歌学术搜索
35. m . Zanin d . Papo p·a·苏萨et al .,“结合复杂网络和数据挖掘:为什么和如何,”物理物理快报的评测报告部分卷。635年,在美国,2016页。视图:出版商的网站|谷歌学术搜索
36. 美国红肿,“梳理失落的环节,”自然,卷453,不。7191年,47-48,2008页。视图:出版商的网站|谷歌学术搜索
37. e . a•莱克特说,p .河中沙洲,m·e·j·纽曼“顶点相似性网络”物理评论E,卷73,不。2、2006。视图:出版商的网站|谷歌学术搜索
38. 周t、l . Lu和研究。张“预测失踪链接通过当地信息,”欧洲物理期刊B,卷71,不。4、623 - 630年,2009页。视图:出版商的网站|谷歌学术搜索
39. j . c . Valverde-Rebaza和a·德·安德拉德洛佩斯,”在复杂网络链路预测基于社区信息,”2012年人工Intelligence-SBIA进步施普林格,页92 - 101年,柏林,德国,2012年。视图:谷歌学术搜索
40. h . y . j . Wang, m . Liu元,w .沈,和l·李,“一个顶点相似指数利用社区信息改善链接预测的准确性,”学报2017年IEEE国际会议系统,人,控制论(SMC)加拿大班夫,页158 - 163,2017年10月。视图:谷歌学术搜索
41. w·刘和l·卢”链接预测基于局部随机游走,“EPL (Europhysics字母),卷89,不。5,2010。视图:出版商的网站|谷歌学术搜索
42. 下午格雷斯和l . Danon群落结构在爵士,”复杂系统的进展》第六卷,没有。4、565 - 573年,2003页。视图:出版商的网站|谷歌学术搜索
43. http://vlado.fmf.uni-lj.si/pub/networks/data/mix/USAir97.net。
44. l·a·亚当,”政治博客圈和2004年美国大选:划分他们的博客,”第三届国际研讨会上链接发现学报》上美国,纽约,纽约,2005年8月。视图:谷歌学术搜索
45. b . Rozemberczki r·戴维斯、r . Sarkar和c·萨顿“GEMSEC:图嵌入与自我集群,”学报ASONAM ACM国际会议加拿大温哥华,页65 - 72,2019年9月。视图:出版商的网站|谷歌学术搜索
46. r·a·罗西和n·k·艾哈迈德,”网络与互动图表分析和可视化数据存储库,”美国29日AAAI会议上人工智能美国奥斯汀,TX, 2015年2月,http://networkrepository.com。视图:谷歌学术搜索
47. 诉他们,J.-L。Guillaume、r . Lambiotte和e . Lefebvre“快速展开的大型网络社区,”杂志的统计力学理论和实验,2008年。视图:出版商的网站|谷歌学术搜索
48. K.-k。商,苏耿赋。李,m .小d·伯顿,y,“链接预测为树状网络,”混乱:一个跨学科的非线性科学》杂志上卷,29号6,061103年,页2019。视图:出版商的网站|谷歌学术搜索
49. 迪尔格h·盖尔,答:“是三分赢真的比两个吗?德国足球理论和实证证据,”SSRN电子杂志,2008年。视图:谷歌学术搜索

版权

版权©2020云元et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。