理论教育 如何选择预测器-《学术影响力的测评方法与实践》

如何选择预测器-《学术影响力的测评方法与实践》

时间:2023-10-06 理论教育 版权反馈
【摘要】:目前,Linkpred有18个预测器,其中几个有一个或多个参数。共同邻居预测器对邻居的规模是敏感的。因此,我们定义度数预测器为:请注意,式(2.5)潜在的假说几乎和式(2.2)潜在的假说相反,前者奖励高度数,后者惩罚它们。Guns讨论了基于集合的相似度计算的向量解释,Egghe、Michel提出了基于邻居的加权预测器的坚实的理论基础。现在让我们来看全局预测器。

如何选择预测器-《学术影响力的测评方法与实践》

目前,Linkpred有18个预测器,其中几个有一个或多个参数。在这里我们只介绍最重要的几个。我们分为本地和全局预测器。Linkpred中使用的大部分预测器,本地和全局,都有一个权变量和一个非权变量。

本地预测器只依赖两个节点的邻居节点。许多网络有一种三元闭包的自然趋势:如果两个链接a-b和b-c存在,则有一种趋势是形成闭包a-c。这一特性与同配性紧密相关,而且被Newman(2001)的合作者网络经验证实,Newman展示了两个研究者合作的概率随着他们共同作者的数量的增加而增加:例如,一对有五个共同作者的科学家合作的可能性是只有两个共同作者的一对科学家的大约两倍。可以通过共同邻居预测器来实现(Liben-Nowell,Kleinberg,2007):

尽管简单共同邻居已经在多种社会网络中被证实执行得很好,三元闭包证明是一种真正有力的机制。

共同邻居预测器对邻居的规模是敏感的。如果u和v有许多邻居,他们自然更可能有更多共同的邻居。因此,几种规范已经在文献中被介绍,如Dice的索引(Zhou et al.,2009)或者余弦度量(Spertus et al.,2005)。后者的定义如下:

其他可操作的规范包括Jaccard、最大和最小重叠、N度量和联系强度。因为它们在信息检索和匹配研究中经常被用作相关性度量(如:Ahlgren,Jarneving,Rousseau,2003;Boyce,Meadow,Kraft,1994;Salton,McGill,1983;VanEck,Waltman,2009),所以这些指标在信息科学文献中是相当有名的。在许多实证研究中,共同邻居的规范会对性能产生相反的作用。换句话说,两个有许多共同邻居的节点会自动地连接彼此,而不管它们共同邻居的总数。这一通则的一个例外是二分网,比如作者—文章网络,Guns(2011)显示,对这种类型的网络,余弦度量可作为一个好的预测器。

Adamic/Adar预测器开始于假说:一个稀疏(如,度数低)邻居比度数高的邻居更可能表明一个社会链接。它的原始定义来自于Adamic和Adar(2003),为进行链接预测被Liben-Nowell和Kleinberg(2007)改编:

一个非常相似的预测器是资源配置,是由Zhou等人(2009)提出的:

资源配置和Adamic/Adar预测器基于相似的假说,但是产生一个稍微不同的排序。实践中,这个预测器要比Adamic/Adar做得好。两者都倾向于强预测,胜过共同邻居预测器。

如果偏好连接是网络进化的潜在机制,那么可以看到节点u和v的度数与两个节点间连接的概率成正比(Barabási et al.,2002)。因此,我们定义度数预测器(也被称作偏好连接预测器)为:

请注意,式(2.5)潜在的假说几乎和式(2.2)潜在的假说相反,前者奖励高度数,后者惩罚它们。强烈建议:如果度结果作为一个预测器使用,共同邻居的规范格式将会有差的结果,反之亦然。然而,一些研究报告度结果的性能差(如:Liben-Nowell,Kleinberg,2007),其他的研究发现度结果是相对强的预测器(如:Yan,Guns,2014)。网络的内聚性和稠密度似乎是影响因素。

