文摘

链接预测是数据科学的一个基本问题,通常要求展开micro-dynamics治理机制的网络。在这方面,使用功能从网络嵌入预测链接吸引了广泛的关注。虽然方法基于边缘特征或节点相似性提出了解决链路预测问题,许多技术难题仍然存在由于独特的网络结构属性,特别是当网络是稀疏的。从图挖掘的角度来看,我们首先给经验证据的启发式和学习优势特性之间的矛盾。然后,我们提出一个新颖的链接预测框架,AdaSim,通过引入一种自适应的相似性函数使用功能从网络嵌入基于随机漫步。节点特性表征是一个基于目标函数得到优化。而不是使用二元操作符生成边缘特性,我们执行链接预测仅仅利用网络的节点的功能。我们定义了一个灵活的相似性函数和一个可调参数,作为一个点球的最初的相似性度量。最优值是通过监督学习,因此学习自适应数据分布。评估算法的性能,我们进行广泛的实验在11个不同的网络上的现实世界。实验结果表明,AdaSim达到更好的性能比最先进的算法和健壮的不同稀疏网络。

1。介绍

网络最近成为代表的一个重要工具和分析多种交互系统从生物到社会科学(1]。技术创新和数据爆炸收集速度,我们人类正进入大数据的时代,因此和参与的这些网络正在迅速扩大。研究这些复杂的联锁网络可以帮助我们了解实际系统的运行机制。因此,在过去的几年中,大量的工作一直致力于研究进化(2,3],拓扑[4,5),和特征6的网络,吸引研究人员从物理学、社会学、和计算机科学。

然而在许多情况下,当前各种网络数据的观测远不完整(7]。例如,在蛋白质相互作用和代谢网络,两个节点是否有链接必须是由实验决定的,这是非常昂贵的。因此,已知的链接可能代表不到1%的实际链接(8]。除此之外,在像Facebook这样的社交网络,只有部分用户显示的观察网络之间的友谊,和仍然存在的用户对已经互相认识但不通过Facebook连接。因此,它始终是一个具有挑战性的有意义的任务来确定双节点连接在当前网络不可能在实际的网络连接,即。预测失踪链接。获取这些知识是有用的,例如,在生物领域,它给予宝贵的指导,开展有针对性的实验,在社交网络领域,它可以用来推荐有前途的友谊,从而提高用户的忠诚到web服务。

的方式来解决链路预测问题(9- - - - - -14大致可以分为两类,即。无监督方法和监督方法。在无人监督的链接预测目前的研究工作,他们把主要精力集中于定义相似性度量无关的节点对 使用从网络拓扑结构提取的信息。定义的指标代表不同种类的一对节点之间的距离和有不同的性能在各种网络和没有人能支配他人。大部分指标很容易计算和解释,但他们是不变的,根本无法应付动态,相互依赖,在网络和其他属性15]。链路预测问题还可以冒充一个二进制分类监管任务从机器学习的角度来看16]。从那时起监督链接预测方法的研究已成为著名的[15,17- - - - - -19),这些研究的结果提供确认的证据,一个监督方法可以提高预测性能的联系。

选择一个适当的特性是至关重要的任何监督机器学习任务(20.- - - - - -22]。链接预测,每个样本数据集对应于一对节点。一个典型的解决方案是使用多个拓扑相似性特征,这是最直观的方式。但所有这些特性是手工制作和成本人类劳动。除此之外,他们常常依赖于领域知识,因此在不同的领域限制泛化。

另一种方法是学习网络的自动功能。将网络视为特殊的文档组成的一系列节点序列,该节点特性可以学到通过求解一个优化问题23]。获取节点的特点后,链接预测的任务是使用两种方法进行的传统。第一个是相似性排序法(24),例如,余弦相似度是用来测量双节点的相似性。两个独立节点,相似度值越大,连接概率越高。另一个是基于边缘特征的分类方法(25,26]。在这种方法中,启发式二元操作符生成的边缘特性等阿达玛操作员和平均操作符。然后训练一个分类器使用这些特性,用来区分两个无关的节点之间的链接是否形成。

