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

有效

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

1.一種網絡圖分割方法，其特征在于，所述方法包括：

隨機將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不滿足交換條件時，完成一次迭代，返回“在所述初始網絡圖全圖范圍內隨機選取一個頂點”步驟，進入下一次迭代；

判斷是否滿足連續T次迭代的全圖通信量變化小于設定閾值，得到第三判斷結果；所述T為大于1的整數；所述全圖通信量為各個頂點通信量之和：N_p表示頂點p的鄰接點集合，L_p為頂點p的標簽，N_p(L_p)表示頂點p的鄰接點中標簽為L_p的頂點集合,一個頂點的通信量為與該頂點的標簽不同的鄰接點的數量；

當所述第三判斷結果表示連續T次迭代的全圖通信量變化小于設定閾值時，迭代停止，獲得分割后的子圖；所述子圖中每一子圖由標簽相同的全部頂點組成。

2.根據權利要求1所述的方法，其特征在于，所述隨機將N類標簽均勻分配給初始網絡圖中的所有頂點，具體包括：

使用哈希方法隨機將N類標簽均勻分配給初始網絡圖中的所有頂點。

3.根據權利要求1所述的方法，其特征在于，所述判斷是否存在滿足交換條件的頂點Q的鄰接點，得到第一判斷結果，之前還包括：

計算所述初始網絡圖的全圖通信量；

獲得所述頂點Q的所有鄰接點；

對于任一所述頂點Q的鄰接點U，將所述鄰接點U的標簽與所述頂點Q的標簽交換，形成新的網絡圖；

計算所述新的網絡圖的全圖通信量；

判斷所述新的網絡圖的全圖通信量是否小于所述初始網絡圖的全圖通信量，得到第四判斷結果；

當所述第四判斷結果表示所述新的網絡圖的全圖通信量小于所述初始網絡圖的全圖通信量時，確定所述鄰接點U為滿足條件的所述頂點Q的鄰接點。

4.根據權利要求1所述的方法，其特征在于，所述當所述第一判斷結果表示存在滿足交換條件的所述頂點Q的鄰接點時，確定與所述頂點Q進行標簽交換的鄰接點R，具體包括：

獲取所有滿足交換條件的所述頂點Q的鄰接點；

計算所有的所述頂點Q的鄰接點的標簽與所述頂點Q的標簽交換后的第一通信量下降值；所述第一通信量為與所述頂點Q相連的通信邊和與所述頂點Q的鄰接點相連的通信邊之和；

將第一通信量下降值按從大到小的順序排序；

將前K個第一通信量下降值對應的鄰接點確定為待定交換點；

計算所述待定交換點中每個鄰接點的標簽與所述頂點Q的標簽交換前后的第二通信量差異值；所述第二通信量為所述頂點Q所在的子圖與所述鄰接點所在的子圖之間的通信量；

將第二通信量差異值中最小差異值對應的鄰接點確定為與所述頂點Q進行標簽交換的鄰接點R。