(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210927391.6 (22)申请日 2022.08.03 (71)申请人 中国科学院信息 工程研究所 地址 100093 北京市海淀区闵庄路甲89号 (72)发明人 刘燕兵　夏辉　袁方方　张春燕　 曹聪　卢毓海　谭建龙　 (74)专利代理 机构 北京君尚知识产权代理有限 公司 11200 专利代理师 邱晓锋 (51)Int.Cl. G06V 10/40(2022.01) G06V 10/10(2022.01) G06V 10/26(2022.01) G06V 10/44(2022.01) (54)发明名称 一种稠密子图抽取方法和系统 (57)摘要 本发明涉及一种稠 密子图抽取方法和系统， 属于计算机软件技术领域。 该方法包括： 对原图 采用Mas策略进行子图分割， 得到节点序列L； 对 节点序列L进行合并检查， 无法通过合并检查的 结点重新回到原图做后续的分割； 对通过合并检 查的子图结点进行合并， 构成K边联通子图。 本发 明在图分解框架中使用了最大S ‑T流解决路径数 搜索问题， 对现有Mas策略的不足提出了改进方 法， 使得本方法在K ‑ECC抽取工作中提高了现有 工作的准确率。 权利要求书1页 说明书7页 附图2页 CN 115424025 A 2022.12.02 CN 115424025 A 1.一种稠密子图抽取 方法， 其特 征在于， 包括以下步骤： 对原图采用Mas策略进行子图分割， 得到节点序列L； 对节点序列L进行合并检查， 无法通过合并检查的结点重新回到原图做后续的分割； 对 通过合并检查的子图结点进行合并， 构成K边联通子图。 2.根据权利要求1所述的方法， 其特征在于， 所述对原图采用Mas策略进行子图分割， 得 到节点序列L， 包括： 首先从父图中随机选择一个结点加入L， 并维护一个L的邻居集合N(L)； 然后从N(L)中选取与L中结点的连接度最大的结点u加入L尾部， 获得u的邻居结点集N(u)， 并更新N(L)， 直到N(L)为空； s、 t是Mas策略生成 的L中的最后两个结点， 最后一个结点为t， 倒数第二个为s， 最后得到的节点序列L 为t之前所有顶点。 3.根据权利要求1所述的方法， 其特征在于， 以G作为输入的Mas策略的第一次运行返回 的最小s1‑t1割(S1,T1)有两种情况： s1和t1位于G的全局最小割的不同侧， 或者位于同一侧； 在前一种情况下(S1,T1)必须是G的全局最小割， 在后一种情况下s1和t1收缩为一个超顶点 而不影响G的全局最小割。 4.根据权利要求1所述的方法， 其特征在于， 当有多个同度结点接入L 时， 以其邻居加入 L的顺序进行排序。 5.根据权利要求1所述的方法， 其特征在于， 所述对节点序列L进行合并检查， 包括： 对L 进行最大s‑t流检测， 如果最大s ‑t流小于K， 则切分子图， 并不断重复这一过程， 同时使用路 径增广与路径交换避免边冲突。 6.根据权利要求5所述的方法， 其特征在于， 所述路径增广旨在找到所有可能的s ‑t路 径。 7.根据权利要求5所述的方法， 其特 征在于， 所述路径交换旨在解决现有路径冲突。 8.一种稠密子图抽取系统， 其特 征在于， 包括： 子图分割模块， 用于对原图采用Mas策略进行子图分割， 得到节点序列L； 合并检查模块， 用于对节点序列L进行合并检查， 无法通过合并检查的结点重新回到原 图做后续的分割， 对通过合并检查的子图结点进行合并， 构成K边联通子图。 9.一种电子装置， 其特征在于， 包括存储器和 处理器， 所述存储器存储计算机程序， 所 述计算机程序被配置为由所述处理器执行， 所述计算机程序包括用于执行权利要求 1～7中 任一项所述方法的指令 。 10.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质存储计算机程 序， 所述计算机程序被 计算机执 行时， 实现权利要求1～7中任一项所述的方法。权　利　要　求　书 1/1 页 2 CN 115424025 A 2一种稠密子 图抽取方 法和系统 技术领域 [0001]本发明属于计算机软件技 术领域， 具体涉及一种稠密子图抽取 方法和系统。 背景技术 [0002]对于K‑ECC(K‑Edge Connected  Component， K边联通子图)的抽取， 是一个多项式 时间问题， 多是从寻找原始图的min ‑cut来将min ‑cut<K的子图抽取出来， 进而将图分解为 多个子图， 由于花费了大量计算资源在不满足条件的子图上， 精确算法的性能非常慢。 随着 图规模的增大， 近似算法在速度上 的优越性就体现了出来， 但是近似算法的准确 率并不理 想。 下面将分别介绍精确算法和近似算法的相关工作。 [0003](一)精确算法 [0004]对于图G＝(V,E)， 如果图G不是K边联通的， 那么必须存在一个割集C， 使得|C|＜k， 删除割集C上的边将会使图分割为两个 不联通的子图G1与G2。 基于这样的分割思 想， Stoer等 提出了一种基于最小割的算法MinimumCut， 其思想是将一个非K边联通图切割 为两个不连 通子图， 直到所有剩余连通子图都是K ‑边连通或图中没有剩余边为止。 当K为3， 容易得到一 个最小割{ e4,7,e5.13}， 将图分割后， 剩余两个不联通子图G1与G2∪G3， 其中G1包含了顶点v1, v2,v3,v4,v5,接下来对G2∪G3进行第二次分割， 由于子图G2∪G3最小割为2， 去除割边以后， G1,G2都为3边联通， 迭代终止。 在使用min ‑cut的想法中， 设计 一个有效的算法来搜索最小割 是为核心关键问题。 [0005]Stoer等使用Mas策略来创建一组结点， 记录最后两个结点s和t之间的最小s ‑t割 并将s和t以及之前所有的结点合并为的序列L， 创建一个超级 结点并在合并图上重复Mas过 程， 直到所有结点都合并为一个。 这个 s‑t cut就是全局min ‑cut。 通过最小割将图不断划分 直到最小割划分的子图边联通度小于K， 停止 分割。 Aissi等在寻找全局最小割的工作中， 将 问题的复杂度降低到 了O(n2log3n)。 [0006]由于最小s ‑t cut等价于最大s ‑t流， 因此使用最大s ‑t流算法也是较为常见的。 Benczur等将问题转化为随机采样的方式， 采用最大流来解决该问题。 首先对图进行Mas计 算图中最大流， 然后找到全局最小割， 直到所有子图都是K ‑ECC,其复杂度 其 中l为迭代次数。 Wang等的方法， 通过构建辅助树来存储不同K值的K边联通子图， 将子图划 分转化为动态 规划的重叠子问题， 低K联通子图依赖于高K联通子图构建， 并且给定任意K值 都可以获得准确结果集。 但是该方案的缺点在于巨大 的计算量以及存储消 耗， 使得整个算 法速度非常慢。 [0007]精确算法都需要花费大量的计算时间获得准确结果， 无法在大规模图中使用。 [0008](二)近似算法 [0009]Raghavan等提出了线形算法MkECSs， 该算法首先将度小于K 的结点以及边删除得 到K‑core图， 然后在众多结点中随机合并两个相邻 结点为一个顶点， 结果被用作迭代执行 合并的输入， 直到图为空集。 为了提高时间效率， 随机选择顶点的方式将导致K边联通子图 的结果是不确定的。 假如选择相邻结点v11,v13进行合并， 那么这将包含在一个单一 的的3‑说　明　书 1/7 页 3 CN 115424025 A 3