CN110598073B

CN110598073B - 基于拓扑关系图的实体网页链接的获取技术

Info

Publication number: CN110598073B
Application number: CN201810516375.1A
Authority: CN
Inventors: 苏柏; 马超; 周长海; 华抒军; 陆掾; 文宁
Original assignee: Microsoft Technology Licensing LLC
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2018-05-25
Filing date: 2018-05-25
Publication date: 2024-04-26
Anticipated expiration: 2038-05-25
Also published as: US11403534B2; CN110598073A; WO2019226371A1; US20210191951A1; EP3803715A1

Abstract

本文公开的基于拓扑关系图的实体网页链接的获取技术，基于网页间的拓扑关系图来确定候选实体网页的权重值，能够充分挖掘候选实体网页与主语实体网页间的关联关系，从而提高找到值链接的概率以及准确度。

Description

基于拓扑关系图的实体网页链接的获取技术

背景技术

随着互联网的发展，网络数据内容呈现爆炸式增长的态势。由于互联网内容的大规模、异质多元、组织结构松散的特点，给人们有效获取信息和知识提出了挑战。知识图谱(Knowledge Graph)以其强大的语义处理能力和开放信息组织能力，为互联网时代的知识化组织和智能应用奠定了基础。知识图谱用于描述实体(Entity)以及实体之间的关系。随着人工智能的技术发展和应用，知识图谱作为人工智能的关键技术之一，已被广泛应用于智能搜索、智能问答、个性化推荐、内容分发等领域。

发明内容

提供本发明实施例内容是为了以精简的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容并不旨在标识所要求保护主题的关键特征或必要特征，也不旨在用于限制所要求保护主题的范围。

上述说明仅是本公开技术方案的概述，为了能够更清楚了解本公开的技术手段，而可依照说明书的内容予以实施，并且为了让本公开的上述和其它目的、特征和优点能够更明显易懂，以下特举本公开的具体实施方式。

附图说明

图1为描绘应用本文实体网页链接的获取技术的示例环境之一的框图。

图2为正向拓扑关系图的示例结构框图；

图3为基于正向拓扑关系图进行第一轮随机游走的示例框图；

图4为基于正向拓扑关系图进行第二轮随机游走的示例框图；

图5为基于正向拓扑关系图的随机游走结果的示例框图；

图6为反向拓扑关系图的示例结构之一的框图；

图7为反向拓扑关系图的示例结构之二的框图；

图8为基于图6的反向拓扑关系图进行第一轮随机游走的示例框图；

图9为基于图6的反向拓扑关系图进行第二轮随机游走的示例框图；

图10为基于图7的反向拓扑关系图进行第一轮随机游走的示例框图；

图11为基于图7的反向拓扑关系图进行第二轮随机游走的示例框图；

图12为描绘本文的实体网页链接的获取方法的流程示意图；

图13为示例性的具有可移动性的电子设备的结构框图；

图14为示例性的计算设备的结构框图。

具体实施方式

下面将参照附图更详细地描述本公开的示例性实施例。虽然附图中显示了本公开的示例性实施例，然而应当理解，可以以各种形式实现本公开而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本公开，并且能够将本公开的范围完整的传达给本领域的技术人员。

本文中，术语“技术”、“机制”可以指代例如(一个或多个)系统、(一个或多个)方法、计算机可读指令、(一个或多个)模块、算法、硬件逻辑(例如，现场可编程门阵列(FPGA))、专用集成电路(ASIC)、专用标准产品(ASSP)、片上系统(SOC)、复杂可编程逻辑设备(CPLD)和/或上述上下文以及在本文档通篇中所允许的(一项或多项)其它技术。

概览

本文涉及针对网站中的网页数据进行知识抽取而形成的知识图谱的相关技术。知识图谱中典型的数据格式为三元组的形式。三元组(SPO)以主谓宾形式来存储数据，包括主语(Subject)、谓语(Predicate)以及宾语(Object)，其中，主语和宾语分别对应于不同的实体，而谓语则表示这两个实体之间存在的相关关系。需要说明的是，在知识图谱领域，对于主语、谓语以及宾语应当做广义理解，而并不局限于语法结构上的主谓宾结构，而应该理解为类似于主谓宾语法结构所体现出的实体之间的逻辑关系。在一些定义中，也可以将SPO定义为：主体、属性以及客体，或者主体、属性以及属性值，其基本的技术含义是一致的。

在基于对网页数据进行抽取而形成的知识图谱中，主语(Subject)包括某一实体(Entity)对应的网页链接，宾语(Object)包括：宾语值(也就是宾语对应的实体的名称，为了方便表述，称作为宾语值)和值链接(Value Link，宾语对应的实体的网页链接)，其中，值为作为另一实体对应的名称，而值链接(Value Link)为该另一实体对应的网页，谓语存储的是的主语与宾语之间的相互关系，这些关系可以采用经过编码后的字符串或者链接的形式存储。

在对网页数据进行抽取的过程中，由于宾语部分对应的实体对应的网页并不一定以非常明显的方式存在，因此，值链接部分经常会存在缺失，这种情况导致了三元组数据的不完整，在后续提供具体服务时，存在一些信息上的缺失。

本文提出的基于拓扑关系图的实体网页链接的获取技术，基于网页间的拓扑关系图和权重值排名的方式来获取值链接，能够充分挖掘实体网页间的关联关系，从而提高找到值链接的概率以及准确度，进而可以最大可能地补充从网页数据中抽取的三元组数据中的值链接的缺失。

说明性环境

下面描述的环境仅构成一个示例，而不旨在将各项权利要求限于任一特定操作环境。可以使用其它环境而不背离所要求保护的主题的精神和范围。

如图1所示，其为描绘应用本文实体网页链接的获取技术的示例环境之一的框图100。在图1所示的示例环境中，服务器101用于海量的网页进行知识抓取，形成知识图谱，并存放于知识图谱数据库102中。

其中，网页的来源可以是连接于互联网103的网站服务器104，服务器101可以通过第三方的网站服务器104提供的网页访问接口，访问各个网站服务器104来获取网页，并进行知识抓取，在该网站服务器104的后台，会存在相应的网页数据库106。另外，网页的来源也可以是来自于与服务器101属于同一运营机构的网页数据库106，网页数据库106对于服务器101而言相当于机构内部的数据库。本文所说的网页，并不限于通过浏览器访问的页面，也可以是通过APP访问的各种类型的页面。

上述的服务器101可以通过一个或多个计算机系统实现(分布式服务器)，该服务器101可以是基于云架构的云服务器，通过互联网与用户终端或者其他第三方服务器连接，为用户或者第三方运营机构提供知识内容服务。

如前文所介绍的，在对网页数据进行抽取的过程中，会存在宾语部分的值链接缺失的情形。针对这种情形，本文提供了一种实体网页链接的获取装置107，可以设置于服务器101中，辅助服务器101完善知识图谱的构建。

该网页链接的获取装置107包括候选实体网页获取模块108、拓扑关系图构建模块109、权重值计算模块110以及排名模块111。

候选实体网页获取模块108，用于根据宾语值检索与该宾语值相关的多个候选实体网页。具体地，在网页数据库中存储的网页中，包含有很多锚文本(anchor text)。从这些锚文本中包含了从当前网页指向另一关联网页的网页链接。通过对这些锚文本进行匹配检索，找到与宾语值匹配的锚文本，进而获得与宾语值相关的多个候选实体网页。

这些候选实体网页都是与宾语值相关的网页，但是并不一定是知识图谱希望存储的值链接对应的网页。具体候选实体网页可能存在如下几种情形：

1)由于存在很多重名的实体，例如，重名的人，重名的地理区域，重名的公司等等。获取到的候选实体网页对应的实体并不一定是输入的知识图谱的三元组中的宾语对应的实体。例如，三元组中作为宾语值对应的实体为足球运动员，而基于锚文本找到的候选实体网页为与该足球运动员重名的滑雪运动员。

2)候选实体网页也不一定就是详细介绍该宾语值对应的实体的网页，可能只是包含了实体的相关信息的网页，这种网页可能并不符合知识图谱的要求或者对知识图谱来说不理想。例如，某个网页中包含了“xxx”电影明星的锚文本，但是该锚文本并没有指向详细介绍该电影明星的网页，而是指向了该电影明星参演的一部电视剧的介绍网页，或者是该电影明星签约的娱乐公司的网页，在这些网页中只有很少的内容提及了该电影明星。作为构建知识图谱而言，希望找到能够更有针对性、更加详细的介绍宾语实体的网页。

