复杂网络中的链路预测：偏好随机游走算法

半]沙特国王大学学报复杂网络中通过相互影响节点进行链路预测的偏好随机游走算法Kamal Berahmanda，Jiang，Elahe Nasirib，Saman Forouzandehc，Yuefeng Liaa澳大利亚布里斯班昆士兰科技大学科学与工程系b伊朗大不里士阿塞拜疆沙希德马达尼大学信息技术和通信系c德黑兰市ICT组织中心应用科技大学计算机工程系，伊朗德黑兰阿提奇莱因福奥文章历史记录：收到2020年2021年5月15日修订2021年5月15日接受2021年5月20日网上发售关键词：复杂网络链路预测局部随机游走有偏随机游走A B S T R A C T在过去的几年里，预测复杂网络中的链接一直是数据挖掘和科学发现领域的重要课题之一这个问题仍然是试图使用图中现有的链接来识别未来的、已删除的和冗余的链接。局部随机游走被认为是拟局部方法中最著名的算法之一。它采用传统的有限步随机游走遍历网络，在每一步中从重要性相等的节点中随机选择一个相邻节点。然后利用节点间的转移概率来计算节点间的相似度.然而，在大多数数据集中，该方法无法准确地对非常相似的节点进行评分。本文提出了一种改进局部随机游动的有效方法，即在每一步中，鼓励随机游动向影响力较大的节点移动。因此，根据源节点的影响来选择下一个节点。为此，利用互信息，节点的非对称相互影响的概念。所提出的方法和其他基于相似性的方法（本地，准本地和全球）之间的比较已经进行，并已报告的结果与其他链路预测方法相比，该方法具有更高的预测精度.版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY许可下的文章（http://creativecommons.org/licenses/by/4.0/）。1. 介绍复杂网络可以描述当前的许多自然现象，包括生物网络、大脑网络以及技术时代的人为现象，如社交网络、交通网络等。这使得网络科学在当今时代成为一个热门的、广泛的、跨学科的领域。有许多问题，如社区检测（Kazato，2010年;贝拉赫曼德例如，2018,2020;Berahmand和Bouyer，2018），识别扩散器节点（Berahmand等人，2019年，2018年），最大影响（Berahmand等人， 2018年）和链接预测*通讯作者。电子邮件地址：kamal. hdr.qut.edu.au（K. Berahmand），el.azaruniv.ac.ir（E.Nasiri），Saman. gmail.com（S.Forouzandeh），y2.li @ qut.edu.au（Y. Li）。沙特国王大学负责同行审查制作和主办：Elsevier（Nasiri等人， 2019年），在这些复杂网络的中心，这被认为是主要的挑战。链路预测是复杂网络分析中的一项重要任务链路预测方法使用过去的数据来预测复杂网络的未来结构。对于给定的社交网络G，它可以被公式化为未在G1/2t0;t00]中提供、但被 预测为存在于G1/2t1;t01]中的边的列表的预测，其中G 1/2t;t0]意味着G在1/ 2t;t0]的时间戳间隔处的子图。 训练间隔由1/2t0;t00]表示，并且t1; t01被称为测试间隔。它旨在预测网络当前结构中缺失的、虚假的或新的链接（Martínez等人， 2017年）。这是一个通用的任务，用于分析网络化的数据，出现在应用和理论分析，新的友谊，并推荐可能的朋友在社交网络包括Twitter和LinkedIn。在生物网络中，它可以用来恢复对蛋白质功能的思考和理解，发现未知的蛋白质理论分析中的链接预测有助于理解信息传播和扩散的机制（Wu等人， 2019年）的报告。最近提出了许多链接预测算法。基于节点相似性的三类算法（Lihttps://doi.org/10.1016/j.jksuci.2021.05.0061319-1578/©2021作者。由Elsevier B.V.代表沙特国王大学出版。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comK. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5376ð - Þ例如，2020; Leicht等人，2006; Zhou等人，2009;Liben-Nowell和Kleinberg，2007）、最大似然算法（Clauset et al.，2008）和概率模型（Airoldi，2008）是这些算法的分类。特别是基于相似性的算法是解决链路预测问题的最有效和最基本的方法之一。 在该方法中，对于每一对顶点i和j，计算得分（sij），其示出两个顶点i和j之间的相似性。一般来说，两个节点之间的相似性定义如下：两个节点在具有许多共享特征的情况下具有相似性。根据时间和空间复杂度，相似性指数分为局部、准局部和全局三类（Kumar，2020）。局部相似性指数利用节点邻居的结构信息来计算节点之间的相似性，而不需要整个网络的结构信息。与全局相似性索引相比，该方法速度更快，并且可以在运行时以并行方式使用。局部相似性指数的主要弱点是它们只能使用来自一级和二级邻域的局部信息。然而，大多数链接发生在具有两个以上节点的路径中（Kumar，2020）。全局相似性指数使用来自整个网络的结构信息来对边缘进行评分，并且它们在大型网络中的计算复杂性使得它们效率低下。此外，它们不能以并行模式运行。然而，与局部相似性指数相比，它们具有更高的准确性。另一方面，准地方相似性指数能够在这两个指数之间建立平衡。它们比局部索引使用更多的信息，并且与全局索引不同，它们不使用冗余信息，这不影响准确性（Wang等人， 2015年）。近年来，随机游走算法一直是研究人员的兴趣之一，因为其易于解释（Zhou等人，2018; Xia，2019）。从实践的角度来看，随机游走在计算机科学领域有几个有用的应用，例如链接预测（Liu和Lü，2010;Curado，2020; Tong等人，2006）、社区检测（Su等人，2017;Pons和Lattero，2005）、网络嵌入（Perozzi等人，2014; Grover和Leskovec ， 2016 ） ， 推 荐 系 统 （ Gori 等 人 ， 2007 ） 和 网 络 扩 散（Masuda等人， 2017年）。图和起始节点是在基于随机行走的方法中给出的。在图上的整个行走过程中，行走者在每一步都随机移动到当前节点的一个邻居。在此过程中构造一个节点序列，该节点序列确定图的遍历。随机游走是基于相似性的主要方法用于链接预测，它通过以全局和准局部方式随机遍历图来检测节点之间的相似性。在全局方式中，使用具有重新开始算法的随机行走，行走器通过采取随机步骤从第一顶点开始遍历，并且以概率c随机地到达第一顶点的邻居之一，并且以概率Ic返回到第一顶点（Tong等人， 2006年）。对于i和j对，该索引的值等于该随机游走者从顶点i开始并在等限状态下位于顶点j的概率。这种方法对于当今庞大的网络来说并不是很有效，因为它的高复杂性和全局信息。然而，局部随机游走（LRW）（Liu和Lü，2010）算法将随机步数限制为l，并且通过应用该限制，该方法不再对平衡具有任何控制。大多数用于随机游走的方法都是使用纯游走来解决链接预测问题。由于在纯随机游动中，所有节点和链路的重要性被同等地考虑，因此所获得的结果将不足以准确地识别节点对的相似性。为了解决上述问题清楚，一个修改版本的LRW算法的建议。由于LRW是使用纯随机行走进行的，并且基于随机方式选择目的节点，因此其进一步的步骤取决于节点邻居。在决定下一步的决策过程中，LRW使用其度随机选择一个邻居如果LRW精确地选择一个具有更显著概率的邻居，节点相似性的准确性将得到提高。为了提高LRW的性能，提出了节点间非对称相互影响的概念这个概念表达了节点对彼此的影响是不对称的。使用这个概念，遍历器使用其对当前节点的影响来选择下一个节点，并为下一步选择更有效的路径。这个过程有助于更精确和有效地遍历网络结构。因此，具有更显著的结构相似性的节点将在所提出的算法中获得更高的分数因此，我们提出的算法，称为相互影响随机行走（MIRW），将通过更有效的路径。与其他算法相比，该算法利用了准局部信息和线性时间复杂度，具有更高的精度和效率.本文的其余部分组织如下。第2总结了复杂网络中链路预测的相关研究，以及现有的节点相似性度量方法。第三部分介绍了本文的一些基本概念，包括互信息、互影响、偏好链的定义，以及一种新的基于互影响的局部随机游走方法，该方法用于度量复杂网络中节点的相似性。第4节给出了实验分析和仿真结果。最后，第5给出了结论。2. 相关作品最近，已经实现了许多用于链路预测的算法，并且已经有几个用于链路预测问题的优秀调查（Martínez等人，2017;Kumar，2020;Wang等人，2015; Pech，2019）。可以为这些方法提供几种分类，例如基于相似性的算法、最大似然方法和概率模型。最大似然方法和概率模型提供比基于相似性的算法更高的准确性;然而，它们具有一些固有的缺点（Clauset等人，2008年）。除了网络结构之外，概率模型通常还依赖于节点属性，因此它们的应用受到相当大的限制（Leicht等人，2006年）。此外，要固定的参数的数量太大，结果，尽管建立了一个相当精确的模型，但我们无法深入了解网络组织。最大似然方法在时间消耗方面不是很有效，并且它们只能处理具有数百个节点的网络（Newman，2001）。相比之下，许多真实网络包括从数百万到数十亿的不同数量的节点。在本文中，我们只强调基于结构的相似性方法使用结构拓扑信息。利用网络的拓扑结构特征，采用基于结构的相似性方法，对不连通的节点对进行相似性评分。这些方法可以分为三类：局部、准局部和全局（Perozzi等人，2014年）。因此，总体而言，基于相似性的算法，特别是仅基于准局部拓扑信息的算法，得到了最广泛的应用。局部相似性方法仅使用长度为2的路径的信息，K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5377ð - ÞðÞðÞðÞ一对节点。它分为两个主要的分类，共同的邻居为基础的和基于聚类系数的方法。 在基于公共邻居的类别中，如果两个断开连接的节点具有更多的公共节点，则它们更有可能相互连接，例如直接计数公共邻居节点的数量的公共邻居索引（CN）（Adamic和Adar，2003）、Adamic-Adar索引（AA）（Sørensen，1948）和资源分配索引（RA）（Zhou等人，2009）惩罚大型公共邻居节点，Sørensen指数（Cannistraci等人，2013）、Leicht-Holme-Newman指数（Leicht等人，2006年），具有大度数端点的惩罚。基于CAR的公共邻居指数（CAR）、节点聚类系数（CCLP）、节点和链路聚类系数（NLC）等方法不仅考虑了节点对的公共邻居，而且还考虑了这些公共邻居之间的局部聚类系数。在该论文中（Wu等人，2016），作者考虑了共同邻居之间的边的数量，并且基于以下假设提出了CAR指数：如果两个节点的共同邻居是本地社区的成员，则两个节点之间存在边的可能性更大Wu等人（Wu等人，2016）设计了CCLP指数。该指标也是基于网络的局部计算种子节点对的所有公共邻居的局部聚类系数并求和以计算该对的最终相似性得分。同一作者开发了NLC索引，其中结合节点和链接聚类信息以找到最终的相似性（Katz，1953）。局部相似性指数的主要优点是计算复杂度低。尽管如此，考虑到直接邻居导致该指数在预测中表现较弱。相反，全局相似性根据网络的全局结构信息指出相似性，包括Katz指数（Lü et al.，2009），对其中期望具有较短路由的两个节点的连接的所有路径进行计数。重启随机游走（Random Walk with Restart，RWR）是PageRank算法的直接应用（Tong等人，2006年）。考虑从节点i开始的随机步行者，他将以概率c迭代地移动到随机邻居，并以概率1c返回节点i。用qij表示这个随机游走者在稳态时位于节点j准局部索引不依赖于全局信息，但与局部方法相比，它们使用额外的拓扑信息，局部随机游动（Liu and Lü，2010）和叠加随机游动（SuperposedRandom Walk，SRW）（Liu and Lü，2010）指标是两个著名的具有有限步相似性指标的随机游动。局部随机游走指数将随机游走器限制在局部范围内，基于局部随机游走的叠加随机游走指数将随机游走器在起始节点处不断地叠加，以强调目标节点附近的半局部方法提供了计算复杂度和所获得的精度之间的折衷。因此，它们被认为是处理链路预测问题的最有效的方法之一在半局部方法中，局部随机游走算法是非常流行的，并且在寻找一对节点之间存在链接的概率然而，该算法在准确性方面存在显著的缺陷在所有使用随机行走方法的链接预测方法中，所有链接和节点的重要性被认为是相等的，这使得这种方法在遍历图结构时效率不高在这里，我们采取了与以前的作品不同的方法在目前的工作中，我们打算利用一个新的概念，即，相互影响，以计算节点对之间的转移概率，并且因此不以纯粹随机的方式选择随机我们声称，我们提出的算法是最有效的算法之一，在半本地类别，由于其高性能的链接预测任务，从大规模数据集上进行的实验所获得的结果的基础上。3. 该方法3.1. 背景和注释在本节中，在讨论算法之前，先回顾一下所提出的算法中的一些基本定义和概念。3.1.1. 定义1（相互信息）在信息论中，互信息是一个概念，它是一个随机变量关于另一个变量的信息量的度量，也用于指示节点信息之间的关系。考虑一对随机变量X和Y，其具有联合概率质量函数 Pxy 和边际概率质量函数 Px和 py（Hangal，S.，ACM KDD。，2010年）。互信息MI X;Y可以表示如下：性能 这种方法可以分为两类MI=X;Y=X XPxyωlogPxyð1Þ局部路径和有限步随机游动。采用所有2步和3步路径的信息，首选所有2步路径X2Xy2Ypxωpy在 本 地 路 径 （ LP ） 中考虑（ Yao 等 人 ， 2018 年 ） 。 有 效 路 径（EP）、重要路径（SP）和短路径资源（RSP）（Zhu等人，2014）是LP的改进版本。Xuzhen等人研究了端点的有效影响并捕获了连通性，并提出了EP，其中创建两个节点之间的影响模型作为路径的连通性，其中它被定义为路径中包括的每个单个链路的传输概率的乘积（Zhu等人，2014年）。Zhu等人提出了SP指数，该指数源于直觉，即短路径可以更好地证明连接其两端的缺失链接（他们表示这种路径是重要的）;低度中间节点是示例。实际上，重要路径索引仅适用于长度为2和3的路径（Ver Steeg和Galstyan，2013）。Yab-ing等人（Zhu等人，2014）基于网络上的资源-业务流机制，考虑了不同长度路径之间的相互作用，提出了RSP指标。在图上随机行走的有限步随机的MI X;Y衡量的是通过网络获得的信息量，将每个随机变量相对于另一个随机变量进行比较，并且具有三个显著特征：MI（X;Y）总是非负的。MI（X;Y）为零当且仅当随机变量X和Y相互独立。MI（X;Y）= MI（Y;X）实际上，互信息是对称函数。因此，MI X;Y的上述性质可以度量随机变量X和Y之间的线性和非线性相关性的结果。3.1.2. 定义2（非对称相互影响（AMI））在社交网络中，节点具有不同的影响力和重要性值，并且每个节点都可以影响其邻居或被其邻居影响。社会影响力的概念影响了各种各样的人，●●●K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5378IjN266IjPInvestj;kkCj（二;三2）N社交网络互动的各个方面，可以从Pi j<$PiCNi;j4c型不同的视角。 在这里，我们正在调查它在链接预测问题。更确切地说，我们利用Pk2CjCNj;k相互影响的概念来衡量一个节点可以影响它的邻居多少，并使用节点之间的影响来处理链接预测。这一概念将使用AMIi;jPijPijωlogpωp联系我们网络引入一个量来表示节点的相互影响，其使用等式（1）中提出的称为“互信息”的概念我们根据我们的目的修改了这个定义。因此，我们使用它们的一阶邻居和这些节点的交集来测量一对节点两个节点之间的相互影响使用等式（2.d）计算：Pi¼Ni2aNjPj2b其中Pij，即，i和j的联合概率是i和j之间的公共邻居的数量与节点j和它的所有邻居之间的公共邻居的总数mul之比。由Pi叠加，Cj表示节点的一阶邻域j五。 使用这个方程意味着节点的影响给它的邻居的信息不仅取决于它与该邻居的公共邻居的数量更具体地，在等式（4.d）中，当节点i和j具有低度和许多相互共享的邻居时，节点i和j此外，当节点i和j具有高度并且没有相互共享的邻居时，节点i和j的最小得分达到;在这些条件下，它们将彼此独立并且不会受到彼此的影响考虑4PCN=2c，图1中的以下网络作为示例，其中PCN=2c，联系我们NÞPE¼2，CNA;EE¼3，Pk2CACN=A;k=10和Pk2C电子CN2007;k20076.PijMIi;jPijωlogpωp2012年因此，我们可以看到节点E受到的影响最大节点A受到的影响最小，而节点A受到的节点E的影响最小。这是由于节点E具有较低的度其中Ni是节点i的一阶邻居的数量，N表示网络中节点的总数。Pi是指节点i从网络的其他节点获得影响CNi;j是指除了两个节点之外，直接连接到节点i和j的节点的数量，并且Pij意味着节点i和节点j的交点的出现概率。实际上，Pij是使用节点i和节点j的共同邻居的计数除以网络中节点的总数计算的概率，并且它可以被解释为节点对i和j受到网络中一组共同节点的影响。这个公式测量了一对节点之间的相互影响，用它们共享的邻域的分数表示因此，一个节点对它的邻居的影响等于它从邻居那里得到的影响但我们知道，在现实生活中，这不可能是真的。根据（Rossi和Ahmed，2015），一对社会实体之间的影响力概念是一个不对称的值，它取决于各种因素，例如，个人在网络中的重要性和作用。我们假设一个节点对其邻居的影响力越大，它被该节点访问的机会就越大。Hangal 等人（ Rossi 和Ahmed ，2015）提供了两个实体之间影响力的定量定义，如下所示：并且除此之外，与节点A及其相邻节点之间的公共邻居的数量相比，与其相邻节点共享更少的公共邻居，因此，与A在节点E上的投资相比，在A上投资更多的资源3.2. 相互影响随机游走算法顶点之间的结构相似性通常是隐藏的，它利用图的拓扑和结构信息来识别节点之间的相似性如果两个节点之间的结构在基于随机游走的方法中，如果网络的结构被更有效地遍历，则节点之间的相似性得分被更准确地计算局部随机游走和叠加随机游走是随机游走方法中最有效和高效的例子。与其他基于随机游走的方法相比，它们具有显著的优势随机带重启行走，也就是说这些方法利用了网络的准局部信息。因此，它们显著降低了计算复杂性。LRW和SRW的主要贡献是限制了步行者可以采取的步骤该方法影响力Investj;i2ð3Þ转移概率矩阵，即;PR，可以使用以下规则计算：i对j的影响是用j对i的投资额除以j对所有其他实体的投资额来确定的投资的概念可以解释为PRij¼1如果i j E度0否则ð6Þ一个人花在另一个人身上的时间或精力。在本文中，我们利用了（Rossi和Ahmed，2015）提供的概念，并对其进行了修改，使其适用于我们的目的。新的非对称相互影响是等式（2.d）的非对称版本，通过以下等式计算：在得到转移概率矩阵后，从节点i开始并在t之后到达节点j步骤可以计算如下：pi;jt-1pi;jt-1在上述设置中，pi0是一个N×1向量，其中第i个元素NiPi¼N4a等于1，其他的都等于0。因此，根据LRW，使用以下公式计算一对节点之间的相似性：Pj<$Nj14betsLRW不含硫量ki：p王空军中文（简体）ðtÞ ð7ÞNij2 jEji;j2 jEjj;iK. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5379不IJωijl¼12jEjj s CAMIij2jEjj s C 阿蜜记IJIJjsCi Pijωlogpiωpj图1.一、A. 在推断不对称相互影响B之前。在推断不对称相互影响之后。其中k和E分别被称为网络中节点的度和SRW通过不断释放步行者改善了LRW更有可能向受其影响更大的节点移动。MIRW算法使用等式（10）来定义：从源节点，导致之间更高的相似性彼此靠近的节点对相似性源于SMIRW最大值kiAMIij：P拉吉王空军ðl Þþ阿蜜记：P拉吉2019年10月10日SRW方法可以如下获得：sSRW不超过1000XsLRW不超过1000l¼1通过为每对顶点（i，j）定义适当的权重，步行器从一个节点跳到相邻节点，其具有朝向具有更高权重的链路的优先权的伪代码所提出的方法如下。尽管LRW和SRW具有计算复杂度低、预测丢失链路准确度高等优点，但与以往的研究相比，它们的主要缺点是转移概率矩阵的计算过程仅根据源节点的度，因此随机游走的结果完全是随机生成的，在捕捉网络结构和寻找节点间相似性方面不够准确。然而，网络中的每个节点在其邻域中可以具有特定的重要性，并且不应该像其他节点一样对待。为了克服这个限制，我们提出了一个偏置函数来区分节点与其邻居的每一个关系本文中引入的偏置函数利用了互信息概念。这种方法测量了每个节点对其邻居的影响。因此，步行者位于节点中的概率，选择其邻居之一进行下一步，与它从该邻居获得的影响成比例地计算节点对之间的相互影响可以通过等式（3）计算。如前所述，这个概念是对称的，并假设一个节点对其邻居的影响等于它从邻居那里得到的影响。然而，为了更有效地产生我们的偏置函数，我们需要考虑节点对彼此的影响是不对称的，并且更喜欢使用AMI而不是MI。这样，从节点i向节点j移动的概率与从节点j向节点i移动的概率不同。因此，作者使用等式（4.d）来计算每对节点的转移概率。因此，我们根据等式（9）引入新的矩阵变换。通过这种方式，通过调整偏置函数的参数，可以强制行走优先访问具有高非对称相互影响值的节点算法1-MIRW相似性的实现过程输入：G=（V，E），n=| V|，m=| E|输出：AUC和精度开始算法1：将原始网络G划分为训练集G train和测试集G test 2：对于Gtrain中的每对节点（i，j）do3：计算非对称相互影响（i，j）4：结束5：对于G train中的每对未连接的节点（x，y）do6：使用等式（6）计算边（x，y）的相似性得分为Sxy。7：End For 8：以降序排列所有S xy的列表9：将排序列表中的顶L边插入G列。//L是从原始网络中移除的边的数量10：计算AUC和精度11：结束算法4. 实验分析在本节中，为了研究所提出的方法的效率，作者进行了一些实验，并报告了他们的结果。所提出的方法这些方法根据网络的结构分为在以下部分中，我们将详细介绍用于性能分析的数据集所有的实验都是在一台配备四核Intel i7的2.20 GHz处理器和16 GB RAM。公司简介^^联系我们PlogPijpiωpjAMIij¼ð9Þ4.1. 数据集联系我们t=1tP.PijPAMIij所提出的方法在真实世界的数据集上进行了评估这些真实世界的网络有一些特点，包括数量，我们提出的算法（相互影响随机游走）允许使用一个不对称的相互影响矩阵。是节点、边的误码率、平均聚类系数、平均最短路径等。有关这些属性的详细说明，请参见jsCiK. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5380喜喜þ¼;表1.表1中从左到右的列分别为：网络名称、节点数（|V|），边数（|E|）、平均度（K）、平均聚类系数（C）、平均最短路径长度（ASPL）、直径（D）。每个数据集都已收集具有比不存在的边缘更高的分数，并且从不同的领域进行研究和分析。扎卡里空手道俱乐部是一个由一所大学的34名成员组成的网络AUCn0：5n}联系我们12Þ空手道俱乐部，每条边描述了一种友谊关系（Girvan和Newman，2002）。 足球也是大学球队之间的足球比赛的网络（Lusseau等人，2003年）。海豚是一个网络，代表了一些海豚之间的关系（瓦茨和斯特罗加茨，1998年）。CELEGANS是线虫的神经网络（Coleman等人，1957年）。PHYSICIANS是一个由246名医生组成的网络，他们是朋友或相互信任（Melián和Bascompte，2004）。食物是一个食物网，128个节点和2075条边（Dorsey，1991）。SmaGri是一个引用网络，其中节点是文档，如果一个文档被另一个文档引用，则会形成一个链接（Bu，2003）。酵母是描述蛋白质之间相互作用的网络（Newman，2006）。NetS-cience是一个连接科学家的合著网络（Datasets，2015）。King James是在相同句子中共同出现的词汇网络（Leskovec等人， 2007年）。CA-GrQc是一个合作伙伴-如果链接预测模型随机地给未观察到的链接打分，那么AUC将等于0.5。因此，如果结果得分高于0.5，则意味着模型的性能优于随机性能。4.2.2. 精度精度度量用于衡量模型正确预测缺失边缘的程度。换句话说，精度是用于测量模型的准确性。为了衡量模型的精度，首先，我们需要使用它们的给定分数按降序排列所有未观察到的边缘然后在得分最高的前L个节点对中，我们计算缺失边的数量。假设Lr缺失边存在于顶L节点对中这意味着模型的精度等于：网络覆盖了作者论文之间的科学合作精度LrLð13Þ4.2. 评价标准为了评估所提出的方法与比较方法的效率，我们需要一些评估指标来衡量每个方法的工作情况。这里使用的两个指标是受试者工作特征曲线下面积（AUC）和精密度。在下面的小节中，我们分别简要介绍每个指标，然后描述评估过程。4.2.1. AUC（Chowdhury，2010年）AUC是用于测量方法区分缺失环节的最常见指标，即，将在未来出现的链接，以及不存在的边缘，即，一对不相连的节点几乎所有的链接预测方法都使用这个度量进行了评估。理论上，该度量使用它们的给定分数对所有未观察到的链接进行排名。然后，它对随机选择的缺失边缘与随机选择的不存在边缘具有较高一致性的次数进行计数。这是一个耗时的过程，所以在实践中，当我们想评估一个方法而不是对所有未观察到的边进行排名时，每次我们只是随机选择一个缺失的边和一个不存在的边，并比较它们的得分。在n次独立比较中，如果n4.2.3. 随机游走长度根据（Liu and Lü，2010），平均最短路径距离与适当的步行长度之间存在正相关关系。因此，我们找到最佳值的随机游动长度相对于平均最短路径。4.3. 比较方法：为了评估我们提出的方法，我们考虑了来自不同类别的几种基线和最先进的链接方法，即，局部、准局部和全局。本节将介绍这些方法。当地方法：Jaccard系数：该方法使用节点对共享的公共邻居相对于其邻居总数的分数来计算节点对的相似性。一对节点的Jaccard系数可以如下计算（Ou等人， 2007年）：JC i jCi\Cj西印度群岛Ci表示节点i2V的一阶邻域。表1真实世界基准网络的拓扑细节网络|V||E|ASPLD1空手道34784.58800.5882.40852足球11561310.6610.4032.50843海豚621595.12900.3033.35784切莱甘斯297214814.4650.3082.45555医生24110989.11200.2512.49056食品128207532.4220.3351.77637斯迈格里102449169.60200.3492.98168酵母237511,6939.84700.3885.09159网宿146127423.75000.8785.821710国王詹姆斯1733913118.5000.1633.38811CA-GrQc524214,49660.5297.6017●K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5381表2不同算法的AUC结果与所提出的方法进行比较当地准局部全球提出网络JCRAAACCLPLPLRWSRWRWRMIRW空手道0.74640.76390.77330.84040.78980.86290.86480.80560.9057足球0.64430.63850.63860.82140.84720.83800.84330.84200.8603海豚0.70880.70780.70920.74600.78060.77860.78030.73630.8001切莱甘斯0.80000.87670.87190.86700.86480.86660.86970.86970.8905医生0.73040.72470.72400.85290.92780.90940.85640.92560.9337食品0.64950.61950.60710.63230.65800.61020.62450.61030.6761斯迈格里0.79080.84770.84320.86420.90590.92440.86760.93120.9247酵母0.91160.91340.90830.90900.95600.96320.91150.86840.9705网宿0.68340.65240.64240.91180.99500.91490.99240.99650.9976国王詹姆斯0.93990.94580.92340.94800.95270.94140.98430.98020.9862CA-GrQc0.83370.84620.83410.92630.96680.91720.96980.96980.9837图二. 所提出的方法与局部方法、准局部方法和全局方法的ROC曲线比较。K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5382图2（续）K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5383XÞþ不2;;● 资源分配：该指标还利用了低压¼A 阿瓜拉A公共邻居的概念来计算一对节点之间的相似性，但以更高的程度惩罚公共邻居。一对节点的资源分配可以如下计算（Zhou等人，2009年）：RA i j1z2jCi\CjjCzjAdamic-Adar系数：这个指标的工作方式与资源分配类似，Adamic-Adar系数计算如下[58]：AA i j1z2jCi\CjjlogjCzjCCLP：该度量还使用节点对的公共邻居，但是不是同等地考虑所有公共邻居，而是使用该节点的聚类系数来为它们分配权重。一对节点的CCLP计算如下（Wu等人， 2016年）：其中A是邻接矩阵。全局方法重新开始的随机游走（Tong等人，2006）：在该方法中，为了找到节点与其他节点之间的相似性，从该节点开始随机游走，并且在每一步中，游走器使用边的转移概率来决定下一个节点。此外，步行者可以返回到具有概率的开始节点一个人的最后，开始节点和其他节点使用到达该节点的概率来确定节点4.4. 实验结果为了评估我们提出的方法与其他方法的对比，我们从数据集中随机删除10%的边缘，并将其视为缺失边缘。剩下的90%的边由训练集组成然后，我们考虑所有其他节点对，不连接作为不存在的边缘。这两组边的并集形成未观察到的边集。在使用每种方法计算所有未观察到的边缘的得分后，我们使用AUC和精度来评估该方法。对每个数据集重复此过程十次，并将其平均值报告为最终结果。CCLP中国z2jCi\Cjj阻尼系数z表2展示了我们提出的算法和其他比较方法在11个真实世界数据集上的结果。每个数据集获得的最佳AUC已在中突出显示准局部方法：局部随机游走：这个相似性指数使用随机游走，并使用局部随机游走来测量一对节点之间的相似性（Liu和Lü，2010）：S LRW¼ki ：pijtkj ：pjit大胆点很明显，虽然准局部方法，即，LRW、SRW和LP，以及全局方法，即，与局部方法相比，RWR在JC、RA、AA和CCLP，它们几乎对所有网络都取得了显著的结果优势例如，在医师网络中，全局和准局部方法实现了比局部方法高10%以上的AUC一致将所提出的方法与i;j2jEj2jEj其他方法，我们知道，MIRW有显着超过-在这个公式中，pxyt是在t步中从节点x到达节点y叠加随机游走：这种方法使用局部随机游走，但给附近的节点更多的分数（Liu和Lü，2010）。SSRW¼XSLRW双螺杆挤出机形成了局部、准局部和全局的方法，证明了MIRW在所有方法中具有巨大的优势。特别地，与全局方法相比，即，RWR，空手道、海豚和酵母网络的AUC分别提高了10%、7%和11%，这是显著的。与局部方法相比，该方法具有很好的性能.例如，在足球、海豚和SmaGri网络中，AUC分别增加了22%、10%和8%，这意味着MIRW的性能大大超过了所有基准i;jl¼1i;j当地方法。此外，与拟局部方法相比，所得结果也是十分显著的。具体来说，在本地路径：这是一个基于路径的方法，它使用带有长度为2和3的路径来计算节点对之间的相似性，但是长度为2的路径更重要（Yao等人，2018年）。在大多数网络中，MIRW的性能同时显著优于LRW和SRW，除了KingJames和NetSi cence，其中MIRW的性能具有竞争力。这是非常重要的，因为它证明了使用表3与所提出的方法相比，不同算法的最高精度结果当地准局部全球提出网络JCRAAACCLPLP LRWSRWRWRMIRW空手道0.00000.19990.22850.05710.31410.25710.36980.3999足球0.34740.29170.29170.00001999年0.29500.21960.3802海豚0.20340.06660.13330.07000.2033 0.16660.06660.13330.2077切莱甘斯0.13330.09800.13660.13000.1400 0.14330.15660.13000.1625医生0.11950.17390.15210.12000.1195 0.15210.17390.14130.1883食品0.04000.12000.12000.14700.1370 0.13660.13670.12500.1800斯迈格里0.01100.18000.19330.21660.2000 0.10660.10660.11660.2233酵母0.58000.49000.72000.70000.6800 0.86000.73000.52000.8900网宿0.66630.54530.51190.48000.3120 0.54000.54000.55000.6900国王詹姆斯0.47000.63400.51260.83000.4210 0.09000.20000.14000.5600CA-GrQc0.12000.13000.15000.18000.7800 0.21000.26000.22000.2700●●●●●●3K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5384图三. 拟定方法与局部方法、准局部方法和全局方法的AUC比较。K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5385图3（续）K. Berahmand，E.纳西里山，巴西-地Forouzandeh等人沙特国王大学学报5386转移概率计算过程中的相互影响在链路预测任务中是非常有益的。4.4.1. ROC曲线受试者工作特征曲线是一种图形，显示了一种方法识别真阳性样本和将其与阴性样本区分开来的程度。我们需要在不同的阈值下绘制真阳性率和假阳性率，以获得ROC