[發明專利]一種網絡圖分割方法及系統

有效

• 申請號: 201710544733.5
• 申請日: 2017-07-06
• 公開（公告）號: CN107222565B
• 公開（公告）日: 2019-07-12
• 發明（設計）人: 李鳳蓮;張雪英;焦江麗;李彥民;田玉楚;劉康;孫穎
• 申請（專利權）人: 太原理工大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/723;H04L12/26
• 代理公司: 北京高沃律師事務所 11569
• 代理人: 王戈

本發明公開一種網絡圖分割方法及系統。該方法包括：隨機將N類標簽均勻分配給網絡圖中的頂點，隨機選取多個頂點作為起始頂點，對于任一起始點，判斷是否存在滿足交換條件的鄰接點，如果是，確定一個鄰接點，進行標簽交換；如果否，在全圖范圍內隨機選取一個頂點，判斷是否滿足交換條件，如果是，則進行標簽交換，如果否，重新選取一個頂點；直至連續T次迭代的全圖通信量變化小于設定閾值，迭代停止，獲得分割后的子圖，每一子圖由標簽相同的全部頂點組成。采用本發明方法或系統，從通信負載均衡角度對網絡圖進行劃分，利用標簽交換，降低子圖與子圖之間的通信量，實現各個節點的通信負載均衡，從而提高計算系統資源利用率，減少計算消耗時間。

技術領域

本發明涉及分布式計算機領域，特別是涉及一種網絡圖分割方法及系統。

背景技術

海量社交網絡數據中蘊含著豐富的信息，圖論是挖掘這些信息的重要方法之一。面對日益增多的圖數據，分布式計算成為處理大規模網絡圖數據的有效手段。在分布式圖計算中，通信所消耗的時間占有很大的比例，通過圖分割方法的設計可以有效地降低通信量并實現負載均衡，從而提高分布式圖計算的效率。

現有的網絡圖分割方法主要考慮如何降低全圖通信量的問題。目前主要的圖分割方法有多層圖劃分方法，該方法的基本原理是先將圖粗化為多個較小的子圖，再分別將每個子圖分割成K個部分，最后將每一小塊映射到全圖得到較為優化的K個分割圖。

以上圖分割方法相比于全圖通信雖然可以在一定程度上提高分布式圖方法執行效率，但是大多數實驗中發現通信負載過重的節點會導致在該節點運行的程序因網絡擁堵而被阻塞，最終通信負載過重的節點會嚴重拖延整個任務的執行時間。

發明內容

本發明的目的是提供一種網絡圖分割方法及系統，以解決由于通信負載不均衡導致運行程序因網絡擁堵被阻塞，嚴重拖延整個任務的執行時間的問題，提高整個任務的執行效率。

為實現上述目的，本發明提供了如下方案：

一種網絡圖分割方法，所述方法包括：

隨機將N類標簽均勻分配給初始網絡圖中的所有頂點，其中N為大于2的整數；對于所述初始網絡圖中的任意頂點O、頂點O的鄰接點P，當所述頂點O與所述鄰接點P的標簽不同時，所述頂點O與所述鄰接點P之間通過通信邊通信；

隨機選取M個頂點作為起始頂點，其中M為大于0的整數；

對于M個頂點中的任一頂點Q，判斷是否存在滿足交換條件的頂點Q的鄰接點，得到第一判斷結果；所述滿足交換條件為兩個頂點的標簽交換后，形成的網絡圖的全圖通信量降低；

當所述第一判斷結果表示存在滿足交換條件的所述頂點Q的鄰接點時，確定與所述頂點Q進行標簽交換的一個鄰接點R；

將所述頂點Q的標簽與所述鄰接點R的標簽交換，得到第一網絡圖；所述第一網絡圖中任一頂點與鄰接點的標簽不同時，兩者之間通過通信邊通信；

完成一次迭代，判斷是否有滿足交換條件的所述頂點Q的鄰接點的鄰接點，進入下一次迭代；

當所述第一判斷結果表示不存在滿足交換條件的所述頂點Q的鄰接點時，在所述初始網絡圖全圖范圍內隨機選取一個頂點S，判斷所述頂點Q與所述頂點S是否滿足交換條件，得到第二判斷結果；

當所述第二判斷結果表示所述頂點Q與所述頂點S滿足交換條件時，將所述頂點Q的標簽與所述頂點S的標簽交換，得到第二網絡圖；所述第二網絡圖中任一頂點與鄰接點的標簽不同時，兩者之間通過通信邊通信；

完成一次迭代，判斷是否存在滿足交換條件的所述頂點S的鄰接點，進入下一次迭代；

當所述第二判斷結果表示所述頂點Q與所述頂點S不滿足交換條件時，完成一次迭代，返回“在所述初始網絡圖全圖范圍內隨機選取一個頂點”步驟，進入下一次迭代；