3)较为详细地介绍三元组中的宾语值对应实体的网页，该网页也是知识图谱所需要的较为理想的网页。本文中的技术方案就是要找到上述的第3)种类型的实体网页。

拓扑关系图构建模块109，用于构建主语实体网页与多个候选实体网页之间的拓扑关系图。候选实体网页获取模块108检索到上述的多个候选实体网页后，就可以在主语实体网页与这些候选实体网页之间构建拓扑关系图了。该拓扑关系图的作用就是挖掘出主语实体网页和各个候选实体网页之间的关联关系，这些关联关系会体现在拓扑关系图的路径关系上。从主语实体网页到多个候选实体网页的拓扑关系图可以包括正向拓扑关系图和/或多个反向拓扑关系图。

正向拓扑关系图是指从主语实体网页到候选实体网页的拓扑关系图。在正向拓扑关系图中，主语实体网页为头节点(Head node)，多个候选实体网页为汇聚节点(Sinknode)。

反向拓扑关系图是指从候选实体网页到主语实体网页的拓扑关系图，由于候选实体网页一般为多个，所以，反向拓扑关系图也为多个。在反向拓扑关系图中，候选实体网页为头节点(Head node)，主语实体网页为汇聚节点(Sink node)。

权重值计算模块110，用于根据拓扑关系图中候选实体网页与主语实体网页之间的路径关系，计算各个候选实体网页的权重值。在拓扑关系图构建模块109生成了之后，就可以基于拓扑关系图中的路径关系来计算候选实体网页的权重值了。权重值计算方法可以采用随机游走的方式来计算，具体地，向拓扑关系图中的头节点分配初始权重值，然后通过多轮次的随机游走，在每个轮次的随机游走的过程中，根据各个节点的出度，进行权重值的分配。经过多轮次的随机游走后，将拓扑关系图中的汇聚节点获得的权重值作为候选实体网页的权重值。

需要说明的是，对于正向拓扑关系图而言，汇聚节点为候选实体网页，在随机游走过程结束后，各个汇聚节点获得的权重值就作为各个候选实体网页的权重值。对于反向拓扑关系图而言，汇聚节点为主语实体网页，在随机游走过程结束后，仍然将汇聚节点获得的权重值作为候选实体网页的权重值。在同时采用正向拓扑关系图和反向拓扑关系图求取候选实体网页的情况下，先分别基于正向拓扑关系和反向拓扑关系计算各个候选实体网页的权重值，然后针对每个候选实体网页，将基于正向拓扑关系图获得的权重值和基于反向拓扑关系图获得的权重值进行相加，获得最终的权重值。

此外，由于随机游走是逐轮次进行的，并且初始的权重值是分配给头节点的，拓扑关系图的构建也是从头节点开始，因此，随机游走可以伴随着拓扑关系图的生成而同步进行。

排名模块111，用于根据各个候选实体网页的权重值进行排名，并根据排名结果确定宾语值对应的值链接。在获得了各个候选实体网页后，就可以根据权重值来进行排名，可以选择排名靠前的一个或者几个候选实体网页的链接作为知识图谱中宾语值对应的值链接。

在上述的处理机制中，构建的图谱关系图挖掘出了主语实体网页和候选实体网页之间的关联关系，其中，正向拓扑关系图和反向拓扑关系体现了主语实体网页和候选实体网页之间的正反两个方向的关联关系，从而能够更加全面地对候选实体网页与主语实体网页之间的关联关系进行评估。另外，通过随机游走的方式来计算候选实体网页的权重值，能够更加准确地量化候选实体网页与主语实体网页之间的关联程度，从而能够根据权重值的排名选择出更加适合的候选实体网页。

下面将针对正向拓扑关系图和反向拓扑关系图，分别说明上述的拓扑关系图的构建过程以及权重值的分配以及排名的处理机制。

正向拓扑关系图的构建

正向拓扑关系图是从主语实体网页开始到多个候选实体网页为止的拓扑关系图。图中的各个节点均对应于不同实体网页，其中，以主语实体网页作为头节点，以候选实体网页作为汇聚节点，头节点和汇聚节点以外的节点为中间节点(Intermediate node)，中间节点对应着主语实体网页与候选实体网页以外的中间实体网页，这些中间节点会存在两种情况，一种是处于头节点和汇聚节点的链接路径上，这些中间实体网页直接或者间接地指向了候选实体网页，另一种是没有位于头节点和汇聚节点的链接路径上，这样的中间实体网页可以认为是与主语实体网页与候选实体网页之间的拓扑关系无关紧要的网页。为了便于描述，在下文中将正向拓扑关系图中的头结点、中间节点以及汇聚节点分别称作第一头节点、第一中间节点以及第一汇聚节点。

正向拓扑关系图的生成过程如下：

将主语实体网页作为第一头节点。

从该主语实体网页开始，抓取该主语实体网页指向的多个中间实体网页和/或候选实体网页，然后再从抓取到的各个中间实体网页继续抓取一个或多个新的中间实体网页和/或候选实体网页。具体地，可以通过主语实体网页或者中间实体网页中的锚文本来获得其指向的其他网页。

如此循环，直至到达预设的第一抓取轮次和/或形成了预设的第一数量的从主语实体网页到候选实体网页的路径，其中，将中间实体网页作为第一中间节点，将候选实体网页作为第一汇聚节点。

考虑到效率和拓扑关系图的有效性，可以对网页抓取的轮次进行一下限制，在指定的轮次中，如果没有构建出从主语实体网页到某个候选实体网页的路径关系，那么这个候选实体网页就可以舍弃掉了。另外，也可以再建立了部分的主语实体网页到候选实体网页的路径链接后，就终止网页抓取的过程，并舍弃掉其他未建立路径链接的候选实体网页。

另外，为了避免后续的随机游走的无限循环，在构建正向拓扑关系图的过程中，去除掉指向头节点的网页而链接。此外，为了让随机游走能够快速收敛，在各个候选实体网页对应的汇聚节点上，可以加上了指向自身的回边，从而使得随机游走能够终止于汇聚节点。

基于正向拓扑关系图的随机游走

在构建完正向拓扑关系图后或者伴随着正向拓扑关系图的构建过程，就可以采用随机游走的方式计算各个候选实体网页的权重值。具体地，先给上述的第一头节点分配初始的第一权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一游走轮次和/或汇聚节点被分配到权重值，获取随机游走结束时的各个第一汇聚节点的权重值，作为各个候选实体网页的权重值。

基于正向拓扑关系图获得的权重值排名

在获取到各个候选实体网页的权重值后，就可以根据权重值的大小进行排名，从而选择出排名靠前的候选实体网页的网页链接作为三元组中的宾语的值链接。

基于正向拓扑关系图的处理示例

下面通过一个具体示例来说明一下基于正向拓扑关系图的处理过程，如图2所示，其为正向拓扑关系图的示例结构框图200。具体的构建过程如下：

阶段A、输入三元组信息如下：

主语：德国国家足球队(以下简称德国队)的网页。主语对应的实体为德国队。

宾语：宾语值为名字为Mike的足球运动员(图中表示为足球运动员Mike)的网页，值链接(value link)缺失。

谓语(主语与宾语之间的关系)：该足球运动员效力于德国队。

针对上述三元组信息，本文的技术方案就是要获得缺失的值链接，即希望找到介绍足球运动员Mike的网页。

阶段B、查找候选实体网页

经过在网页数据库中，以Mike为关键字在各个网页的锚文本中进行匹配检索，以获得与Mike相关的候选实体网页。如图中所示，找到的候选实体网页为：名字为Mike的足球运动员的网页(图中表示为足球运动员Mike的网页205)和同样名字为Mike的滑雪运动员的网页(图中表示为滑雪运动员Mike的网页206)。

阶段C、构建正向拓扑关系图

从德国队的网页201开始，进行网页抓取，经过两轮次的网页抓取，形成了如图2所示的拓扑结构。其中，德国队的网页201为第一头节点、足球运动员Mike的网页205和滑雪运动员Mike的网页206为第一汇聚节点，其他网页为第一中间节点。

为了简化示例，仅对位于头节点和汇聚节点的链接路径上的中间实体节点赋予的具体化网页名称，对于没有在头节点和汇聚节点的链接路径上的中间实体节点，仅在图中表示为文本的图标，并在下文中简单地称为网页。

具体地，在第一轮的网页抓取过程中，根据德国队的网页201的锚文本中，抓取到了足球运动员Jack的网页202、德国世界杯的网页203以及德国的网页(介绍德国国家的网页)204以及网页207，第一轮的网页抓取获得的都是中间实体网页。