随着功能从网络嵌入保护网络的局部结构,余弦相似度适用于强烈选型网络但未能捕捉网络的disassortativity,即。宁愿在大尺度上建立连接,节点在小尺度(7]。因此,使用余弦相似性链接预测患有统计性能缺陷。此外,边缘特征通过二元操作符将可能失去节点的信息,由于节点的特点是学会了通过求解一个优化问题,但边缘特性(见图1一个明确的解释和节将讨论细节3.3)。此外,边缘有相同的维数和节点特性,通常在几百的规模。这意味着即使逻辑回归等线性模型,它仍然需要学习数以百计的参数,提出了我们的问题可行性特别是当数据规模很大。如何设计一个简单的,通用高效的链路预测方法使用节点特性直接从网络嵌入仍然是一个开放的问题。

为了解决上述问题,我们提出一个新颖的链路预测方法,AdaSim(自适应相似性函数),对大规模网络。节点特性表征得到了通过优化基于目标函数使用随机梯度下降法技术。而不是使用启发式二元操作符生成边缘特性,我们执行链接预测仅仅利用网络的节点的功能。我们的重要贡献在于定义一个灵活的节点相似性函数只有一个可调参数,作为原始相似性的一个点球。最优值可以通过监督学习,因此自适应数据分布,使AdaSim能够捕捉不同网络的各种链接形成机制。与原来的余弦相似度相比,该方法推广跨各种网络数据集。

总之,我们的主要贡献如下:(我)我们建议,AdaSim,小说链接预测方法通过引入一种自适应相似性函数使用功能从网络嵌入。(2)我们表明,AdaSim足够灵活只有一个可调参数。它是可调节的网络属性。这种灵活性赋予AdaSim的力量捕获不同网络的链接形成机制。(3)我们证明的有效性AdaSim通过进行实验各种不同网络的真实。结果表明,该方法可以提高链接预测在不同程度的表现。此外,我们发现AdaSim工作高度稀疏网络特别好。

剩下的论文结构如下。部分2评论链接预测相关的一些研究工作。链接预测的问题定义和特性介绍了学习部分3,数据集上的一些实证研究也在这一节中。部分4说明了提出的链路预测方法AdaSim每个组件的详细说明。实验结果与分析部分表示5。最后,部分6总结了纸。

2。相关工作

早期作品链接预测主要集中在探索拓扑信息来源于图表。Liben-Nowell和jonkleinberg27]研究拓扑特性,比如常见的几个邻国Adamic-Adar, PageRank和卡茨,发现拓扑信息是有益的在预测与随机预测的链接。随后,一些架构预测提出了链接预测,例如,资源分配(28],community-enhanced预测[8)和聚类系数链接预测(29日]。

艾尔哈桑等人是第一个模型链接预测二元分类问题从机器学习的角度来看16]。各节点之间的相似性度量对从网络中提取和作为监督学习设置功能;分类器是由这些特征作为输入来区分正样本(链接形式)和负样本(不形式)的链接。此后,监督分类方法已经普遍预测领域的联系。Lichtenwalter等人提出了一个高性能的称为HPLP链接预测框架。一些新的视角链接预测,例如,一个算法的通用性,拓扑的原因,和抽样方法,包含在裁判。15]。后,监督随机walk-based Backstrom和Leskovec提出的算法17)有效地将信息从网络结构丰富的边缘节点和属性数据。

此外,链路预测问题也扩展到异构信息网络(30.- - - - - -33]。在这些作品中,提出了基于网络模式的核心概念,即meta-path。多个信息源可以有效地融合成一个单一的路径和不同的元路径有不同的物理含义。一些相似的措施可以使用元计算路径;然后,他们被视为特征分类器的区分正面和负面的链接。

所有上述工作监督链接预测使用手工特性,这通常需要昂贵的人类劳动和依赖于领域知识。缓解这个问题,可以使用自动通过表示学习中学到的潜在特性(34]。网络的无监督特征学习方法通常使用不同的光谱特性图的矩阵表示,如邻接和拉普拉斯算子矩阵。在线性代数的角度来看,这种方法可以被看作是一种降维技术。几位工作35,36)已经完成的目标获得的节点特征图,但计算eigendecomposition矩阵是昂贵的,因此这些方法不切实际的大型网络规模。

