(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211407710.7 (22)申请日 2022.11.10 (71)申请人 哈尔滨工业大 学 （深圳） （哈尔滨工 业大学深圳科技创新研究院） 地址 518055 广东省深圳市南 山区桃源街 道深圳大 学城哈尔滨工业大 学校区 (72)发明人 刘圣鑫　邱泽龙　 (74)专利代理 机构 深圳市君胜知识产权代理事 务所(普通 合伙) 44268 专利代理师 王永文 (51)Int.Cl. G06F 16/2455(2019.01) G06F 16/901(2019.01) (54)发明名称 一种有向图中目标子图查找方法及相关设 备 (57)摘要 本发明公开了一种有向图中目标子图查找 方法及相关设备。 方法包括： 根据原始有向图中 所有顶点的出度和入度获取初始顶 点集合， 初始 顶点集合中的每个顶点的出度都不小于原始有 向图对应的出度目标差值， 初始顶 点集合中的每 个顶点的入度都不小于原始有向图对应的入度 目标差值； 根据初始顶点集合中的顶 点个数在原 始有向图中删除至少一个顶点 或有向边， 得到处 理有向图； 在处理有向图中获取目标子图， 目标 子图为原始有向图中满足目标条件的子图中包 含的顶点数量最大的子图。 本发 明可以实现高效 地从稀疏数据中查找尽可能多的相互关联性强 的部分数据。 权利要求书3页 说明书12页 附图4页 CN 115438088 A 2022.12.06 CN 115438088 A 1.一种有向图中目标子图查找方法， 其特 征在于， 所述方法包括： 获取原始有向图， 获取所述原始有向图中的所有顶点的出度和入度， 根据所有顶点的 出度和入度获取初始顶点集合， 其中， 所述初始顶点集合中的每个顶点的出度都不小于所 述原始有向图对应的出度目标差值， 所述初始顶 点集合中的每个顶点的入度都不小于所述 原始有向图对应的入度目标差值； 根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向 边， 得到处 理有向图； 在所述处理有向图中获取目标子图， 所述目标子图为所述原始有向图中满足 目标条件 的子图中包含的顶点数量最大的子图， 所述目标条件为子图中的每个顶点的出度都不小于 该子图对应的出度目标差值且每 个顶点的入度都不小于该子图对应的入度目标差值； 其中， 图对应的出度目标差值为该图的顶点数量与预设出度阈值的差值， 图对应的入 度目标差值 为该图的顶点数量与预设入度阈值的差值。 2.根据权利要求1所述的有向图中目标子图查找方法， 其特征在于， 所述根据 所述初始 顶点集合中的顶点个数在所述原 始有向图中删除至少一个顶点或有向边， 包括： 获取目标值， 所述目标值为第一值与所述初始顶点集合中的顶点个数值中的最大值， 其中， 所述第一 值为所述预设出度阈值和所述预设入度阈值中的最小值； 基于所述目标值， 采用第一方式在所述原 始有向图中删除至少一个顶点； 和/或 采用第二方式在所述原 始有向图中删除至少一个有向边。 3.根据权利要求2所述的有向图中目标子图查找方法， 其特征在于， 所述采用第 一方式 在所述原 始有向图中删除至少一个顶点， 包括： 对于所述原始有向图中的一个目标顶点， 若所述目标顶点的出度小于所述目标值和所 述预设出度阈值之间的差值， 或者， 所述 目标顶点的入度小于所述 目标值和所述预设入度 阈值之间的差值， 则在所述原 始有向图中删除所述目标顶点。 4.根据权利要求2所述的有向图中目标子图查找方法， 其特征在于， 所述采用第 二方式 在所述原 始有向图中删除至少一个有向边， 包括： 对于所述原始有向图中的每个顶点， 分别获取对应的目标出度集合和目标入度集合， 其中， 在所述原始有向图中存在目标顶点到所述目标顶点对应的所述目标出度集合中的每 个顶点的有向边， 在所述原始有向图中存在所述目标顶点对应的所述目标入度集合中的每 个顶点到所述目标顶点的有向边； 获取所述原始有向图中的第 一目标顶点和第 二目标顶点之间的出度交集和入度交集， 其中， 所述出度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标出度集 合的交集， 所述入度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标入 度集合的交集； 根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少一个 有向边。 5.根据权利要求4所述的有向图中目标子图查找方法， 其特征在于， 所述根据 所述出度 交集和所述入度交集中顶点的数量在所述原 始有向图中删除至少一个有向边， 包括： 若所述原始有向图中存在所述第一目标顶点到所述第二目标顶点的有向边和所述第 二目标顶点到所述第一 目标顶点的有向边， 并且， 所述出度 交集中顶点的数量不大于第一权　利　要　求　书 1/3 页 2 CN 115438088 A 2差值或所述入度交集中顶点的数量不大于第二差值， 则在所述原始有向图中删除所述第一 目标顶点和所述第二目标顶点之间的连接边； 其中， 所述第一差值为所述目标值与所述预设出度阈值的两倍的差值， 所述第二差值 为所述目标值与所述预设入度阈值的两倍的差值； 若所述原始有向图的所述第一目标顶点和所述第二目标顶点之间的连接边为单向连 接边， 并且， 所述出度 交集中顶点的数量不大于第三差值或所述入度 交集中顶点的数量不 大于第四差值， 则 在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之 间的 连接边； 其中， 所述第三差值 为所述第一差值加1， 所述第四差值 为所述第二差值加1。 6.根据权利要求1所述的有向图中目标子图查找方法， 其特征在于， 所述在所述处理有 向图中获取目标子图， 包括： 将所述处 理有向图中所有的顶点加入至候选集中， 并设置扩张解 集为空集； 在每个分支图中选取一个顶点作为根节点， 根据 所述根节点所在的集合生成至少一个 分支并更新所述扩张解 集， 每个分支中包括 一个分支图； 当目标分支图中的所有节点的出度都不小于所述目标分支图对应的出度目标差值且 所有节点的入度都不小于所述目标分支图对应的入度目标差值时， 不再在所述目标分支图 中选取顶点作为 根节点； 在所有的所述目标分支图中选取顶点个数最大的图作为所述目标子图； 其中， 初始分支图为所述处 理有向图。 7.根据权利要求6所述的有向图中目标子图查找方法， 其特征在于， 所述根据 所述根节 点所在的集 合生成至少一个分支并更新所述扩张解 集， 包括： 当所述根节点在所述扩张解集时， 获取所述根节点对应的第一出度集合、 第二出度集 合和第一入度集合、 第二入度集合， 其中， 所述第一出度集合中的顶点都属于所述扩张解 集， 且所述扩张解集对应的子图中不存在所述根节点到所述根节点对应的所述第一出度集 合中每个顶点的有向边， 所述第二出度集合中的顶点 都属于所述候选集且 所述候选集对应 的子图中不存在所述根节点到所述根节点对应的所述第二出度集合中的每个顶点的有向 边， 所述第一入度集合中的顶点都属于所述扩张解集， 且所述扩张解集对应的子图中不存 在所述根节点对应的所述第一入度集合中每个顶 点到所述根节点的有向边， 所述第二入度 集合中的顶点都属于所述候选集， 且所述候选集对应的子图中不存在所述根节点对应的所 述第二入度集 合中的每 个顶点到所述 根节点的有向边； 若所述根节点的出度小于所述根节点所在的分支图对应的出度目标差值， 则获取所述 根节点对应的第一参数， 所述第一参数为预设出度阈值与所述第一出度集合中顶点的个数 的差值； 根据所述第一参数和所述第二出度集合生成 个出度分支并将所述第二出 度集合中的前 个顶点加入至所述扩张解集中， 其中， 为所述第一参数， 前 个所述出度分支的分支图由从所述根节点所在的分支图中分别删除所述第二出度集合中 的前 个顶点而产生， 第 个所述出度分支的分支图由从所述根节点所在的 分支图中删除所述第二出度集 合中前 个顶点之外的顶点而产生；权　利　要　求　书 2/3 页 3 CN 115438088 A 3