(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211196442.9 (22)申请日 2022.09.29 (71)申请人 北京明略昭辉科技有限公司 地址 100082 北京市海淀区北三环西路25 号27号楼二层2020室 (72)发明人 刘海强　孟嘉　高阳　 (74)专利代理 机构 北京超成律师事务所 1 1646 专利代理师 朱品真 (51)Int.Cl. G06F 16/36(2019.01) G06F 16/33(2019.01) G06F 16/335(2019.01) (54)发明名称 一种获取最短连通路径的方法及装置 (57)摘要 本发明提供了一种获取最短连通路径的方 法及装置， 其中， 该获取最短连通路径的方法包 括： 在知识图谱中， 获取源节点的源节点元数据， 以及， 获取目标节点的目标节点元数据； 依据预 先存储的元数据类型与元数据关键词集的映射 关系， 获取所述源节点元数据映射的源元数据类 型以及所述目标节点元数据映射的目标元数据 类型； 构建所述源元数据类型与所述目标元数据 类型的连通关系； 以所述源节点为起始节点， 在 所述知识图谱中， 依据所述连通关系进行边扩 展， 获取包含所述目标节点的连通路径， 基于包 含所述目标节 点的连通路径， 获取所述源节点和 目标节点之间的最短连通路径。 可以提高获取最 短连通路径的效率。 权利要求书2页 说明书9页 附图2页 CN 115422375 A 2022.12.02 CN 115422375 A 1.一种获取最短连通路径的方法， 其特 征在于， 包括： 在知识图谱中， 获取源节点的源节点元 数据， 以及， 获取目标节点的目标节点元 数据； 依据预先存储的元数据类型与元数据关键词集的映射关系， 获取所述源节点元数据映 射的源元 数据类型以及所述目标节点元 数据映射的目标 元数据类型； 构建所述源元 数据类型与所述目标 元数据类型的连通关系； 以所述源节点为起始节点， 在所述知识图谱中， 依据所述连通关系 进行边扩展， 获取包 含所述目标节点的连通路径， 基于包含所述 目标节点的连通路径， 获取所述源节点和目标 节点之间的最短连通路径。 2.根据权利要求1所述的方法， 其特征在于， 所述依据所述连通关系进行边扩展， 获取 包含所述 目标节点的连通路径， 基于包含所述 目标节点的连通路径， 获取所述源节点和目 标节点之间的最短连通路径， 包括： 获取所述起始节点满足所述连通关系的第一知识图谱关系； 针对每一第一知识图谱关系， 确定与所述 起始节点相连通的下一节点； 判断下一节点是否为所述目标节点： 若是， 将包含所述目标节点的连通路径置于缓存中， 在遍历完所有第一知识图谱关系 后， 获取所述缓存中的连通路径， 得到所述源节点和目标节点之间的最短连通路径； 若否， 依据所述连通关系， 获取 所述下一节点满足所述连通关系的第二知识图谱关系； 针对每一第二知识图谱关系， 确定与所述下一节点相连通的下下节点， 依据与判断下 一节点是否为所述目标节点相同的流 程， 判断下 下节点是否为所述目标节点。 3.根据权利要求1所述的方法， 其特征在于， 所述依据所述连通关系进行边扩展， 获取 包含所述目标节点的连通路径， 包括： 获取所述起始节点满足所述连通关系的第一知识图谱关系； 针对每一第一知识图谱关系， 确定与所述 起始节点相连通的下一节点； 判断下一节点是否为所述目标节点， 若是， 获取包含所述目标节点的连通路径， 若否， 依据所述连通关系， 获取 所述下一节点满足所述连通关系的第二知识图谱关系； 针对每一第二知识图谱关系， 确定与所述下一节点相连通的下下节点， 直至确定的节 点中包括所述目标节点。 4.根据权利要求3所述的方法， 其特征在于， 所述获取所述起始节点满足所述连通关系 的第一知识图谱关系， 包括： 获取与所述起始节点相邻的相邻节点， 统计所述起始节点与相邻节点的知识图谱关 系； 依据预先设置的连通关系与知识图谱关系的映射关系， 从获取的知识图谱关系中， 提 取所述连通关系映射的知识图谱关系， 得到第一知识图谱关系。 5.根据权利要求1至4任一项所述的方法， 其特征在于， 所述连通关系包括： 人 ‑人， 满足 该连通关系的第一知识 图谱关系包括： 父子关系、 配偶关系、 同学关系、 朋友关系、 同事关 系、 亲戚关系。 6.根据权利要求1至4任一项所述的方法， 其特征在于， 获取所述源节点元数据映射的 源元数据类型， 包括： 针对每一元数据类型映射的元数据关键词集， 计算所述源节点元数据与该元数据关键权　利　要　求　书 1/2 页 2 CN 115422375 A 2词集的相似度， 获取相似度最高的元数据关键词集映射的元数据类型， 得到所述源元数据 类型。 7.一种获取最短连通路径的装置， 其特 征在于， 包括： 元数据获取模块， 用于在知识图谱中， 获取源节点的源节点元数据， 以及， 获取目标节 点的目标节点元 数据； 元数据类型查询模块， 用于依据预先存储的元数据类型与元数据关键词集的映射关 系， 获取所述源节点元数据映射的源元数据类型以及所述目标节点元数据映射的目标元数 据类型； 连通关系构建模块， 用于构建所述源元 数据类型与所述目标 元数据类型的连通关系； 最短连通路径获取模块， 用于以所述源节点为起始节点， 在所述知识图谱中， 依据 所述 连通关系进行边扩展， 获取包含所述 目标节点的连通路径， 基于包含所述 目标节点的连通 路径， 获取 所述源节点和目标节点之间的最短连通路径。 8.根据权利要求7 所述的装置， 其特 征在于， 所述 最短连通路径获取模块具体用于： 获取所述起始节点满足所述连通关系的第一知识图谱关系； 针对每一第一知识图谱关系， 确定与所述 起始节点相连通的下一节点； 判断下一节点是否为所述目标节点： 若是， 将包含所述目标节点的连通路径置于缓存中， 在遍历完所有第一知识图谱关系 后， 获取所述缓存中的连通路径， 得到所述源节点和目标节点之间的最短连通路径； 若否， 依据所述连通关系， 获取 所述下一节点满足所述连通关系的第二知识图谱关系； 针对每一第二知识图谱关系， 确定与所述下一节点相连通的下下节点， 依据与判断下 一节点是否为所述目标节点相同的流 程， 判断下 下节点是否为所述目标节点。 9.一种计算机设备， 其特征在于， 包括： 处理器、 存储器和总线， 所述存储器存储有所述 处理器可执行 的机器可读指令， 当计算机设备运行时， 所述处理器与所述存储器之间通过 总线通信， 所述机器可读指 令被所述处理器执行时执行如权利要求 1至7任一所述的获取最 短连通路径的方法的步骤。 10.一种计算机可读存储介质， 其特征在于， 该计算机可读存储介质上存储有计算机程 序， 该计算机程序被处理器运行时执行如权利要求1至7任一所述的获取最短连通路径的方 法的步骤。权　利　要　求　书 2/2 页 3 CN 115422375 A 3