Perozzi et al。23]扩展skip-gram模型图,提出了一个框架,DeepWalk,代表了网络作为一种特殊的“文档”组成的一系列节点序列,生成的随机漫步。DeepWalk可以学习功能,为网络中的节点,和表示学习过程与下游节点分类和链接预测等任务。之后,提出了Node2vec Grover和Leskovec [26]。与DeepWalk相比,Node2vec使用偏置随机漫步来控制节点的采样空间序列。同质性等网络特性和结构可以被Node2vec等价。链接预测进行了使用边缘特性通过启发式二元操作符在节点功能。在[37),作者提出了一个深模型称为SDNE捕捉网络的高度非线性特性。一阶和二阶距离共同利用捕捉当地和全球网络结构,分别。最近,王et al。38)提出了一个新颖的模块化的非负矩阵分解(M-NMF)模型将不仅当地和全球网络结构,而且社区信息网络嵌入。为了模型的各种角色进行交互节点与其他节点交互时,涂等。39)提出了一个上下文感知网络嵌入(甘蔗)方法通过引入共同关注机制。甘蔗更精确地模型节点之间的语义关系。为了节省计算时间,在24),链接预测直接使用余弦相似度的节点特征而不是边缘特征。

上面的工作主要集中在网络嵌入技术和忽视链接形成的典型特征。现有的工作和我们的努力之间的主要区别在于,我们考虑一个适应性的相似性函数和学习型的想法,使我们的模型足够灵活来捕获各种链接形成的不同的网络模式。例如,一个负面的价值可以削弱“结构等效”的作用,提高分数不同的节点对,因此捕捉disassortativity链接形成。

3所示。问题陈述和功能学习框架

在本节中,我们首先给出链接的正式定义预测问题。然后特性提出了网络学习框架。最后,我们介绍了实证研究结果在几个网络数据集在使用节点链接预测功能。

3.1。问题公式化

给定一个网络 ,在哪里是一组节点, 是链接的设置,不允许有多个链接或self-links网络中任意两个节点。假设网络中的一些链接在现阶段未被注意的或失踪。链接预测任务的目标是预测的可能性之间的联系两个无关的节点使用固有的信息网络。

因为我们正在考虑一个监督方法链接预测,我们首先需要构建一个标签的数据集 ,在哪里特征向量的吗样品和 相应的标签。具体地说, 在这和表示节点的特点和 ,分别。从网络节点特性表示学习。从节点功能节点是一个映射函数对特征。任何节点在 , 表明该节点对属于正样本和负样本。阳性样品的边缘, ,从网络随机挑出来的 。我们删除从G获得并保持子( )完全连接。为了生成负样本,我们对从样品同等数量的节点没有边缘连接。数据集啐分为两部分:训练数据集和测试数据集 。一个分类模型数据集可以学会吗 ,然后这个模型将被用于预测一对节点是否在数据集应该有一个链接连接它们。我们的算法是典型的方法从图像挖掘的领域。因此,与我们之前的论文的一部分(9,10),我们遵循约定在人工智能领域中(阳性样本)50%的观察到的链接,和分数是基于的结合和相同数量的nonobserved链接(负样本)。高度稀疏性接触网络,只有少量的节点,而不是由所有观察到的链接。

3.2。网络嵌入的特性学习

对于一个给定的网络 ,一个映射函数 从节点到特征向量可以学到链接预测。在这里是一个指定的参数,它表示特征向量和维度的数量是一个矩阵的大小 参数。映射函数通过一系列的学习文档节点序列,使用优化技术起源于语言建模。

语言建模的目的是评估一个句子出现在文档的可能性。使用语料库构建的模型 。更正式,它旨在最大化 对所有训练语料库,这个词的词汇,的上下文包括单词的左侧和右边。最近的研究表示学习使很多关注利用概率神经网络来构建一个通用表示的话,扩展语言建模的范围超出了原来的目标。每个词是由一个连续和低维的特征向量。然后是最大化的问题 在哪里表示的潜在表示一个单词。