然后进行第二轮的网页抓取，根据足球运动员Jack的网页202的锚文本，抓取到了足球运动员Mike的网页205、网页208以及德国世界杯的网页203，根据德国世界杯的网页203的锚文本，抓取到了足球运动员Mike的网页205、网页209以及足球运动员Jack的网页202，根据德国的网页204，抓取到了滑雪运动员Mike的网页206和网页210。网页208、网页209以及网页210均为中间实体网页。

另外，为了避免后续的随机游走的无限循环，去除掉了网页207指向德国队的网页201的网页的边。此外，为了让随机游走能够快速收敛，对足球运动员Mike的网页205和滑雪运动员Mike的网页206加上了指向自身的回边，从而使得随机游走能够终止于第一汇聚节点。

阶段D、随机游走(Random walk)：求各个候选实体网页的权重

如图3、图4以及图5所示，图3为基于正向拓扑关系图进行第一轮随机游走的示例框图300，图4为基于正向拓扑关系图进行第二轮随机游走的示例框图400，图5为基于正向拓扑关系图的随机游走结果的示例框图500。为了便于形象说明上述的权重值的分配过程，在图中的箭头上的数字表示在本轮次中在箭头对应的出度方向上分配的权重值，在各个网页所在的方框或者圆圈中的数字表示在本轮次获得权重值。另外，对于每轮次的随机游走，图中仅示出了本轮次各个网页的初始的权重值和在出度方向上分配的权重值，而未示出在本轮次随机游走结束时，各个网页获得的权重值。在本轮次随机游走结束时，各个网页获得的权重值将会作为下一轮次的随机游走的各个网页的初始的权重值，因此，将标记在下一轮次的随机游走的示意图中。

第一轮次的随机游走(如图3所示)：从第一头节点出发，向德国队的网页201分配一个初始的权重值1，并按照德国队的网页201的出度，向其指向的足球运动员Jack的网页202、德国世界杯的网页203以及德国的网页204以及网页207均等地分配权重值，如图中所示，德国队的网页201的出度为4，在其各个出度上分配的权重值均为0.25，因此，足球运动员Jack的网页202、德国世界杯的网页203以及德国的网页204以及网页207在第一轮次的随机游走中都获得了0.25的权重值。另外，由于正向拓扑关系图中，除了德国队的网页201被分配了初始的权重值以外，其他的网页都没有权重值，因此，也无法向其他网页分配权重值。

第二轮次的随机游走(如图4所示)：在第二轮次的随机游走中，各个网页以在第一轮次结束时获得的权重值为第二轮次的初始的权重值继续进行权重值的分配。如图4所示，在第二轮次的随机游走中，德国队的网页201的初始的权重值为0，足球运动员Jack的网页202、德国世界杯的网页203以及德国的网页204以及网页207(图中标记出其获得的初始的权重值)的初始的权重值为0.25，由于网页207指向德国队的网页201边已经被去除掉，因此，网页207无法向德国队的网页201分配权重值。足球运动员Jack的网页202根据其出度，分别向网页208、足球运动员Mike的网页205以及德国世界杯的网页203分别分配了0.083的权重值。德国世界杯的网页203根据其出度，分别向网页209、足球运动员Jack的网页202以及足球运动员Mike的网页205分配了0.083的权重值。德国的网页204根据其出度，分别向网页210和滑雪运动员Mike的网页206分配了0.125的权重值。最终，经过第二轮的随机游走，足球运动员Jack的网页202获得了0.083的权重值，德国世界杯的网页203获得了0.083的权重值，足球运动员Mike的网页205获得了0.166的权重值，滑雪运动员Mike的网页206获得了0.125的权重值。

两轮次的随机游走后的结果(如图5所示)：第二轮随机游走结束后，作为中间实体网页的足球运动员Jack的网页202和德国世界杯的网页203的权重值均为0.083。作为候选实体网页的足球运动员Mike的网页205和滑雪运动员Mike的网页206的权重值分别为0.166和0.125。

如果将随机游走的轮次设定为两个轮次，则候选实体网页所获得权重值即为图5所示的结果。

如果将随机游走的轮次设定为三个轮次，则可以在图5所示的权重值分配情况的基础上，再进行一轮次的随机游走。在第三轮次的随机游走的过程中，足球运动员Jack的网页202和德国世界杯的网页203的初始权重值均为0.083，并根据各自出度继续进行权重值的分配。而由于足球运动员Mike的网页205和滑雪运动员Mike的网页206都增加了指向自身的回边，则不会再向其他的网页分配权重值，并将前一轮次获得的权重值积累下来。最终经过第三轮次的随机游走后，足球运动员Mike的网页205获得了来自足球运动员Jack的网页202分配来的权重值0.028(0.0083÷3≈0.028)和来自德国世界杯的网页203分配来的权重值0.028(0.0083÷3≈0.028)，再加上上一轮次获得的权重值0.166，最终足球运动员Mike的网页205的权重值变为0.222。而滑雪运动员Mike的网页206在第三轮次的随机游走中，没有获得新的权重值，其最终的权重值为0.125。

阶段E、基于正向拓扑关系图获得的权重值的排序

无论采用两轮次还是三轮次的随机游走，在进行排名后，足球运动员Mike的网页205获得的权重值都大于滑雪运动员Mike的网页206获得的权重值，因此，可以选择足球运动员Mike的网页205的网页链接作为上述的知识图谱中缺失的值链接。

从这个示例中可以看出，在路径关系方面，由于足球运动员Mike的网页205与德国队的网页201之间的直接或间接的关联关系要多于滑雪运动员Mike的网页206，因此，可以认为足球运动员Mike的网页205更适合作为上述三元组中宾语的值链接，这样的结果也是与事实相符的。

下面介绍一下基于反向拓扑图关系图的处理过程。

反向拓扑关系图的构建

反向拓扑关系图是从各个候选实体网页开始到主语实体网页为止的拓扑关系图。反向拓扑关系图的数量为多个，一般与候选实体网页的数量相对应。反向拓扑关系图的生成过程与正向拓扑关系图的生成过程的技术原理是一样的，只是建立拓扑关系图的方向是相反的。

在反向拓扑关系图中，以候选实体网页作为头节点，以主语实体网页作为汇聚节点。头节点和汇聚节点以外的节点为中间节点，中间节点对应着主语实体网页与候选实体网页以外的中间实体网页，这些中间节点会存在两种情况，一种是处于头节点和汇聚节点的链接路径上，这些中间实体网页直接或者间接地指向了主语实体网页，另一种是没有位于头节点和汇聚节点的链接路径上，这样的中间实体网页可以认为是与候选实体网页与主语实体网页之间的拓扑关系无关紧要的网页。为了与正向拓扑关系图中的各个节点进行区分，在下文中将反向拓扑关系图中的头结点、中间节点以及汇聚节点分别称作第二头节点、第二中间节点以及第二汇聚节点。

反向拓扑关系图的生成过程如下：

以候选实体网页作为第二头节点。

从该第二头节点开始，抓全该候选实体网页指向的多个中间实体网页或者主语实体网页，然后再从抓取到的各个中间实体网页继续抓取一个或多个新的中间实体网页和/或主语实体网页；具体地，可以通过候选实体网页或者中间实体网页中的锚文本来获得其指向的其他网页。

如此循环，直至到达预设的第二抓全轮次和/或形成了预设的第二数量的从候选实体网页到候选实体网页的路径，其中，将中间实体网页作为第二中间节点，将主语实体网页作为第二汇聚节点。

考虑到效率和拓扑关系图的有效性，可以对网页抓取的轮次进行一下限制，在指定的轮次中，如果没有构建出从候选实体网页到主语实体网页的路径关系，那么这个候选实体网页就可以舍弃掉了。

另外，为了避免后续的随机游走的无限循环，在构建反向拓扑关系图的过程中，去除掉指向头节点的网页而链接。此外，为了让随机游走能够快速收敛，在主语实体网页对应的汇聚节点上，可以加上了指向自身的回边，从而使得随机游走能够终止于汇聚节点。

基于反向拓扑关系图的随机游走

在构建完各个反向拓扑关系图后或者伴随着反向拓扑关系图的构建过程，就可以采用随机游走的方式计算各个候选实体网页的权重值。

具体地，基于各个反向拓扑关系图，给第二头节点分配初始的第二权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第二游走轮次和/或第二汇聚节点被分配到权重值，将基于反向拓扑关系图的随机游走结束时的各个反向拓扑关系图中的第二汇聚节点的权重值，作为各个反向拓扑关系图中的候选实体网页的权重值。

基于反向拓扑关系图获得的权重值排名

