(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210241096.5 (22)申请日 2022.03.11 (71)申请人 山东大学 地址 250013 山东省青岛市 即墨区滨 海路 72号 (72)发明人 于东晓　刘余　罗琦　成秀珍　 (74)专利代理 机构 青岛华慧泽专利代理事务所 (普通合伙) 37247 专利代理师 付秀颖 (51)Int.Cl. G06F 16/26(2019.01) G06F 16/2458(2019.01) G06F 16/23(2019.01) (54)发明名称 一种超图并行多边图核维护方法 (57)摘要 本发明公开了一种超图并行多边图核维护 方法， 包括以下步骤， S1.计算超图中所有节点的 核值core， 一个超边中， 核值最小节点的核值作 为该超边 的核值； S2.计算节点u的NI(u)， NI(u) 为节点u所在超边中的超边核值大于等于节点u 的核值的超边集合； S3.计算超边e的EI(e)， EI (e)为超边中节点核值等于 该超边核值的节点的 |NI|的最小值； S4.进行图核维护增量或图核维 护减量的并行处理。 其优点在于， 当图中存在边 的插入、 删除时， 保证图核的正确的更新。 权利要求书2页 说明书4页 附图2页 CN 114780628 A 2022.07.22 CN 114780628 A 1.一种超图并行多边图核维护方法， 其特 征在于， 包括以下步骤， S1.计算超图中所有节点的核值core， 一个超边中， 核值最小节点的核值作为该超边的 核值； S2.计算节点u的NI(u)， NI(u)为节点u所在超边 中的超边核值大于等于节点u的核值的 超边集合； S3.计算超边e的EI(e)， EI(e)为超边中节点核值等于该超边核值的节点的|NI|的最小 值； S4.进行图核维护增量或图核维护减量的并行处 理。 2.根据权利要求1所述的一种 超图并行多边图核维护方法， 其特征在于， 图核维护增量 步骤如下： 步骤一、 当一批超边集合E需要插入到超图G中， 如果E为空， 则结束算法运行， 否则从集 合E中， 筛选出满足如下条件的超边SPS， 该超边集合中任意两条超边的核值最小的节点集 合互不相同， 并将S PS内的超边按照边的核值分类； 步骤二、 选取SPS内核值为k的所有超边， 按照根据现有的节点核值， 更新对应的NI和 EI； 步骤三、 将S PS内核值为k的超边中核值 最小的节点存 入队列Q中； 步骤四、 从队列 Q中取出一个节点u， 若队列 Q为空， 则跳转到步骤七； 若队列 Q不为空， 对 于节点u的所有邻边e， 计算符合此 条件EI(e)>k的边的数目作为deg(u)； 步骤五、 如果deg(u)>k,则继续 算法， 否则跳转 步骤四； 步骤六、 对于节点u满足此条件的EI(e)>k的边e， 将边e中核值等于k的节点存入队列Q 中， 跳转步骤四； 步骤七、 选择deg中值最小的节点u， 若deg(u)<＝k,则从deg中删除节点u并继续算法， 否则跳转到步骤九； 步骤八、 如果deg 中存在点v在N I(u)的超边中， 则deg(v)＝deg(v) ‑1， 跳转到步骤 七； 步骤九、 将deg中所有的节点， 核值均增加1， 根据现有的节点核值， 更新对应的NI和EI， 跳转到步骤一。 3.根据权利要求1所述的一种 超图并行多边图核维护方法， 其特征在于， 图核维护减量 步骤如下： 步骤一、 当一批超边集合E需要超图G中删除， 如果E为空， 则结束算法运行， 否则从集合 E中， 筛选出满足如下条件的超边SPS， 该超边集合中任意两条超边的核值最小的节点集合 互不相同， 并将S PS内的超边按照边的核值分类； 步骤二、 选取SPS内核值为k的所有超边， 按照根据现有的节点核值， 更新对应的NI和 EI； 步骤三、 将S PS内核值为k的超边中核值 最小的节点存 入队列Q中； 步骤四、 从队列Q中取 出一个节点u， 若队列Q 为空， 则跳转到步骤 七； 步骤五、 对于节点u的所有邻边e， 计算EI(e)中仍存在的边的数目作为deg(u)如果deg (u)<k,则继续 算法， 否则跳转到步骤四； 步骤六、 将节点u存入nodeset集合中， 对于节点u的NI(u)中的边e， 将边e中核值等于k 的节点存 入队列Q中， 并将该边标记为 不存在， 跳转到步骤四；权　利　要　求　书 1/2 页 2 CN 114780628 A 2步骤七、 将nodeset中所有的节点， 核值均减少1， 根据现有的节点核值， 更新对应的NI 和EI， 跳转到步骤一。权　利　要　求　书 2/2 页 3 CN 114780628 A 3