网络的社会表示可以学到类似地通过一系列的节点序列生成的特定的采样策略 。类似于单词的上下文在语言建模中,被定义为节点的邻居吗使用抽样策略 。网络的节点表示可以通过优化以下表达式

学表示可以捕获共享在当地图结构网络中的节点之间的相似性。节点有类似的社区将会获得类似的表示。

3.3。实证结果在几个网络数据集

在了解网络中的节点表示,链接预测任务有两种方法,即。,node-similarity-based法和edge-feature-based法。前者是简单的和可伸缩的,后者是复杂而强大的。但是这两种方法都有它们的局限性在有效地描述链接节点对的形成模式。自从node-similarity-based方法没有参与学习,不能意识到全球网络属性链接预测的影响。边缘特征方法不能描述节点两人关系很好使用启发式二元运算符在功能层面,作为从节点特性映射过程中存在信息丢失边缘特性。我们的经验证据显示这两种方法的局限性下面。

3.3.1。启发式二元操作符的限制

图1(一)显示了一个玩具网络(krackhardt风筝图)与10节点和18边缘。每个节点和边缘有一个独特的标签。给定一个特定的采样策略 ,我们可以获得节点序列和序列后同时执行相应的优势在网络上。因此,表示两个节点和边缘表示网络的使用优化技术是可以习得的。为一个特定的节点,学会边表示被称为“真正的”特性和生成的边表示使用二进制运算符叫做“启发式”特性。众所周知,如果一个二元运算符是足够好,它应该能够准确地描述成对的节点之间的关系,即。,启发式特征之间的相关性和真实的特性应该尽可能的强大。18在玩具网络边缘,五个不同的启发式二元操作符(26)(见表1)(选择生成边缘特性部门运营商,我们省略的因为它有非常相似的结果相比 ),与真正的优势及其相关特性显示在图中1 (b)。

从图的基础上的证据1,我们可以看出不同的运营商有不同的结果代表的特性对节点和没有人可以支配别人。的边缘,例如,边缘10和16,可以的阿达玛运营商,而另一些人,例如,边缘12日14日和17日的特点平均操作符。此外,最值小于0.5,这意味着启发式边缘之间的弱相关特性和真正的边缘特征。这验证我们声称边缘特性通过启发式二元操作符可能会导致节点特性的信息丢失。

3.3.2。相似性方法的限制

给定一个无关的节点组 ,几个指标可以用来衡量他们的相似之处,例如,共同邻居之间和 ,和访问路径的数量和 。但这里我们只考虑余弦相似性的度量因为我们有一对节点的特征向量和 ,分别。余弦相似度用来描述链接形成概率,它被定义为 在哪里表示转置和意味着 - - - - - -规范的一个向量。余弦相似度测量的是两间夹角的余弦值 - - - - - -维的向量从网络获得表示学习。事实上余弦相似性的概念已被用于链接预测在几个工作(24,40,41]。但有一些问题当直接使用余弦相似性链接预测。第一个是它没有考虑节点对的标签信息。因此,它属于无监督学习的范畴。然而,大量的作品表明,监督学习方法链接预测可以提高性能(15,18,19]。另一个是余弦相似性太死板,捕捉不同形成机制不同的网络链接。

表示阶段的学习网络,假设两个节点有类似的表示,如果他们有类似的上下文节点序列采样策略 。对于网络来说,这表明,如果两个节点是结构(三个节点 图中,假设的测地距离 2, 5,我们说什么更接近于比 )对方,然后他们有一个高概率同时发生在同一序列导致一个高价值的余弦相似性。但在实际网络中,两个节点是否会形成一个链接不仅仅是受到这种结构性的亲密。网络中两个节点远离彼此也会有很高的建立关系的机会,如果他们在结构上是相同(26]。为两个节点图的距离越近,越容易为他们建立联系”不一定,尤其是当网络稀疏和非选型。