在基于各个反向拓扑关系图获取到各个候选实体网页的权重值后，可以直接根据该权重值对各个候选实体网页进行排名，从而选择出排名靠前的候选实体网页的网页链接作为三元组中的宾语的值链接。

基于反向拓扑关系图的处理示例

下面通过一个具体示例来说明一下基于反向拓扑关系图的处理过程，如图6和图7所示，图6为反向拓扑关系图的示例结构之一的框图600，图7为反向拓扑关系图的示例结构之二的框图700。该反向拓扑关系图构建过程，仍然以正向拓扑关系图中三元组作示例。

如前面的示例所提到的，经过前述示例的阶段A和阶段B后，查找到的候选实体网页为：足球运动员Mike的网页205和滑雪运动员Mike的网页206。

阶段C1、构建反向拓扑关系图

从足球运动员Mike的网页205出发，进行网页抓取，经过两轮次的网页抓取，形成了如图6所示拓扑结构。其中，足球运动员Mike的网页205为第二头节点、德国队的网页201为第二汇聚节点，德国世界杯的网页203、某足球俱乐部的网页601、某女明星的网页602、网页603、网页604以及网页605为第二中间节点。

从滑雪运动员Mike的网页206出发，进行网页抓取，经过两轮次的网页抓取，形成了如图7所示拓扑结构。其中，滑雪运动员Mike的网页206为第二头节点、德国队的网页201为第二汇聚节点，德国世界杯的网页203、某滑雪场的网页701、某运动品牌的网页702、冬奥会的网页706、某篮球运动员的网页707、网页703、网页704、网页705为第二中间节点。

具体的抓取过程，和构建正向拓扑关系图的处理过程类似，在此不再赘述。

阶段D1、随机游走

如图8和图9所示，其中，图8为基于图6的反向拓扑关系图进行第一轮随机游走的示例框图800，图9为基于图6的反向拓扑关系图进行第二轮随机游走的示例框图900。

基于图6的第一轮次的随机游走(如图8所示)：从作为第二头节点的足球运动员Mike的网页205出发，向足球运动员Mike的网页205分配一个初始的权重值1，并按照足球运动员Mike的网页205的出度，向其指向的网页均等地分配权重值，如图8所示，足球运动员Mike的网页205的出度为3，在其各个出度上分配的权重值均为0.33，因此，德国世界杯的网页203、某足球俱乐部的网页601以及某女明星的网页602分别被分配了0.33的权重值。

基于图6的第二轮次的随机游走(如图9所示)：在第二轮次的随机游走中，各个网页以在第一轮次结束时获得的权重值为第二轮次的初始的权重值继续进行权重值的分配。如图9所示，德国世界杯的网页203、某足球俱乐部的网页601以及某女明星的网页602的出度均为2，向其指向的网页分配的权重值均为0.165。

经过两个轮次的随机游走后，图6中的德国队的网页201累计获得权重值为0.495，由于基于反向拓扑关系图计算权重值的目的是为了对候选实体网页进行筛选，因此，将权重值0.495作为足球运动员Mike的网页205的权重值。

如图10和图11所示，其中，图10为基于图7的反向拓扑关系图进行第一轮随机游走的示例框图1000，图11为基于图7的反向拓扑关系图进行第二轮随机游走的示例框图1100。

基于图7的第一轮次的随机游走(如图10所示)：从作为第二头节点的滑雪运动员Mike的网页206出发，向滑雪运动员Mike的网页206分配一个初始的权重值1，并按照滑雪运动员Mike的网页206的出度，向其指向的网页均等地分配权重值，如图10所示，滑雪运动员Mike的网页206的出度为3，在其各个出度上分配的权重值均为0.33，因此，德国世界杯的网页203、某滑雪场的网页701以及某运动品牌的网页702分别被分配了0.33的权重值。

基于图7的第二轮次的随机游走(如图11所示)：在第二轮次的随机游走中，各个网页以在第一轮次结束时获得的权重值为第二轮次的初始的权重值继续进行权重值的分配。如图11所示，德国世界杯的网页203、某滑雪场的网页701以及某运动品牌的网页702的出度均为2，向其指向的网页分配的权重值均为0.165。

经过两个轮次的随机游走后，图7中的德国队的网页201累计获得权重值为0.165，由于基于反向拓扑关系图计算权重值的目的是为了对候选实体网页进行筛选，因此，将权重值0.165作为滑雪运动员Mike的网页206的权重值。

阶段E1、基于反向拓扑关系图获得的权重值的排序

通过比较可知滑雪运动员Mike的网页206的权重值小于足球运动员Mike的网页205的权重值，因此，选择足球运动员Mike的网页205的网页链接作为三元组的中宾语的值链接。

正向拓扑关系图和反向拓扑关系图的结合应用

正向拓扑关系图和反向拓扑关系图从两个方向上挖掘了主语实体网页与候选实体网页之间的关联关系，在实际应用中，可以将正向拓扑关系图和反向拓扑关系图相结合来计算候选实体网页的权重值。

具体地，按照前面介绍的正向拓扑关系图和反向拓扑关系图的构建方式分别构建出正向拓扑关系图和反向拓扑关系图。按照前面介绍的基于正向拓扑关系图的随机游走的方式，求出的各个候选实体网页在正向拓扑关系图中的权重值作为第一中间权重值，按照前面介绍的基于反向拓扑关系图的随机游走的方式，求出的各个候选实体网页在反向拓扑关系图中的权重值作为第二中间权重值。将每个候选实体网页的第一中间权重值和第二中间权重值进行相加，获得该候选实体网页的最终权重值。最后，根据该最终权重值的大小进行排名，从而选择出排名靠前的候选实体网页的网页链接作为三元组中的宾语的值链接。

将正向拓扑关系图和反向拓扑关系图相结合而计算出的候选实体网页的权重值，能够更加全面地体现出主语实体网页与候选实体网页之间的关联关系，从而获得更加准确的值链接。

正向拓扑关系图和反向拓扑关系图的结合应用示例

仍然以图2至图11中提到的三元组信息作为示例，如前面所介绍的，在分别基于上述的图2所示的正向拓扑关系图以及图6和图7所示的反向拓扑关系图，计算出候选实体网页的权重值(以两个轮次的随机游走为例)后，再分别进行相加，从而获得各个候选实体网页的最终权重值。

具体地，足球运动员Mike的网页205和滑雪运动员Mike的网页206在图2中获得的权重值(基于两个轮次的随机游走)分别为0.166和0.125。

足球运动员Mike的网页205在图6中获得权重值为0.495，滑雪运动员Mike的网页206在图7中获得的权重值为0.165。

将基于正向拓扑关系图和反向拓扑关系图的权重值进行分别相加，足球运动员Mike的网页205最终获得的权重值为0.661，滑雪运动员Mike的网页206最终获得的权重值为0.29。

经过排名处理可知，足球运动员Mike的网页205的权重值远高于滑雪运动员Mike的网页206的权重值，因此，选择足球运动员Mike的网页205的网页链接作为三元组的中宾语的值链接。

说明性过程

如图12所示，其为描绘本文的网页链接的获取方法的流程示意图。该方法的处理过程包括：

S1201：根据宾语值检索与该宾语值相关的多个候选实体网页。

S1202：构建主语实体网页与多个候选实体网页之间的拓扑关系图，并根据拓扑关系图中候选实体网页与主语实体网页之间的路径关系，计算各个候选实体网页的权重值。

具体地，构建主语实体网页与多个候选实体网页之间的拓扑关系图可以包括：构建从主语实体网页到多个候选实体网页的正向拓扑关系图，和/或，构建从各个候选实体网页到主语实体网页的多个反向拓扑关系图。

计算各个候选实体网页的权重值可以包括：采用随机游走的方式，计算候选实体网页的权重值。其中，该权重值可以是基于正向拓扑关系图获得的权重值，也可以是基于反向拓扑关系图获得的权重值，也可以是基于正向拓扑关系图和反向拓扑关系图的结合而获得的权重值。

S1203：根据各个候选实体网页的权重值进行排名，并根据排名结果确定宾语值对应的值链接。

以上介绍了本文的实体网页链接的获取方法的主要处理流程，其技术细节以及相应的技术效果在前文的介绍中进行了详细说明，在此不再赘述。

电子装置实现示例

本公开的电子装置可以是具有可移动性的电子设备，也可以是较少移动的或者非移动的计算设备。本公开的电子装置至少具有处理单元和存储器，存储器上存储有指令，处理单元从存储器上获取指令，并执行处理，以使电子装置执行动作。

