(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210357034.0 (22)申请日 2022.03.31 (71)申请人 中国电子科技 集团公司第十五研究 所 地址 100083 北京市海淀区北四环中路21 1 号 (72)发明人 李常宝　高泽　李云鹏　潘爽　 袁媛　刘忠麟　赵静　 (74)专利代理 机构 北京理工大 学专利中心 11120 专利代理师 代丽 (51)Int.Cl. H04L 43/0811(2022.01) G06F 16/215(2019.01) G06F 16/22(2019.01)G06F 16/23(2019.01) (54)发明名称 一种基于多图的连通分量增量计算方法 (57)摘要 本发明公开了一种基于多图的连通分量增 量计算方法， 通过对连通分量进行重新编号， 连 接形成一张图， 再进行计算得到新的连通分量， 实现合并含有相同点的不同图后再进行连通分 量的计算， 解决了在合并图时， 需要重新计算连 通分量， 导 致计算时间长、 效率低的问题。 权利要求书1页 说明书4页 CN 115051936 A 2022.09.13 CN 115051936 A 1.一种基于多图的连通分量增量计算方法， 其特 征在于， 包括以下步骤： 收集现有的连通分量ID形成连通分量集合， 且不同图ID所包含的连通分量的ID均 不相 同； 对所述连通分量集合进行聚合操作， 将所有连通分量ID对应的图ID收集起来， 形成 (compontID,Set(图ID))； 令Set(图ID)中只有一条数据的节点与自身连接形成自连接的 边， 令Set(图ID)中具有多条数据的节点彼此互联形成互联的边， 由此形成新图； 对所述新 图进行连通分量计算得到Ip与新连通分量 ID的数据对。 2.根据权利要求1所述的连通分量增量计算方法， 其特征在于， 所述对所述连通分量集 合进行聚合操作的方式为采用大 数据处理框架Spark的reduceByK ey方法实现。 3.根据权利要求1所述的连通分量增量计算方法， 其特征在于， 在所述对所述新图进行 连通分量计算得到Ip与新连通分量ID的数据对后， 将Ip与新连通分量ID的数据对存储为 (IP,新连通分量 ID， 新图ID)。 4.根据权利要求3所述的连通分量增量计算方法， 其特征在于， 所述将Ip与新连通分量 ID的数据对存储为(IP,新连通分量ID， 新图ID)的过程为分成时间阶段进行存储， 即先计算 所述时间阶段内的连通分量， 再对连通分量进行合并后计算全部数据的连通分量。 5.根据权利要求 4所述的连通分量增量计算方法， 其特 征在于， 所述时间阶段为 一周。权　利　要　求　书 1/1 页 2 CN 115051936 A 2一种基于多图的连通分量增量计算方 法 技术领域 [0001]本发明属于计算机网络流量分析技术领域， 具体涉及一种基于多图的连通分量增 量计算方法。 背景技术 [0002]在网络流量分析过程中， 依据大规模流量数据分析网络数据时， 在解决不同来源 的网络数据的网络归属判断问题以及由网络实效性带来的节点变化问题时， 往往需要重新 计算连通分量。 [0003]在分析网络数据时， 对于不同渠道、 不同设备获取的网络数据， 在需要判断其是否 属于同一网络时间时需要 经过详细的数据分析， 计算连通性时往往无法获得完备的网络归 属， 所以当判断两组网络数据属于同一物理网络时， 需要重新计算连通分量。 此时， 通常采 用的方法是获取所有符合条件的协 议数据重新进 行计算， 然而重新计算会极大地耗费空间 和时间资源。 [0004]此外， 由于网络连通性具有时效性， 当原网络数据中的某些节点发生改变时， 连通 性往往会随之改变， 尤其是发生了网络地址重新分配时连通性也会改变。 此时， 如果需要获 取新的连通数据， 往往需要去除掉网络状况更改之前的数据， 对于这种情况， 通常采用的方 法是获取所有符合条件的协议数据重新进行计算， 同样会耗费大量的时间， 造成了资源的 浪费。 [0005]综上所述， 针对上述两种场景， 现有技术均是通过获取所有符合条件的协议数据 再重新进行计算的方式得到连通性， 且此类计算都属于全量计算， 这会极大 的耗费空间和 时间资源。 发明内容 [0006]有鉴于此， 本发明提供了一种基于多图的连通分量增量计算方法， 实现了将现有 的连通分量数据进行合并得到新图后再计算得到新的连通分量。 [0007]本发明提供的一种基于多图的连通分量增量计算方法， 包括以下步骤： [0008]收集现有的连通分量ID形成连通分量集合， 且不同图ID所包含的连通分量的ID均 不相同； 对 所述连通分量集合进 行聚合操作， 将所有 连通分量ID对应的图ID收集起来， 形成 (compontID,Set(图ID))； 令Set(图ID)中只有一条数据的节点与自身连接形成自连接的 边， 令Set(图ID)中具有多条数据的节点彼此互联形成互联的边， 由此形成新图； 对所述新 图进行连通分量计算得到Ip与新连通分量 ID的数据对。 [0009]进一步地， 所述对所述连通分量集合进行聚合操作的方式为采用大数据处理框架 Spark的reduceByK ey方法实现。 [0010]进一步地， 在所述对所述新图进行连通分量计算得到Ip与新连通分量ID的数据对 后， 将Ip与新连通分量 ID的数据对 存储为(IP,新连通分量 ID， 新图ID)。 [0011]进一步地， 所述将 Ip与新连通分量ID的数据对存储为(IP,新连通分量ID， 新图ID)说　明　书 1/4 页 3 CN 115051936 A 3