如图2,我们可以看到,不同的网络有不同的模式在建立新连接(部分中描述的数据集5。1)。这些模式是密切相关的网络属性,如聚类系数、密度和assortativity的图表。一些网络assortativity高,两个无关的节点往往是连接结构紧密,而另一些则不是。更具体地说,两个独立节点的链接形成的概率大大减少与测地距离的增加C.elegans数据集,97.8%新跨越的测地线距离小于3的链接。但对于努特拉数据集,测地距离的增加,形成概率的链接先增加后减少,和大部分的新链接(62.4%)是由节点和距离等于5或6双。为路由器数据集,新链接跨度范围广泛的测地线距离2 - 34,几乎一半的新链接(48.67%)跨越距离大于5。链接形成的分布概率比其他两个更复杂的数据集。

余弦相似度函数分配更高的分数对节点如果他们相互接近,反之亦然。它可以捕获链接图的形成模式2(一个),即,the shorter the distance between two unconnected nodes, the higher the probability to be connected. But cosine similarity fails to capture the patterns in the cases of Figures2 (b)和2 (c),特别是图2 (b),链接形成模式遵循一个高斯分布。图的模式2 (b),节点更倾向于与那些建立连接相对远离他们。当执行一个链接预测任务在这种情况下,对节点有一个相对长的距离应该比那些更短更相似。

因此,我们需要设计一个灵活的相似性函数链接预测和捕捉链接形成的各种模式。除了相似函数应该设计的基础上,简明和可伸缩性。这可以通过调整节点的相似性对和平衡链接形成概率在不同的距离。灵感来自于这一点,我们提出一个修改后的相似性函数被定义为 在哪里是一个平衡的因素控制节点的相似性对与不同的测地线距离。标签的节点对,最优值可以学到监督。

4所示。拟议的框架

在这项工作中,我们提出一个新颖的链接预测框架,AdaSim基于自适应相似性函数使用的功能从网络表示。整个框架见图3。它可以分为三个部分:子图生成、特征表示、相似性函数学习。首先,积极的和消极的节点索引是通过随机抽样。相应的子图通过生成边缘去除。然后我们学习的表示网络中节点使用一个无监督的方法。最后,定义相似度函数和最优参数决定通过监督学习。相似函数获得最优惩罚可以直接用来解决链路预测问题。

4.1。子图生成

不像其他任务,比如链接聚合或节点分类,完整的结构信息是可用的,一定比例的链接需要删除之前执行网络链接预测表示学习(42- - - - - -44]。为了实现这一目标,一个迭代可以选择一个链接并确定是否它是可移动的。但此操作不太有效,非常耗时,特别是当网络非常稀疏,因为它需要遍历中的几乎所有的节点图。

相反,我们提出一个快速积极的抽样方法基于最小生成树(MST)。一个MST原始图像边缘的一个子集的所有节点连接在一起。这意味着所有的边都是可移动的,除了那些属于MST和删除不折断的性质的连通性。算法中的1 - 4行1显示我们的方法的核心。我们首先生成一个MST表示为 使用克鲁斯卡算法。积极的样品是随机选择的 。产生负样本 ,我们对从样品同等数量的节点 ,没有边缘连接(5 - 7行)。然后删除所有的边缘从并获得的子图(第8行)。

4.2。特征表示

现在我们继续执行功能的子图的学习任务 。这个任务包括两个核心组件。,a node sequence sampling strategy and a language model.

4.2.1。准备节点序列抽样

的节点序列抽样,最经典的策略是广度优先搜索(BFS)和深度优先搜索(DFS) [26]。BFS是从一个特定的节点和探讨了邻居先移动到下一个水平。相反,DFS遍历网络从一个节点开始,探索尽可能在每个分支在回溯。BFS和DFS代表两个极端的抽样策略对他们探索的搜索空间,带来价值的影响表示。事实上,附近采样通过BFS可以反映结构等效网络和采样节点的DFS可以反映出宏观视野的社区,这是至关重要的在推断社区基于同质性(26]。尽管他们是派拉蒙的意义产生有趣的表征,同时也不能揭示了复杂网络的属性。抽样策略,我们需要一个能顺利插入DFS和BFS之间的需求可以满足随机漫步在图表。