在一些例子中，上述图1至图12涉及的一个或多个模块或者一个或多个步骤或者一个或多个处理过程，可以通过软件程序、硬件电路，也可以通过软件程序和硬件电路相结合的方式来实现。例如，上述各个组件或者模块以及一个或多个步骤都可在芯片上系统(SoC)中实现。SoC可包括：集成电路芯片，该集成电路芯片包括以下一个或多个：处理单元(如中央处理单元(CPU)、微控制器、微处理单元、数字信号处理单元(DSP)等)、存储器、一个或多个通信接口、和/或用于执行其功能的进一步的电路和可任选的嵌入的固件。

如图13所示，其为示例性的具有可移动性的电子设备1300的结构框图。该电子设备1300可以是小型因素便携式(或移动)电子设备。这里所说的小型因素便携式(或移动)电子设备可以是：例如，蜂窝电话、个人数据助理(PDA)、笔记本电脑、平板电脑、个人媒体播放器装置、无线网络观看装置、个人头戴装置、专用装置或包括以上功能中的任何一个的混合装置。电子设备1300至少包括：存储器1301和处理器1302。

存储器1301，用于存储程序。除上述程序之外，存储器1301还可被配置为存储其它各种数据以支持在电子设备1300上的操作。这些数据的示例包括用于在电子设备1300上操作的任何应用程序或方法的指令，联系人数据，电话簿数据，消息，图片，视频等。

存储器1301可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，如静态随机存取存储器(SRAM)，电可擦除可编程只读存储器(EEPROM)，可擦除可编程只读存储器(EPROM)，可编程只读存储器(PROM)，只读存储器(ROM)，磁存储器，快闪存储器，磁盘或光盘。

存储器1301耦合至处理器1302并且包含存储于其上的指令，所说的指令在由处理器1302执行时使电子设备执行动作，作为一种电子设备的实施例，该动作可以包括：执行上述图12对应的实体网页链接的获取方法的处理操作，或者执行图1至图11所介绍的网页链接的获取装置的处理逻辑的处理操作。

对于上述的处理操作，在前面方法和装置的相关内容中已经进行了详细说明，对于上述的处理操作的详细内容同样也适用于电子设备1300中，即可以将前面实施例中提到的具体处理操作，以程序的方式写入在存储器1301，并通过处理器1302来进行执行。

进一步，如图13所示，电子设备1300还可以包括：通信组件1303、电源组件1304、音频组件1305、显示器1306、芯片组1307等其它组件。图13中仅示意性给出部分组件，并不意味着电子设备1300只包括图13所示组件。

通信组件1303被配置为便于电子设备1300和其他设备之间有线或无线方式的通信。电子设备可以接入基于通信标准的无线网络，如WiFi，2G、3G、4G以及5G或它们的组合。在一个示例性实施例中，通信组件1303经由广播信道接收来自外部广播管理系统的广播信号或广播相关信息。在一个示例性实施例中，通信组件1303还包括近场通信(NFC)模块，以促进短程通信。例如，在NFC模块可基于射频识别(RFID)技术，红外数据协会(IrDA)技术，超宽带(UWB)技术，蓝牙(BT)技术和其他技术来实现。

电源组件1304，为电子设备的各种组件提供电力。电源组件1304可以包括电源管理系统，一个或多个电源，及其他与为电子设备生成、管理和分配电力相关联的组件。

音频组件1305被配置为输出和/或输入音频信号。例如，音频组件1305包括一个麦克风(MIC)，当电子设备处于操作模式，如呼叫模式、记录模式和语音识别模式时，麦克风被配置为接收外部音频信号。所接收的音频信号可以被进一步存储在存储器1301或经由通信组件1303发送。在一些实施例中，音频组件1305还包括一个扬声器，用于输出音频信号。

显示器1306包括屏幕，其屏幕可以包括液晶显示器(LCD)和触摸面板(TP)。如果屏幕包括触摸面板，屏幕可以被实现为触摸屏，以接收来自用户的输入信号。触摸面板包括一个或多个触摸传感器以感测触摸、滑动和触摸面板上的手势。触摸传感器可以不仅感测触摸或滑动动作的边界，而且还检测与触摸或滑动操作相关的持续时间和压力。

上述的存储器1301、处理器1302、通信组件1303、电源组件1304、音频组件1305以及显示器1306可以与芯片组1307连接。芯片组1307可以提供处理器1302与电子设备1300中的其余组件之间的接口。此外，芯片组1307还可以提供电子设备1300中的各个组件对存储器1301的访问接口以及各个组件间相互访问的通讯接口。

在一些例子中，上述图1至图12涉及的一个或多个模块或者一个或多个步骤或者一个或多个处理过程，可以通过具有操作系统和硬件配置的计算设备来实现。

图14其为示例性的计算设备1400的结构框图。此处所提供的对计算机1400的描述只是为了说明，并不是限制性的。实施例也可以在相关领域的技术人员所知的其它类型的计算机系统中实现。

如图14所示，计算设备1400包括一个或多个处理器1402、系统存储器1404，以及将包括系统存储器1404的各种系统组件耦合到处理器1402的总线1406。总线1406表示若干类型的总线结构中的任何一种总线结构的一个或多个，包括存储器总线或存储器控制器、外围总线、加速图形端口，以及处理器或使用各种总线体系结构中的任何一种的局部总线。系统存储器1404包括只读存储器(ROM)1408和随机存取存储器(RAM)1410。基本输入/输出系统1412(BIOS)储存在ROM 1408中。

计算机系统1400还具有一个或多个以下驱动器：用于读写硬盘的硬盘驱动器1414、用于读或写可移动磁盘1418的磁盘驱动器1416、以及用于读或写诸如CD ROM、DVDROM或其他光介质之类的可移动光盘1422的光盘驱动器1420。硬盘驱动器1414、磁盘驱动器1416，以及光驱动器1420分别通过硬盘驱动器接口1424、磁盘驱动器接口1426，以及光学驱动器接口1428连接到总线1406。驱动器以及它们相关联的计算机可读介质为计算机提供了对计算机可读指令、数据结构、程序模块，及其他数据的非易失存储器。虽然描述了硬盘、可移动磁盘和可移动光盘，但是，也可以使用诸如闪存卡、数字视频盘、随机存取存储器(RAM)、只读存储器(ROM)等等之类的其他类型的计算机可读存储介质来储存数据。

数个程序模块可被储存在硬盘、磁盘、光盘、ROM或RAM上。这些程序包括操作系统1430、一个或多个应用程序1432、其他程序1434以及程序数据1436。这些程序可包括例如用于实现图1至图12所示的示例所执行的处理流程和处理逻辑。

用户可以通过诸如键盘1438和指点设备1440之类的输入设备向计算设备1400中输入命令和信息。其它输入设备(未示出)可包括话筒、控制杆、游戏手柄、卫星天线、扫描仪、触摸屏和/或触摸平板、用于接收语音输入的语音识别系统、用于接收手势输入的手势识别系统、诸如此类。这些及其他输入设备可通过耦合到总线1406的串行端口接口1442连接到处理器1402，但也可以通过其他接口(诸如并行端口、游戏端口、通用串行总线(USB)端口)来进行连接。

显示屏1444也通过诸如视频适配器1446之类的接口连接到总线1406。显示屏1444可在计算设备1400外部或纳入其中。显示屏1444可显示信息，以及作为用于接收用户命令和/或其它信息(例如，通过触摸、手指姿势、虚拟键盘等等)的用户界面。除了显示屏1444之外，计算设备1400还可包括其他外围输出设备(未示出)，如扬声器和打印机。

计算机1400通过适配器或网络接口1450、调制解调器1452、或用于通过网络建立通信的其他手段连接到网络1448(例如，因特网)。可以是内置的或外置的调制解调器1452可以经由串行端口接口1442连接到总线1406，如图14所示，或者可以使用包括并行接口的另一接口类型连接到总线1406。

如此处所用的，术语“计算机程序介质”、“计算机可读介质”以及“计算机可读存储介质”被用于泛指介质，诸如与硬盘驱动器1414相关联的硬盘、可移动磁盘1418、可移动光盘1422、系统存储器1404、闪存卡、数字视频盘、随机读取存储器(RAM)、只读存储器(ROM)以及其它类型的物理/有形存储介质等。这些计算机可读存储介质与通信介质(不包括通信介质)相区别且不重叠。通信介质通常在诸如载波等已调制数据信号中承载计算机可读指令、数据结构、程序模块或者其它数据。术语“已调制数据信号”是指使得以在信号中编码信息的方式来设定或改变其一个或多个特征的信号。作为示例而非限制，通信介质包括诸如声学、RF、红外线的无线介质和其它无线介质以及有线介质。各个实施例也针对这些通信介质。

