(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211130659.X (22)申请日 2022.09.16 (71)申请人 北京百度网讯科技有限公司 地址 100085 北京市海淀区上地十街10号 百度大厦2层 (72)发明人 彭涵宇　范成林　孙明明　 (74)专利代理 机构 北京市汉坤律师事务所 11602 专利代理师 姜浩然　吴丽丽 (51)Int.Cl. G06F 16/901(2019.01) G06F 16/23(2019.01) (54)发明名称 图数据的处 理方法、 装置、 设备和介质 (57)摘要 本公开提供了一种图数据的处理方法、 装 置、 设备和介质， 涉及大数据技术领域， 具体涉及 大规模图数据处理技术。 该方法包括： 迭代地对 包括多个节 点的网络图执行以下操作， 直至执行 操作后的网络图满足第一预设条件： 针对网络图 中的每一个节 点， 基于该节点在网络图中的度数 确定该节点的移 除损失值， 其中， 该节点在网络 图中的度数指示该节点在网络图中的邻居节点 的数量； 基于网络图中的每一个节 点的移除损失 值， 在网络图中确定多个待移除节 点并确定多个 待移除节点的移 除顺序； 以及基于移 除顺序， 接 连将多个待移除节点逐一 从网络图中移除， 以获 取网络图的多个子图并更新网络图； 以及在网络 图的所有所获取的子图中确定满足第二预设条 件的子图。 权利要求书3页 说明书13页 附图3页 CN 115455244 A 2022.12.09 CN 115455244 A 1.一种图数据的处 理方法， 包括： 迭代地对包括多个节点的网络图执行以下操作， 直至执行所述操作后的网络图满足第 一预设条件： 针对所述网络图中的每一个节点， 基于该节点在所述网络图中的度数确定该节点的移 除损失值， 其中， 该节点在所述网络图中的度数指示该节点在所述网络图中的邻居节点的 数量； 基于所述网络图中的每一个节点的移除损失值， 在所述网络图中确定多个待移除节点 并确定所述多个待移除节点的移除顺序； 以及 基于所述移除顺序， 接连将所述多个待移除节点逐一从所述网络 图中移除， 以获取所 述网络图的多个子图并更新所述网络图， 其中， 更新后的网络图不包括所述多个待移除节 点； 以及 在所述网络图的所有所获取的子图中确定满足第二预设条件的子图。 2.根据权利要求1所述的方法， 其中， 所述多个待移除节点包括所述网络图中移除损失 值最小的预设比例的节点。 3.根据权利要求2所述的方法， 其中， 所述预设比例为1/2。 4.根据权利要求1所述的方法， 其中， 所述多个待移除节点的移除顺序 是基于所述多个 待移除节点各自的移除损失值按照从小到大的排序结果而确定的。 5.根据权利要求1所述的方法， 其中， 所述第 二预设条件指示对应的密度函数最大的子 图。 6.根据权利要求5所述的方法， 其中， 子图的密度函数是基于该子图中的每一个节点在 该子图中的度数的p次幂和该子图所包括的节点的数量确定的， p为 不等于0的预设参数。 7.根据权利要求6所述的方法， 其中， 所述移除损失值是基于对应的节点在所述网络图 中的度数的p次幂、 该节点在所述网络图中的每一个邻居节 点在所述网络图中的度数的p次 幂、 以及该节点在所述网络图中的每一个邻居节 点在所述网络图中的度数减1的p次幂而确 定的。 8.根据权利要求1所述的方法， 其中， 所述第 一预设条件指示所述网络图中的节点数量 不多于预设值。 9.根据权利要求1所述的方法， 其中， 所述网络图包括以下任意 一项： 生物信息图， 所述生物信息图中的节点表征生物信息结构单元， 包括原子、 原子团、 官 能团、 碱基对或碱基对片段、 氨基酸或氨基酸序列中的至少一个， 邻居节点表征与对应的生 物信息结构单 元具有关联的其 他生物信息结构单 元； 网络拓扑图， 所述网络拓扑图中的节点表征网络设备， 邻居节点表征与对应的网络设 备间存在通信链路的其 他网络设备； 或 社交关系图， 所述社交关系图中的节点表征用户， 邻居节点表征与对应的用户相关的 其他用户。 10.一种图数据的处 理装置， 包括： 第一处理单元， 被配置为迭代地对包括多个节点的网络 图进行处理， 直至处理后的网 络图满足第一预设条件， 所述处 理单元包括： 第一确定子单元， 被配置为针对所述网络 图中的每一个节点， 基于该节点在所述网络权　利　要　求　书 1/3 页 2 CN 115455244 A 2图中的度数确定该节点的移除损失值， 其中， 该节点在所述网络图中的度数指示该节点在 所述网络图中的邻居节点的数量； 第二确定子单元， 被配置为基于所述网络 图中的每一个节点的移除损 失值， 在所述网 络图中确定多个待移除节点并确定所述多个待移除节点的移除顺序； 以及 第一节点移除子单元， 被配置为基于所述移除顺序， 接连将所述多个待移除节点逐一 从所述网络图中移除， 以获取所述网络图的多个子图并更新所述网络图， 其中， 更新后的网 络图不包括所述多个待移除节点； 以及 第一确定单元， 被配置为在所述网络图的所有所获取的子图中确定满足第 二预设条件 的子图。 11.根据权利要求10所述的装置， 其中， 所述多个待移除节点包括所述网络图中移除损 失值最小的预设比例的节点。 12.根据权利要求1 1所述的装置， 其中， 所述预设比例为1/2。 13.根据权利要求10所述的装置， 其中， 所述多个待移除节点的移除顺序 是基于所述多 个待移除节点各自的移除损失值按照从小到大的排序结果而确定的。 14.根据权利要求10所述的装置， 其中， 所述第 二预设条件指示对应的密度函数最大的 子图。 15.根据权利要求14所述的装置， 其中， 子图的密度函数是基于该子图中的每一个节点 在该子图中的度数的p次幂和该子图所包括的节点的数量确定的， p为 不等于0的预设参数。 16.根据权利要求15所述的装置， 其中， 所述移除损失值是基于对应的节点在所述网络 图中的度数的p次幂、 该节点在所述网络图中的每一个邻居节点在所述网络图中的度数的p 次幂、 以及该节点在所述网络图中的每一个邻居节点在所述网络图中的度数减1的p次幂而 确定的。 17.根据权利要求10所述的装置， 其中， 所述第 一预设条件指示所述网络图中的节点数 量不多于预设值。 18.根据权利要求10所述的装置， 其中， 所述网络图包括以下任意 一项： 生物信息图， 所述生物信息图中的节点表征生物信息结构单元， 包括原子、 原子团、 官 能团、 碱基对或碱基对片段、 氨基酸或氨基酸序列中的至少一个， 邻居节点表征与对应的生 物信息结构单 元具有关联的其 他生物信息结构单 元； 网络拓扑图， 所述网络拓扑图中的节点表征网络设备， 邻居节点表征与对应的网络设 备间存在通信链路的其 他网络设备； 或 社交关系图， 所述社交关系图中的节点表征用户， 邻居节点表征与对应的用户相关的 其他用户。 19.一种电子设备， 包括： 至少一个处 理器； 以及 与所述至少一个处 理器通信连接的存 储器； 其中 所述存储器存储有可被所述至少一个处理器执行的指令， 所述指令被所述至少一个处 理器执行， 以使所述至少一个处 理器能够执 行权利要求1 ‑9中任一项所述的方法。 20.一种存储有计算机指令的非瞬时计算机可读存储介质， 其中， 所述计算机指令用于 使所述计算机执 行根据权利要求1 ‑9中任一项所述的方法。权　利　要　求　书 2/3 页 3 CN 115455244 A 3