买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜浙江大学申请的专利一种分布式的基于邻居节点聚类的图分割方法及装置获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN118170950B 。

龙图腾网通过国家知识产权局官网在2025-05-23发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202311781141.7，技术领域涉及：G06F16/901；该发明授权一种分布式的基于邻居节点聚类的图分割方法及装置是由田文杰;王灿;史麒豪;罗进开设计研发完成，并于2023-12-22向国家知识产权局提交的专利申请。

本一种分布式的基于邻居节点聚类的图分割方法及装置在说明书摘要公布了：本发明提出了一种分布式的基于邻居节点聚类的图分割方法及装置。构建无向图以及指定的分区个数，将点集划分为若干个子集，使得每个节点均位于且仅位于其中一个子集中；满足负载均衡限制，分区大小尽可能均等；割边数量最小化，即两端处于不同分区的边的总量尽可能少。本发明基于图分割问题的LDG算法：采用邻居节点聚类的思想，将每个节点指派至邻居节点中所在最多的分区，通过将关联紧密的节点纳入同一分区降低割边的数量；对较大的分区施加线性惩罚因子，从而满足负载均衡限制。在单机LDG算法的基础上，本发明设计并实现了一套高效、易于实现，且适用于任意分区个数k的分布式并行计算方案，能在较短的运行时间内对巨型图结构完成划分。

本发明授权一种分布式的基于邻居节点聚类的图分割方法及装置在权利要求书中公布了：1.一种分布式的基于邻居节点聚类的图分割方法，其特征在于，该方法包括以下步骤：1分布式计算集群中共有P台主机，分布式计算集群中所有计算节点构成无向图结构GV,E；其中V表示计算节点的集合，E表示计算节点之间构成的边的集合；2将点集V和边集E分别划分为P个子集，将划分后边集的子集以及点集的子集中所有计算节点权值作为对应主机的初始输入；3通过主机间的All-to-all集合通信将所有计算节点u∈Viin的权值cu移动至第i台主机；将所有满足起始点u∈Viin的边u,v移动至第i台主机，得到预处理后的边集，Viin表示为标号在ri-1～ri-1范围内的所有计算节点；ri表示第i台主机计算节点标号分界点；具体步骤如下：3.1在每台主机内部，将每条无向边拆分为两条边u,v和v,u；3.2对所有拆分后的边按照u,v的字典序执行任一保证排序后负载均衡的分布式排序算法，使得算法结束后，第1台主机持有的边集持有字典序最小的2|E|P条边，第2台主机持有的边集持有紧随其后的2|E|P条边……以此类推直至最后一台主机3.3计算每台主机对应的分界点即每个节点u被划归至自身作为边的起点出现时，标号最小的主机；3.4令Viin为标号在ri-1～ri-1范围内的所有节点，通过主机间的All-to-all集合通信将所有节点u∈Viin的权值cu移动至第i台主机；3.5输入策略标号A或B；若maxdegv2|E|P，则强制将策略标号修改为B；若策略标号为B，则跳转至步骤3.7；否则，跳转至步骤3.6；3.6将所有满足起始点u∈Viin的边u,v移动至第i台主机，得到预处理后的边集结束预处理步骤；3.7对于每一个分区令3.8令ij表示所有“跨分区”的节点u：其自身处于另外第j台主机的内部节点Vjin之内，却在当前第i台主机内存在以u为起点的边；从自身存储的完成对所有的计算之后，通过All-to-all集合通信算子将其告知第j台主机，结束预处理步骤；4在第i台主机内部，定义为所有终点位于第j台主机的边，为上述中出现过的所有起始节点，i≠j，便于确定节点间通信的目标主机；5对于每个计算节点v∈V，令πv←RandInt1,k，即在1～k之间等概率随机选取一个分区标号；6执行若干次迭代，每轮迭代对分区结果πv进行更新；得到第i台主机输出所有内部节点u∈Viin最终的分区标号πu；每一轮迭代过程如下：6.1同步分区结果：第i台主机通过All-to-all集合通信将内所有节点的分区结果发送至第j台主机；6.2单机LDG算法：每台主机分别对所有内部节点以k,λ为参数执行单机LDG算法，更新所有内部节点u∈Viin的所在分区πu。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人浙江大学，其通讯地址为：310058 浙江省杭州市西湖区余杭塘路866号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。