如上文所指示的，计算机程序和模块(包括应用程序1432及其他程序1434)可被储存在硬盘、磁盘、光盘、ROM或RAM上。这样的计算机程序也可以通过网络接口1450、串行端口接口1442或任何其他接口类型来接收。这些计算机程序在由应用程序执行或加载时使得计算机1400能够实现此处所讨论的实施例的特征。因此，这些计算机程序表示计算机系统1400的控制器。

这样，各个实施例还涉及包括储存在任何计算机可用存储介质上的计算机指令/代码的计算机程序产品。这样的代码/指令当在一个或多个数据处理设备中执行时，使数据处理设备如此处所描述的那样操作。可包括计算机可读存储介质的计算机可读存储设备的示例包括诸如RAM、硬盘驱动器、软盘驱动器、CD ROM驱动器、DVD DOM驱动器、压缩盘驱动器、磁带驱动器、磁性存储设备驱动器、光学存储设备驱动器、MEM设备、基于纳米技术的存储设备等的存储设备以及其它类型的物理/有形计算机可读存储设备。

示例条款

A：一种方法，包括：

根据宾语值检索与该宾语值相关的多个候选实体网页；

构建主语实体网页与多个所述候选实体网页之间的拓扑关系图，并根据所述拓扑关系图中所述候选实体网页与主语实体网页之间的路径关系，计算各个候选实体网页的权重值；

根据各个候选实体网页的权重值进行排名，并根据排名结果确定宾语值对应的值链接。

B：根据段落A所述方法，所述构建主语实体网页与多个所述候选实体网页之间的拓扑关系图包括：

构建从所述主语实体网页到多个所述候选实体网页的正向拓扑关系图，和/或，构建从各个所述候选实体网页到所述主语实体网页的多个反向拓扑关系图。

C：根据段落B所述的方法，所述计算各个候选实体网页的权重值包括：采用随机游走的方式，计算所述候选实体网页的权重值。

D：根据段落A所述的方法，其中，所述拓扑关系图包括正向拓扑关系图，所述正向拓扑关系图包括第一头节点、第一中间节点以及第一汇聚节点，

所述构建主语实体网页与多个所述候选实体网页之间的拓扑关系图包括：

将所述主语实体网页作为第一头节点；

从该主语实体网页开始，抓取该主语实体网页指向的多个中间实体网页和/或所述候选实体网页，然后再从抓取到的各个中间实体网页继续抓取一个或多个新的中间实体网页和/或所述候选实体网页；

如此循环，直至到达预设的第一抓取轮次和/或形成了预设的第一数量的从所述主语实体网页到所述候选实体网页的路径，其中，将所述中间实体网页作为第一中间节点，将所述候选实体网页作为所述第一汇聚节点。

E：根据段落D所述的方法，其中，所述计算各个候选实体网页的权重值包括：给所述第一头节点分配初始的第一权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一游走轮次和/或所述汇聚节点被分配到权重值，获取随机游走结束时的各个第一汇聚节点的权重值，作为各个候选实体网页的权重值。

F：根据段落D所述的方法，其中，所述拓扑关系图还包括多个反向拓扑关系图，所述反向拓扑关系图包括第二头节点、第二中间节点以及第二汇聚节点，

所述构建主语实体网页与多个所述候选实体网页之间的拓扑关系图还包括：采用如下方式分别构建各个所述候选实体网页到所述主语实体网页的多个反向拓扑关系图：

以候选实体网页作为第二头节点；

从该第二头节点开始，抓全该候选实体网页指向的多个中间实体网页或者所述主语实体网页，然后再从抓取到的各个中间实体网页继续抓取一个或多个新的中间实体网页和/或所述主语实体网页；

如此循环，直至到达预设的第二抓全轮次和/或形成了预设的第二数量的从所述候选实体网页到所述候选实体网页的路径，其中，将所述中间实体网页作为第二中间节点，将所述主语实体网页作为所述第二汇聚节点。

G：根据段落F所述的方法，其中，所述计算各个候选实体网页的权重值包括：

基于正向拓扑关系图，给所述第一头节点分配初始的第一权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一游走轮次和/或所述汇聚节点被分配到权重值，将基于所述正向拓扑关系图的随机游走结束时的各个第一汇聚节点的权重值作为对应候选实体网页的第一中间权重值；

基于各个所述反向拓扑关系图，给所述第二头节点分配初始的第二权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第二游走轮次和/或所述第二汇聚节点被分配到权重值，将基于所述反向拓扑关系图的随机游走结束时的各个反向拓扑关系图中的第二汇聚节点的权重值，作为各个反向拓扑关系图中的候选实体网页的第二中间权重值；

将各个所述候选实体网页的第一中间权重值和第二中间权重值进行相加而获得的权重值，作为各个所述候选实体网页的权重值。

H：根据段落A所述的方法，其中，所述根据宾语值检索与该宾语值相关的多个候选实体网页包括：

将所述宾语值与网页中的锚文本进行匹配检索，以获取与该宾语值相关的多个候选实体网页。

I：根据段落D所述的方法，其中，

在构建所述正向拓扑关系图的过程中，去掉指向所述第一头节点的节点链接，在所述第一汇聚节点上增加指向自身的回边。

J：根据段落F所述的方法，其中，

在构建所述正向拓扑关系图的过程中，去掉指向所述第一头节点的节点链接，在所述第一汇聚节点上增加指向自身的回边；

在构建所述反向拓扑关系图的过程中，去掉指向所述第二头节点的节点链接，在所述第二汇聚节点上增加指向自身的回边；

K：一种装置，包括：

候选实体网页获取模块，用于根据宾语值检索与该宾语值相关的多个候选实体网页；

拓扑关系图构建模块，用于构建主语实体网页与多个所述候选实体网页之间的拓扑关系图；

权重值计算模块，用于根据所述拓扑关系图中所述候选实体网页与主语实体网页之间的路径关系，计算各个候选实体网页的权重值；

排名模块，用于根据各个候选实体网页的权重值进行排名，并根据排名结果确定宾语值对应的值链接。

L：根据段落K所述的装置，其中，所述拓扑关系图包括正向拓扑关系图，所述正向拓扑关系图包括第一头节点、第一中间节点以及第一汇聚节点，

将所述主语实体网页作为第一头节点；

M：根据段落L所述的装置，其中，所述计算各个候选实体网页的权重值包括：

给所述第一头节点分配初始的第一权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一游走轮次和/或所述汇聚节点被分配到权重值，获取随机游走结束时的各个第一汇聚节点的权重值，作为各个候选实体网页的权重值。

N：根据段落L所述的装置，其中，所述拓扑关系图还包括多个反向拓扑关系图，所述反向拓扑关系图包括第二头节点、第二中间节点以及第二汇聚节点，

以候选实体网页作为第二头节点；

O：根据段落N述的装置，其中，所述计算各个候选实体网页的权重值包括：

P：根据段落K所述的装置，其中，所述根据宾语值检索与该宾语值相关的多个候选实体网页包括：

Q：一种电子设备，包括：

处理单元；以及

存储器，耦合至所述处理单元并且包含存储于其上的指令，所述指令在由所述处理单元执行时使所述设备执行动作，所述动作包括：

根据宾语值检索与该宾语值相关的多个候选实体网页；

R：根据段落Q所述的电子设备，其中，所述构建主语实体网页与多个所述候选实体网页之间的拓扑关系图包括：

S：根据段落Q所述的电子设备，其中，所述拓扑关系图包括正向拓扑关系图，所述正向拓扑关系图包括第一头节点、第一中间节点以及第一汇聚节点，

将所述主语实体网页作为第一头节点；

T：根据段落Q所述的电子设备，其中，所述计算各个候选实体网页的权重值包括：给所述第一头节点分配初始的第一权重值，并采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一游走轮次和/或所述汇聚节点被分配到权重值，获取随机游走结束时的各个第一汇聚节点的权重值，作为各个候选实体网页的权重值。

U：根据段落S所述的电子设备，其中，所述拓扑关系图还包括多个反向拓扑关系图，所述反向拓扑关系图包括第二头节点、第二中间节点以及第二汇聚节点，

以候选实体网页作为第二头节点；

V：根据段落U所述的电子设备，其中，所述计算各个候选实体网页的权重值包括：

结语

