(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210368301.4 (22)申请日 2022.04.02 (71)申请人 武汉大学 地址 430072 湖北省武汉市武昌区珞珈山 (72)发明人 赵琛　刘梦赤　 (74)专利代理 机构 武汉智权专利代理事务所 (特殊普通 合伙) 42225 专利代理师 张凯 (51)Int.Cl. G06F 17/18(2006.01) G06F 9/50(2006.01) (54)发明名称 基于直方图的K-core算法、 装置、 设备及存 储介质 (57)摘要 本发明公开了一种基于直方图的K ‑core算 法、 装置、 设备及存储介质， 涉及K ‑core分解算法 技术领域， 该方法包括： 根据每个节点的邻接点 的度数分布建立对应节点的直方图； 基于当前的 直方图， 对涉及的节点进行正向收敛和反向广 播， 以完成一次迭代， 并对正向收敛和反向广播 的过程中核数发生变化的节点的直方图进行修 改； 重复迭代过程， 以所有节点的直方图不发生 变化时的长度作为各个节点的稳态核数。 本发明 中的算法在具备扩展性的同时还能保证计算速 度。 权利要求书2页 说明书11页 附图4页 CN 114756822 A 2022.07.15 CN 114756822 A 1.一种基于直方图的K ‑core算法， 其特 征在于， 该 方法包括以下步骤： 根据每个节点的邻接点的度数分布建立对应节点的直方图； 基于当前的直方图， 对涉及的节点进行正向收敛和反向广播， 以完成一 次迭代， 并对正 向收敛和反向广播的过程中核数发生变化的节点的直方图进行修改； 重复迭代过程， 以所有节点的直方图不发生变化时的长度作为各个节点的稳态核数。 2.如权利 要求1所述的一种基于直方图的K ‑core算法， 其特征在于， 所述根据每个节点 的邻接点的度数分布建立对应节点的直方图， 包括： 将每个节点的核数初始化 为度数， 每 个节点的度数为该节点的邻接点数量； 根据一节点的度数大小， 确定该节点的邻接点的度数分布的度数值种类， 统计该节点 的邻接点的度数在每种度数值下 所包括的个数； 以度数值种类作为直方图长度， 并以每种度数值下所包括的个数作为直方图的数据， 来建立对应节点的直方图。 3.如权利 要求2所述的一种基于直方图的K ‑core算法， 其特征在于， 所述根据一节点的 度数， 确定该节点的邻接点的度数分布的度数值种类， 包括： 当一节点的度 数为N时， 确定该节点的邻接点的度数分布的度 数值种类为N， 其中N为自 然数。 4.如权利 要求2所述的一种基于直方图的K ‑core算法， 其特征在于， 所述基于当前的直 方图， 对涉及的节 点进行正向收敛和反向广播， 以完成一次迭代， 并对正向收敛和反向广播 的过程中核数发生变化的节点的直方图进行修改， 包括： 以当前的直方图长度作为每个节点当前核数， 确定因支持度不够而不 能维护当前核数 的活动节点 集合； 更新活动节点集合中的节点的核数， 使得更新后的核数在具有足够支持度的同时尽可 能大， 并基于更新后的核数对活动节点集合中的节点的直方图的长度和数据进行修改， 以 完成节点的正向 收敛； 确定活动节点 集合中的节点 不能为其邻接点 提供支持度的邻接点 集合； 更新邻接点集合中的节点的核数， 使活动节点集合中的节点可为邻 接点集合中的节点 提供支持度， 并基于更新后的核数对邻接点集合中的节点的直方图的长度和数据进行修 改， 以完成节点的反向广播。 5.一种实现基于直方图的K ‑core算法的装置， 其特 征在于， 包括： 生成模块， 其 根据每个节点的邻接点的度数分布建立对应节点的直方图； 迭代模块， 其基于当前的直方图， 对涉及的节点进行正向收敛和反向广播， 以完成一 次 迭代， 并对正向 收敛和反向广播的过程中核数发生变化的节点的直方图进行修改； 所述迭代模块还用于重复迭代过程， 以所有节点的直方图不发生变化 时的长度作为各 个节点的稳态核数。 6.如权利要求5所述的一种装置， 其特征在于， 所述生成模块根据每个节点的邻 接点的 度数分布建立对应节点的直方图， 包括： 将每个节点的核数初始化 为度数， 每 个节点的度数为该节点的邻接点数量； 根据一节点的度数大小， 确定该节点的邻接点的度数分布的度数值种类， 统计该节点 的邻接点的度数在每种度数值下 所包括的个数；权　利　要　求　书 1/2 页 2 CN 114756822 A 2以度数值种类作为直方图长度， 并以每种度数值下所包括的个数作为直方图的数据， 来建立对应节点的直方图。 7.如权利要求6所述的一种装置， 其特征在于， 所述生成模块根据一节点的度数， 确定 该节点的邻接点的度数分布的度数值种类， 包括： 当一节点的度 数为N时， 确定该节点的邻接点的度数分布的度 数值种类为N， 其中N为自 然数。 8.如权利要求6所述的一种装置， 其特征在于， 所述迭代模块基于当前的直方图， 对涉 及的节点进行正向收敛和反向广播， 以完成一次迭代， 并对正向收敛和反向广播的过程中 核数发生变化的节点的直方图进行修改， 包括： 以当前的直方图长度作为每个节点当前核数， 确定因支持度不够而不 能维护当前核数 的活动节点 集合； 更新活动节点集合中的节点的核数， 使得更新后的核数在具有足够支持度的同时尽可 能大， 并基于更新后的核数对活动节点集合中的节点的直方图的长度和数据进行修改， 以 完成节点的正向 收敛； 确定活动节点 集合中的节点 不能为其邻接点 提供支持度的邻接点 集合； 更新邻接点集合中的节点的核数， 使活动节点集合中的节点可为邻 接点集合中的节点 提供支持度， 并基于更新后的核数对邻接点集合中的节点的直方图的长度和数据进行修 改， 以完成节点的反向广播。 9.一种设备， 其特征在于， 所述设备包括处理器、 存储器、 以及存储在所述存储器上并 可被所述处理器执行 的计算机程序， 其中所述计算机程序被所述处理器执行时， 实现如权 利要求1至4中任一项所述的基于直方图的K ‑core算法的步骤。 10.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质上存储有计算机 程序， 其中所述计算机程序被处理器执行时， 实现如权利要求1至4中任一项所述的基于直 方图的K‑core算法的步骤。权　利　要　求　书 2/2 页 3 CN 114756822 A 3