買專利賣專利找龍圖騰，真高效！ 查專利查商標用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或微信搜索“龍圖騰網”。