系统的多个方面的硬件与软件实现之间区别不大；使用硬件还是软件通常(但并不总是，因为在某些背景下，硬件与软件之间的选择可以变得显著)是表示成本与效率权衡的设计选择。存在可以实现在此描述的处理和/或系统和/或其它技术(例如，硬件、软件，以及/或固件)的各种承载工具，并且优选承载工具将随着部署该处理和/或系统和/或其它技术的背景而改变。例如，如果实现方确定速度和准确度最重要，则该实现方可以选择主要硬件和/或固件承载工具；如果灵活性最重要，则该实现方可以选择主要软件实现；或者，此外又另选地，该实现方可以选择硬件、软件，以及/或固件的一些组合。

前述详细描述已经经由使用框图、流程图，以及/或示例阐述了该装置和/或处理的各种实施方式。至于这种框图、流程图，以及/或示例包含一个或更多个功能和/或操作，本领域技术人员应当明白，这种框图、流程图，或示例内的每一个功能和/或操作可以单独地和/或共同地，通过宽范围的硬件、软件、固件，或者实际上其任何组合来实现。在一个实施方式中，在此描述的主旨的几个部分可以经由专用集成电路(ASIC)、现场可编程门阵列(FPGA)、数字信号处理器(DSP)，或其它集成格式来实现。然而，本领域技术人员应当认识到，在此公开的实施方式的一些方面整个地或者部分地可以等同地在集成电路中实现，实现为运行在一个或更多个计算机上的一个或更多个计算机程序(例如，实现为运行在一个或更多个计算机系统上的一个或更多个程序)，实现为运行在一个或更多个处理器上的一个或更多个程序(例如，实现为运行在一个或更多个微处理器上的一个或更多个程序)，实现为固件，或者实际上实现为其任何组合，并且根据本公开，设计电路和/或编写用于软件和/或固件的代码完全处于本领域技术人员的技术内。另外，本领域技术人员应当清楚的是，在此描述的主题的机制能够按多种形式作为程序产品分配，并且在此描述的主题的例示性实施方式适用，而与被用于实际执行该分配的特定类型的信号承载介质无关。信号承载介质的示例包括但不限于，以下：可记录型介质，如软盘、硬盘驱动器(HDD)、质密盘(CD)、数字通用盘(DVD)、数字磁带、计算机存储器等；和传输型介质，如数字和/或模拟通信媒介(例如，光纤线缆、波导管、有线通信链路、无线通信链路等)。

本领域技术人员应当认识到，按在此阐述的方式来描述装置和/或处理，并且此后，使用工程实践将这样描述的装置和/或处理集成到数据处理系统中是本领域内常见的。即，在此描述的装置和/或处理的至少一部分可以经由合理量的实验而集成到数据处理系统中。本领域技术人员应当认识到的是，通常的数据处理系统通常包括以下中的一个或更多个：系统单元外壳、视频显示装置、诸如易失性和非易失性存储器的存储器、诸如微处理器和数字信号处理器的处理器、诸如操作系统、驱动器、图形用户接口，以及应用程序的计算实体、诸如触摸板或触摸屏的一个或更多个交互式装置，以及/或包括反馈回路和控制电动机的控制系统(例如，用于感测位置和/或速度的反馈；用于移动和/或调节组件和/或数量的控制马达)。通常的数据处理系统可以利用任何合适商业可获组件来实现，如通常在数据计算/通信和/或网络通信/计算系统中找到的那些。

在此描述的主题有时例示了包含在不同的其它组件内或与其相连接的不同组件。要明白的是，这样描绘的架构仅仅是示例性的，并且实际上，可以实现获得相同功能的许多其它架构。在概念意义上，用于获得相同功能的组件的任何排布结构都有效地“关联”，以使获得希望功能。因此，在此为获得特定功能而组合的任两个组件都可以被看作彼此“相关联”，以使获得希望功能，而与架构或中间组件无关。同样地，这样关联的任两个组件还可以被视作彼此“可操作地连接”，或“可操作地耦接”，以获得希望功能，并且能够这样关联的任两个组件也可以被视作可彼此“操作地耦接”，以获得希望功能。可操作地耦接的具体示例包括但不限于，物理上可配合和/或物理上交互的组件和/或可无线地交互和/或无线地交互的组件和/或逻辑上交互和/或逻辑上可交互组件。

针对在此实质上使用的任何复数和/或单数术语，本领域技术人员可以针对背景和/或应用在适当时候从复数翻译成单数和/或从单数翻译成复数。为清楚起见，各种单数/多数置换在此可以确切地阐述。

本领域技术人员应当明白，一般来说，在此使用的，而且尤其是在所附权利要求书中(例如，所附权利要求书的主体)使用的术语通常旨在作为“开放式”措辞(例如，措辞“包括(including)”应当解释为“包括但不限于”，措辞“具有(having)”应当解释为“至少具有”应当解释为“包括但不限于”等)。本领域技术人员还应当明白，如果想要特定数量的介绍权利要求列举，则这种意图将明确地在该权利要求中陈述，并且在没有这些列举的情况下，不存在这种意图。例如，为帮助理解，下面所附权利要求书可以包含使用介绍性短语“至少一个”和“一个或更多个”来介绍权利要求列举。然而，使用这种短语不应被认作，暗示由不定冠词“一(a)”或“一(an)”介绍的权利要求列举将包含这种介绍权利要求列举的任何特定权利要求限制于仅包含一个这种列举的发明，即使同一权利要求包括介绍性短语“一个或更多个”或“至少一个”以及诸如“一(a)”或“一(an)”的不定冠词(例如，“一(a)”或“一(an)”通常应当被解释成意指“至少一个”或“一个或更多个”)；其对于使用为介绍权利要求列举而使用的定冠词来说同样保持为真。另外，即使明确地陈述特定数量的介绍权利要求列举，本领域技术人员也应当认识到，这种列举通常应当被解释成，至少意指所陈述数量(例如，“两个列举”的仅有的列举在没有其它修饰语的情况下通常意指至少两个列举，或者两个或更多个列举)。而且，在使用类似于“A、B，以及C等中的至少一个”的惯例的那些实例中，一般来说，这种句法结构希望本领域技术人员在意义上应当理解这种惯例(例如，“具有A、B，以及C中的至少一个的系统”应当包括但不限于具有单独A、单独B、单独C、A和B一起、A和C一起、B和C一起，以及/或A、B以及C一起等的系统)。在使用类似于“A、B，或C等中的至少一个”的惯例的那些实例中，一般来说，这种句法结构希望本领域技术人员在意义上应当理解这种惯例(例如，“具有A、B，或C中的至少一个的系统”应当包括但不限于具有单独A、单独B、单独C、A和B一起、A和C一起、B和C一起，以及/或A、B以及C一起等的系统)。本领域技术人员还应当明白的是，实际上，呈现两个或更多个另选术语的任何转折词和/短语(无论处于描述、权利要求书中，还是在附图中)应当被理解成，设想包括这些术语、这些术语中的任一个，或者两个术语的可能性。例如，短语“A或B”应当被理解成，包括“A”或“B”或“A和B”的可能性。

本说明书中针对“实现方式”、“一个实现方式”、“一些实现方式”，或“其它实现方式”的引用可以意指，结合一个或更多个实现方式描述的特定特征、结构，或特性可以被包括在至少一些实现方式中，但不必被包括在所有实现方式中。前述描述中不同出现的“实现方式”、“一个实现方式”，或“一些实现方式”不必全部针对同一实现方式而引用。

虽然利用不同方法和系统描述和示出了特定示例性技术，但本领域技术人员应当明白，在不脱离要求保护的主题的情况下，可以进行各种其它修改，并且可以代替等同物。另外，在不脱离在此描述的中心概念的情况下，可以进行许多修改以使适应针对要求保护的主题的教导的特定情况。因此，要求保护的主题不限于所公开的特定示例，而是这种要求保护的主题还可以包括落入所附权利要求书及其等同物的范围内的所有实现。

尽管已经用结构特征和/或方法动作专用的语言描述了本主题，但要理解，所附权利要求书中定义的主题不必限于所描述的具体特征或动作。而是，这些具体特征和动作是作为实现该权利要求的解说性形式而公开的。

除非另外具体声明，否则在上下文中可以理解并一般地使用条件语言(诸如“能”、“能够”、“可能”或“可以”)表示特定示例包括而其他示例不包括特定特征、元素和/或步骤。因此，这样的条件语言一般并非旨在暗示对于一个或多个示例以任何方式要求特征、元素和/或步骤，或者一个或多个示例必然包括用于决定的逻辑、具有或不具有用户输入或提示、在任何特定实施例中是否要包括或要执行这些特征、元素和/或步骤。

除非另外具体声明，应理解联合语言(诸如短语“X、Y或Z中至少一个”)表示项、词语等可以是X、Y或Z中的任一者、或其组合。