许多网络有加权链接。例如,在我们的案例研究中,链接的权重等于文章合作者的数量。在链接预测中考虑链的权重似乎是一个合乎逻辑的步骤。因此,这个主题经常被忽略是相当令人惊讶的(对一些例外,参见Murata,Moriyasu,2007;Lü,Zhou,2010)。Guns(2012)讨论了基于集合的相似度计算的向量解释,Egghe、Michel(2002)提出了基于邻居的加权预测器的坚实的理论基础。例如,余弦预测器的加权变量变为:(www.daowen.com)

对每个节点i,有一个相应的变量元素xi或yi。如果节点i连接着节点u,那么xi=wu,j,是u和i间的链接权重(对节点v和yi同样)。如果节点i没和u(或者v)相连,则相应的变量元素为0。这样一来,Linkpred实现了所有本地预测器的加权版本。

现在让我们来看全局预测器。即使两个节点没有共同的邻居,它们仍然可能发生联系并在后期形成链接。一种直接的关系度量方式是采用两个节点间的图距离:

在这里,d(u,v)表示从节点u到v的最短路径长度。如果考虑链接权重,图距离可以这样定义:

在这里,wi(i=1,…,t)表示在最短路径中(u和v之间的距离t)第i个链接的权重。加权图距离与不加权图距离相比,是更好的预测器(Guns,2012)。

1953年,Leo Katz提出了一个中心性预测器,目的是为了克服度中心性的局限(Katz,1953)。让我们用A表示网络的全邻接矩阵。如果在节点vi和vj间有个链接,则元素aij是1;如果没有链接,则为0。Ak(A的第k次幂)中的每个元素有一个值,等于从节点vi到vj、长度为k的步数(Wasserman,Faust,1994,p.159)。Katz预测器被定义为:

总之,步数长表明从开始节点到结束节点间是一个较弱的连接。Katz(1953)因此提出一个参数β(0<β<1),表示一个单独链接有效性的概率。因此,长度k的每一步都有一个有效概率βk。潜在的假设是两个节点间步数的多少表明了两节点间联系的强弱。Guns和Rousseau(2014)提出Katz预测器的加权变量在多图的环境中能最好地被描述,一个网络中一对节点能被多重链接连接。这种预测器是Lindpred所有预测器中最成熟和执行最好的预测器之一。

PageRank以它在Google搜索引擎中的应用而闻名(Brin,Page,1998)。假设存在一个随机漫步(一个随机的Web冲浪运动员,Page,Brin,Motwani,Winograd,1999),从一个随机节点开始,随机选择一个它的邻居并导航到其邻居节点,如此类推。而且,在每个节点,漫步者很少有机会被传送到网络中其他的随机节点。前进到一个邻居的概率是α(0<α<1),传送的概率是1-α。我们能决定漫步者在一个给定节点的概率。一些节点比其他节点更重要,这些节点将会有一个高关联概率。概率值等于节点的PageRank。Rooted PageRank是PageRank的一个变量,表示随机游走以同一种方式穿越网络,处理传送不是随机的,漫步者总是被传送回同一个根节点。关联的Rooted PageRank值能被解释为其他节点与根节点关联度的预测器。

SimRank是网络中两个节点间相关性的度量,由Jeh和Widom(2002)提出。SimRank的观点可以被总结为:链接到同一个节点的节点是相关的。为了计算SimRank,我们假设任一节点与自己是最大相关的,sim(a,a)=1。无权公式由Antonellis、Molina、Chang(2008)提出:

在这里,c(0<c<1)是衰减系数,决定着相关度以多快的速度衰减。有趣的是,SimRank的作者明确地承认它具备文献计量的遗传。他们把SimRank作为一种普遍的共引行为,也考虑引用文献的相关性,依此类推。这样归纳尤其对那些邻居节点少的节点(比如,文章很少引用)有利(Jeh,Widom,2002)。Rooted PageRank和SimRank的性能似乎在不同的研究中也不同,甚至胜过其他预测器,其关键是要仔细地调整参数。而且,有些研究使用无权计算版本,但是,加权的版本在大多数例子中性能更好。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