(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211232039.7 (22)申请日 2022.10.10 (71)申请人 国网江苏省电力有限公司南 通供电 分公司 地址 226000 江苏省南 通市青年中路52号 (72)发明人 姜鑫东　张燕　季晨宇　王晨璐　 毛艳芳　吕晓祥　陈晔　马俊明　 李苗苗　葛振宇　 (74)专利代理 机构 南通市永通专利事务所(普 通合伙) 3210 0 专利代理师 葛雷 (51)Int.Cl. H04L 67/51(2022.01) G06F 16/22(2019.01) G06F 16/2455(2019.01)G06F 16/2458(2019.01) (54)发明名称 一种基于频繁子图挖掘的网络系统关联服 务发现方法 (57)摘要 本发明公开了一种基于频繁子图挖掘的网 络系统关联服务发现方法， 使用Coco哈希和最小 堆这两种数据结构来统计网络流数据中各个节 点的访问信息， 并使用相应的图序列生成算法来 对各类数据进行处理生成频繁子图挖掘所需的 图序列数据。 在处理完所有网络流数据后， 运行 网络系统服务发现算法快速地挖掘出相关的网 络系统服务。 最终使用网络系统关联服务发现算 法来挖掘出已统计的IP访问数据中的一些相互 关联的数据， 筛选出之间存在一定关系的IP地址 组成的频繁项集， 然后进一步处理准确统计出网 络系统关联服务。 本发明将统计后的网络数据流 信息转化为图序列数据集而后采用频繁子图挖 掘相关技术， 挖掘出网络系统中的关联服务相关 信息。 权利要求书2页 说明书8页 附图1页 CN 115473933 A 2022.12.13 CN 115473933 A 1.一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特征在于， 该方法包括以 下步骤： （1） 为每个IP地址设置一个全局Coco  Sketch， 简称为Sketch， 在接收到网络流数据后， 解析得到源IP地址、 目的IP地址等信息， 将这些信息更新到每 个IP对应的全局Sketc h中； （2） 访问统计后的Sketch信息文件， 按照一定的时间间隔提取源IP、 源端口、 目的IP、 目 的端口生成 图序列所需要的信息， 并整合所有提取后的信息， 生成包含访问被访问等关系 的图序列数据集并通过 K‑means聚类方法， 将图序列数据集进行进一 步划分； （3） 对给定的图集G， 称图集G的只含有一条边的频繁子图为单边频繁子图； 对图集G的 所有单边频繁子图按出现的频度升序排列， 得到单边频繁子图的集合E={e1， e2，… ,en},我 们称对应边ei的修正后的图的生成树为对应该单边频繁子图的单边频繁子图树； 根据前述 所得的包含网络访问相关信息的图序列数据集， 对图集中的图进行深度优先遍历， 生成 图 的单边频繁子图的所有单边频繁子图树， 并且以一棵树为基树把该图的其它单边频繁子图 树都重叠到该树上； （4） 生成最初基树的图的边的五元素并以边在存储结构中的顺序作为边的唯一标识符 保存到设定的存储结构映射边集中； 然后将图序列数据分别与映射树进行重叠操作， 通过 映射树中边上记录的对应映射边集中边的编号， 把重叠成功的边在映射边集中作标记， 重 叠不成功的边添加到映射 边集中并作标记； （5） 在每一个单边频繁子图对应的映射边集按边频率降序排列， 统计大于最小支持度 的每个支持度数对应的所有的边并统计边节点出现次数等相关信息， 进而统计得到网络系 统相关服 务信息并根据相关频率降序存 入文件； （6） 读取上一步所得数据文件并设置最小支 持度计数MIN_COUNT； 对文件内容进行扫描 找到频繁项集M； 并将M中各项按支持度递减排序， 同时对原数据文件进行二次扫描生成相 关树， 并通过相关约束组合得到具体的频繁项集； （7） 对图集中各个子图进行计算筛选， 获得相应的候选子图， 而后对候选子图以及上一 步所得的频繁项集进行比对， 进一 步筛选， 完成网络系统关联服 务发现。 2.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 步骤 （1） 中为了统计相关网络数据流信息， 构造不同的CocoSketch， 分别记录每个 源IP发起访问总数， 每个目的IP接受访问总数， 每个目的IP端口接收访问总数， 主机 之间访 问总数。 3.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 在步骤 （2） 中对统计后的Sketch信息文件进 行进一步提取 统计相关信息， 并利用这 些信息生 成图序列， 并进一步采用K ‑means聚类方法， 对 所生成的图序列数据集进行聚类划 分。 4.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 对图序列数据集中的图进行深度优先遍历， 得到图的所有 单边频繁子图树， 同时以 一棵树为基树把该图的其它单边频繁 子图树重 叠到基树上。 5.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 生成最初基树的图中边的五元素并以边在 存储结构中的顺序作为边的唯一标识符 保存到设定的存 储结构映射 边集中。权　利　要　求　书 1/2 页 2 CN 115473933 A 26.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 在步骤 （6） 中， 对文件内容进行二次扫描， 生 成相关树， 包括根节点、 项 前缀子树、 顶 头表， 其中项 前缀子树中每个节 点包4个域:项 所对应的序号、 节 点计数值、 指向父节点或最 左子女节点的指针、 指向同名节点链中下一个节点或者右兄弟节点的指针， 而后倒序遍历 项头表， 判断是否与被约束子树端点相同且端点的支持度技术≥MIN_COUNT， 满足条件， 则 通过组合方式得到新的频繁项集， 反 之， 通过递归挖掘被约束子树获得新的频繁项集。 7.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 将图集中的各个子图的的邻接矩阵按照正规化算法进行正规化并转换成正准形， 求出所对应的编 码， 并按编 码值从小到大升序排列各图； 按编 码大小的升序序列将 每个k阶 邻接矩阵分别与后面的矩阵结合； 每两个k阶的邻接矩阵， 判断其二者的编码， 若其编码的 前k‑2项相同， 说明两矩阵包含同一个k ‑1阶子矩阵， 可以生 成候选k+1阶子图， 若不相等， 则 放弃结合， 继续判断其后面的矩 阵； 对k‑l阶子图集进行剪枝， 计算针1阶候选子图的支持 度， 并根据最小支持度进 行判断生成k +l阶频繁图； 重复以上步骤直到不再产生新的候选子 图为止。 8.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法， 其特 征在于， 通过比对候选子图每个节点与网络系统服务记录以及比对候选子图各边关系与新 频繁项集， 实现网络系统关联服 务发现。权　利　要　求　书 2/2 页 3 CN 115473933 A 3