本文所述和/或附图中描述的流程图中任何例行描述、元素或框应理解成潜在地表示包括用于实现该例程中具体逻辑功能或元素的一个或多个可执行指令的代码的模块、片段或部分。替换示例被包括在本文描述的示例的范围内，其中各元素或功能可被删除，或与所示出或讨论的顺序不一致地执行，包括基本上同步地执行或按相反顺序执行，这取决于所涉及的功能，如本领域技术人也将理解的。

应当强调，可对上述示例作出许多变型和修改，其中的元素如同其他可接受的示例那样应被理解。所有这样的修改和变型在此旨在包括在本公开的范围内并且由以下权利要求书保护。

本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

Claims

1.一种用于获取网页链接的方法，包括：

根据第二实体的名称检索与所述第二实体的名称相关的多个候选实体网页；

部分地通过从抓取到的多个中间实体网页抓取一个或多个新的中间实体网页或所述多个候选实体网页来构建第一实体网页与所述多个候选实体网页之间的拓扑关系图，其中，将所述抓取到的多个中间实体网页用作第一中间节点，并且将所述候选实体网页中的一个候选实体网页用作第一汇聚节点，并且其中，基于所述第一实体网页和第一汇聚节点之间的路径抓取所述一个或多个新的中间实体网页；

确定所述第一实体网页与所述多个候选实体网页中的各个候选实体网页之间的所述拓扑关系图中节点的出度，其中，所述出度包括从所述第一实体网页通向各个候选实体网页的各条边的比例值；

根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系，计算所述候选实体网页的权重值，其中，所述权重值表示直接通向各个候选实体网页的所述出度之和；以及

根据所述候选实体网页的权重值进行排名，并且根据所进行的排名的排名结果确定所述第二实体的名称对应的网页链接。

2.根据权利要求1所述方法，其中，所述构建第一实体网页与所述多个候选实体网页之间的拓扑关系图包括：

构建从所述第一实体网页到所述多个候选实体网页的正向拓扑关系图，和/或构建从所述候选实体网页到所述第一实体网页的多个反向拓扑关系图。

3.根据权利要求2所述的方法，其中，根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系计算所述候选实体网页的权重值包括：采用随机游走的方式，计算所述候选实体网页的权重值。

4.根据权利要求1所述的方法，其中，所述拓扑关系图包括正向拓扑关系图，并且所述正向拓扑关系图包括所述第一实体网页、第一中间节点以及所述第一汇聚节点，

所述构建第一实体网页与所述多个候选实体网页之间的拓扑关系图包括：

进行以下操作直至到达预设的第一抓取轮次或形成了预设的第一数量的从所述第一实体网页到所述候选实体网页的路径：

从所述第一实体网页开始，抓取所述第一实体网页指向的所述多个中间实体网页或所述候选实体网页。

5.根据权利要求4所述的方法，其中，根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系计算所述候选实体网页的权重值包括：

给所述第一实体网页分配初始的第一权重值，采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一随机游走轮次和/或汇聚节点被分配到权重值，并且获取所述随机游走结束时的所述第一汇聚节点的权重值，作为所述候选实体网页的权重值。

6.根据权利要求4所述的方法，其中，所述拓扑关系图还包括多个反向拓扑关系图，并且所述反向拓扑关系图包括所述候选实体网页、第二中间节点以及第二汇聚节点，

所述构建第一实体网页与所述多个候选实体网页之间的拓扑关系图还包括：采用如下方式分别构建从所述候选实体网页到所述第一实体网页的所述多个反向拓扑关系图：

进行以下操作直至到达预设的第二抓取轮次或形成了预设的第二数量的从所述候选实体网页到所述第一实体网页的路径：

从所述候选实体网页开始，抓取所述候选实体网页指向的所述多个中间实体网页或者所述第一实体网页；以及

从所述抓取到的多个中间实体网页抓取一个或多个新的中间实体网页或所述第一实体网页，其中，将所述抓取到的多个中间实体网页用作第二中间节点，并且将所述第一实体网页用作所述第二汇聚节点，并且其中，基于所述候选实体网页和所述第二汇聚节点之间的路径抓取所述一个或多个新的中间实体网页。

7.根据权利要求6所述的方法，其中，根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系计算所述候选实体网页的权重值包括：

基于所述正向拓扑关系图，给所述第一实体网页分配初始的第一权重值；

采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第一随机游走轮次或汇聚节点被分配到权重值，并且将基于所述正向拓扑关系图的所述随机游走结束时的所述第一汇聚节点的权重值用作对应所述候选实体网页的第一中间权重值；

基于所述反向拓扑关系图，给所述候选实体网页分配初始的第二权重值；

采用随机游走的方式，按照节点的出度进行权重值分配，直至达到预设的第二随机游走轮次或所述第二汇聚节点被分配到权重值，并且将基于所述反向拓扑关系图的所述随机游走结束时的所述反向拓扑关系图中的第二汇聚节点的权重值用作所述反向拓扑关系图中的所述候选实体网页的第二中间权重值；以及

将各个候选实体网页的所述第一中间权重值中的一个第一中间权重值和所述第二中间权重值中的一个第二中间权重值进行相加而获得的权重值用作所述各个候选实体网页的权重值。

8.根据权利要求1所述的方法，其中，所述根据所述第二实体的名称检索与所述第二实体的名称相关的多个候选实体网页包括：

对所述第二实体的名称与网页中的锚文本进行匹配检索，以获取与所述第二实体的名称相关的所述多个候选实体网页。

9.根据权利要求4所述的方法，其中，

在构建所述正向拓扑关系图的过程中，去掉指向所述第一实体网页的节点链接，并在所述第一汇聚节点上增加指向所述第一汇聚节点的回边。

10.根据权利要求6所述的方法，其中，

在构建所述正向拓扑关系图的过程中，去掉指向所述第一实体网页的节点链接，在所述第一汇聚节点上增加指向所述第一汇聚节点的回边；

在构建所述反向拓扑关系图的过程中，去掉指向所述候选实体网页的节点链接，在所述第二汇聚节点上增加指向所述第二汇聚节点的回边。

11.一种用于获取网页链接的装置，包括：

候选实体网页获取模块，其被配置为根据第二实体的名称检索与所述第二实体的名称相关的多个候选实体网页；

拓扑关系图构建模块，其被配置为部分地通过从抓取到的多个中间实体网页抓取一个或多个新的中间实体网页或所述多个候选实体网页来构建第一实体网页与所述多个候选实体网页之间的拓扑关系图，其中，将所述抓取到的多个中间实体网页用作第一中间节点，并且将所述候选实体网页中的一个候选实体网页用作第一汇聚节点，并且其中，基于所述第一实体网页和第一汇聚节点之间的路径抓取所述一个或多个新的中间实体网页；

出度确定模块，其被配置为确定所述第一实体网页与所述多个候选实体网页中的各个候选实体网页之间的所述拓扑关系图中节点的出度，其中，所述出度包括从所述第一实体网页通向各个候选实体网页的各条边的比例值；

权重值计算模块，其被配置为根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系，计算所述候选实体网页的权重值，其中，所述权重值表示直接通向各个候选实体网页的所述出度之和；以及

排名模块，其被配置为根据所述候选实体网页的权重值进行排名，并且根据所进行的排名的排名结果确定所述第二实体的名称对应的网页链接。

12.根据权利要求11所述的装置，其中，所述拓扑关系图包括正向拓扑关系图，并且所述正向拓扑关系图包括所述第一实体网页、第一中间节点以及所述第一汇聚节点，

13.根据权利要求12所述的装置，其中，根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系计算所述候选实体网页的权重值包括：

14.根据权利要求12所述的装置，其中，所述拓扑关系图还包括多个反向拓扑关系图，并且所述反向拓扑关系图包括所述候选实体网页、第二中间节点以及第二汇聚节点，

15.根据权利要求14所述的装置，其中，根据所述拓扑关系图中所述候选实体网页与所述第一实体网页之间的路径关系计算所述候选实体网页的权重值包括：

16.根据权利要求11所述的装置，其中，所述根据所述第二实体的名称检索与所述第二实体的名称相关的多个候选实体网页包括：

17.一种电子设备，包括：

处理单元；以及

存储器，其耦合至所述处理单元并且包含存储于其上的指令，所述指令由所述处理单元执行以执行根据权利要求1-10中的任一项所述的方法。

18.至少一种具有指令的机器可读介质，所述指令在被至少一个处理器执行时，使所述至少一个处理器执行根据权利要求1-10中的任一项所述的方法。