随机漫步的长度在扎根在节点是一个随机过程,随机变量 这样 和随机选择一个节点均匀的邻居吗 。随机漫步出现在各种模型的大规模网络,如计算节点相似之处(19,45),学习等级节点(46,47,估计网络属性(48]。除此之外,它们是一类输出敏感的基础算法,采用计算群落结构的局部信息。

这个连接的原因促使我们用随机漫步的节点序列中提取网络信息的采样策略。

算法中的1 - 6行2显示节点采样序列的过程。如图3,我们可以获得一系列的节点序列使用随机漫步。例如,如果我们想要一个随机游走的长度 扎根在网络上的玩具,我们可能得到的结果 。同样获得的其他序列。

4.2.2。语言模型

为了得到网络的表示,目标是解决 在哪里 , 是上下文大小,是表示节点的映射函数特性。为 ,我们可以使用softmax,对数线性分类模型,得到后验分布的节点。然而softmax涉及总和所有节点对和做这样计算每个训练实例非常昂贵,使其不切实际的大型网络规模。

为了解决这个问题,一种直觉是限制输出向量更新每个训练实例的数量。因此,分层softmax [49提出提高学习效率,我们采用在这工作。最后,我们使用随机梯度下降法(SGD)技术来优化算法的目标函数(7行2)每个节点的社会表征,即, ,图中。如图3为玩具网络中的每个节点,我们可以得到一个 - - - - - -与之关联的维表示。

4.3。相似度函数的学习

节点对 ,我们使用和从网络获得表示学习作为他们的特性。考虑偏差分布在不同的测地线距离真正的链接,我们提出一种新颖的相似性函数定义为

我们表示 和 为了简单起见。然后,(7)可以写成

一双物流功能申请映射节点相似度值 ,这是一个概率表明它属于积极类或消极类。我们使用表示这个概率,表示为

为了测量预测值之间的亲密和真正的标签,我们选择熵损失作为我们的目标,这被定义为

随机梯度下降方法用于得到的最优值通过最小化 ,它的更新规则可以写成 在哪里

算法3显示了参数学习过程的核心部分。训练数据集和测试数据集是第一个通过1号线算法3。的最优值学会了使用SGD训练数据集(2)行。用于测量节点的相似性对吗我们可以得到他们的概率算法通过线路连接3到63。最后,评估结果通过第7行。

5。实验

在本节中,我们首先给出一个简短的描述中使用的数据集的实验。接下来,我们介绍了基线模型链接预测和评价指标。然后,实验结果给出了详细的分析。随着AdaSim框架包括几个参数,最后,我们将展示这些参数的不同的选择如何影响链接预测的性能。

5.1。数据集

全面评估计划的链路预测算法的性能,我们使用十个真实数据集进行实验,而这些数据集通常用于预测领域的联系。这些数据来自各领域和他们的细节描述如下:(我)秀丽隐杆线虫(50的神经网络秀丽隐杆线虫有虫吃。节点代表神经元和边缘表示突触或缝隙连接。(2)PB(51)是一个网络对美国政治博客之间的超链接。(3)Wiki-vote(52包含所有维基百科]是一个社交网络投票数据从维基百科,直到2008年1月的《盗梦空间》。网络中的节点代表维基百科用户和定向边缘节点到节点代表该用户投票用户 。(iv)Email-enron(52)是一个通信网络,涵盖了所有电子邮件沟通大约一半一百万封电子邮件。节点网络的电子邮件地址,如果至少有一个电子邮件地址为了解决 ,然后他们有一个他们之间的联系。(v)Epinions这样(52是who-trust-whom在线社交网络。网站的成员Epinions这样才能决定是否相互信任。如果用户信任用户 ,还有他们之间的联系。(vi)Slashdot(52与技术有关的新闻网站。网络包含了朋友和敌人Slashdot的用户之间的联系。(七)性(53)是一个著名的性接触网络。这个网络非常稀疏,几乎没有封闭的三角形。(八)Roadnet(52)代表一个加州公路网络,这是一个典型的稀疏和树状网络。(第九)权力(50)是一种传统的稀疏网络,表示美国西部的电网。(x)路由器是路由器级别的互联网络收集的Rocketfuel项目(54]。(十一)p2p-Gnutella(52努特拉)是一个对等文件共享网络。网络中的节点代表主机和边缘代表这些主机的努特拉之间的联系。

这些网络的基本拓扑信息是列在表中2,包括节点和边的数量,平均学历,平均聚类系数、直径和密度的网络。我们大致把网络稠密和稀疏的基于平均度和平均聚类系数。总之,我们在网络的各种特性进行实验,即。稀疏和密集,大大小小的。因此,数据集可以全面反映了该方法的特点(不同于其他网络,有观察到的链接的高度稀疏性接触网络由于小数量的节点)。

5.2。基线的方法和评价指标

为了验证算法的性能,我们进行比较AdaSim按照以下链接预测模型。(我)常见的邻居(CN):节点 ,让表示的邻居的 。两个节点,和 ,有一个高概率的连接如果他们有许多共同的邻居55,56]。最简单的方法来测量这个社区重叠是通过直接计算共同邻居的数量,也就是说, (2)资源分配(RA) (28:一对无关的节点和 ,假设可以发送一些资源媒介的邻居。之间的相似性和可以被定义为接收到的资源从 ,这描述为 在哪里的程度 。(3)优惠附件(PA) (57:优先连接机制用于生成随机的无标度网络,连接的新链接成正比 。同样,一个新的连接的概率和成正比 。的巴勒斯坦权力机构相似性指数被定义为 (iv)索尔顿海指数(SI) (40]:SI的另一个名字是余弦相似性和被定义为 (v)聚类系数预测(CCLP)[链接29日:这是一个相似性指数与当地更多的结构信息。在这种方法中,聚类系数的本地链接信息转达了共同的邻居。 在哪里通过节点是三角形的数量 。(vi)异质性指数(10]:这个方法是基于网络异构性和稀疏和树状网络的最先进的。 在哪里是一个免费的异质性指数。(七)Node2vec(26):这是一个监督的方式链接使用逻辑回归预测。在这种方法中使用的功能是通过启发式生成二元操作符的节点对功能从网络嵌入。有两个参数,和 ,控制节点序列抽样。注意,当 ,node2vec等于DeepWalk [23]。

旁边Node2vec无人监督的功能,还有其他方法学习图表,如光谱聚类(58和线59]。我们在这工作,因为他们已经排除他们不如Node2vec(26]。我们也排除其他监督方法,如整体学习(15)和支持向量机(16]。这些方法可以得到相对更好的性能,但高复杂性为代价的,这不是我们的初衷。

我们采用接受者操作特征下的面积(AUC)定量评估链路预测算法的性能。AUC值量化的概率随机选择缺失的环节给出更高的分数比一双随机选择的节点没有一个链接。更高的分数意味着更好的性能。

5.3。实验结果

为了获得以下结果,我们设置了参数的典型值在[26]。也就是说, ,和一个时代的优化运行。百分之五十的边缘被视为积极的例子。消极的节点对没有边缘连接随机抽样从网络。的两个参数,和 ,在Node2vec,他们选择通过网格搜索结束 。准备数据集后,我们使用10倍交叉验证评估性能。为了客观、每个数据集上的实验是重复十次,平均结果被发表在表3。

一般的观察我们可以从这些结果是,该链接预测算法,AdaSim比所有基线方法,可以获得更好的性能在所有的数据集。更具体地说,无人监督的相似性链接预测方法实现比监督的价值相对较低,因为标签信息不是杠杆来提高模型的性能。但是,巴勒斯坦权力机构预测达到竞争结果相比AdaSim甚至比Node2vec五11的数据集。这是因为优惠附件的关键特性之一发电法律无标度网络。它反映了网络演化的机制,涉及添加新的节点和边。因此,它可以获得更好的性能在链接预测问题。但相似性链接预测方法执行极其糟糕的网络稀疏时因为有限或没有封闭的三角形结构存在于这些网络。

在所有的监督链接预测方法,AdaSim优于两DeepWalk和Node2vec在所有的11网络获得不同尺度的比率。增益比率从0.75%变化到43.04%的AUC值相比Node2vec。

直观地显示处罚的影响在链接预测性能,设置为特定的值来与固定增量(这里 出于演示)和显示AUC在三个数据集的结果,也就是说,秀丽隐杆线虫,路由器,Wiki-vote,在图4。请注意, 对应于原始的余弦相似性度量。它可以清楚地看到,从图4,AUC的结果是大大影响的价值 。与刚性余弦相似度相比,我们的提议AdaSim可以大大提高链路预测的性能。这也验证我们的实证研究部分3.3不同的网络有不同的链接形成模式,从而灵活和适应性的相似性函数链接预测是需要捕获这些不同的模式。

我们选择三个代表稀疏网络,即性(小)、电力(媒介),和p2p-Gnutella(大),并报告CN,时钟时间CCLP,黑,Node2vec, AdaSim表4。从这个表我们可以观察到,随着网络规模的增加,预测所有算法所需的时间也会增加。此外,上优于比相似性的算法通常需要更多的时间因为向量乘法需要更多时间不仅仅是计算两个节点的邻居信息。虽然我们的预测算法需要更多的时间,它也取得了相当大的性能提升,如上所述。

5.4。与不同的稀疏网络性能

网络在现实世界中通常是稀疏的,我们只知道非常有限的节点之间的信息交互。例如,80%的细胞内分子相互作用的酵母和99.7%的人类仍然是未知的(40]。一个好的链接预测方法应该健壮的性能与不同的稀疏网络。

我们改变的稀疏网络通过随机删除一定百分比的原始网络链接,然后按照上述实验设置报告不同的方法的结果。Wiki-Vote数据集上的结果显示在图中5。只有四个基准图中列出的方法CN,CCLP,DeepWalk执行同样的类风湿性关节炎和Node2vec,分别。

从结果可以看出,AUC值降低的增加删除边比因为它变得越来越具有挑战性的使用信息网络拓扑描述节点相似性。相似性方法表现良好时,删除边比例相对较小。此外,AdaSim表现一贯良好,健壮的不同稀疏的网络条件。即使百分之八十的边缘是移除,AdaSim仍然可以保持约0.95的AUC性能。总的来说,AdaSim不仅是强大的不同网络条件也比基线达到更好的性能。

5.5。参数的敏感性

有几个参数参与AdaSim算法和图6,我们检查参数的不同的选择如何影响的性能AdaSimWiki-Vote数据集。除了被测试的参数,其他参数假设默认值。

我们测量维度的AUC的函数表示 ,走的长度和走每个节点的数量 。我们观察到学习表示节点的尺寸限制了对链路预测性能的影响。随着维数的增加,AUC值略有增加,饱和时达到128。它也可以观察到一个更大的和将提高性能;这是因为更多的种子节点的邻居信息包含在表示学习过程,可以更精确地捕获和节点相似之处。

6。结论

在这项工作中,我们专注于功能从网络嵌入链接预测问题。边缘特性通过启发式二元操作符是一个产生信息损失原始节点的投影特性,我们定量的证据之间的矛盾启发式边缘特性和学习的。此外,我们已经开发出一种新颖的链接预测框架AdaSim通过引入一种自适应相似函数来处理余弦相似度的不灵活性,特别是稀疏或树状网络。AdaSim首先学习网络的节点表示解决基于目标函数,然后添加一个惩罚参数, ,在最初的相似性函数。最后,最优值通过监督学习学习。被提议的AdaSim是灵活的,因此自适应数据分布,可以捕获各种链接形成机制不同的网络。我们使用公开可用的真实网络数据集进行实验,和广泛的比较AdaSim与七成熟的代表基线的方法。结果表明,AdaSim达到更好的性能在所有数据集比最先进的算法。也是强劲的稀疏网络和获得竞争性能虽然大部分的边缘人失踪。

数据可用性

所有的数据集都可以获得相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作得到了国家自然科学基金(61901247,61901247),山东省自然科学基金ZR2019BF032,国家社会科学基金重大项目(zda149 19日和19日zda324),中央大学和基础研究基金(14370119和14370119)。