[發(fā)明專利]一種網(wǎng)絡(luò)圖分割方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201710544733.5
• 申請日: 2017-07-06
• 公開（公告）號: CN107222565B
• 公開（公告）日: 2019-07-12
• 發(fā)明（設(shè)計）人: 李鳳蓮;張雪英;焦江麗;李彥民;田玉楚;劉康;孫穎
• 申請（專利權(quán)）人: 太原理工大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/723;H04L12/26
• 代理公司: 北京高沃律師事務(wù)所 11569
• 代理人: 王戈

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

技術(shù)領(lǐng)域

本發(fā)明涉及分布式計算機領(lǐng)域，特別是涉及一種網(wǎng)絡(luò)圖分割方法及系統(tǒng)。

背景技術(shù)

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

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

以上圖分割方法相比于全圖通信雖然可以在一定程度上提高分布式圖方法執(zhí)行效率，但是大多數(shù)實驗中發(fā)現(xiàn)通信負(fù)載過重的節(jié)點會導(dǎo)致在該節(jié)點運行的程序因網(wǎng)絡(luò)擁堵而被阻塞，最終通信負(fù)載過重的節(jié)點會嚴(yán)重拖延整個任務(wù)的執(zhí)行時間。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種網(wǎng)絡(luò)圖分割方法及系統(tǒng)，以解決由于通信負(fù)載不均衡導(dǎo)致運行程序因網(wǎng)絡(luò)擁堵被阻塞，嚴(yán)重拖延整個任務(wù)的執(zhí)行時間的問題，提高整個任務(wù)的執(zhí)行效率。

為實現(xiàn)上述目的，本發(fā)明提供了如下方案：

一種網(wǎng)絡(luò)圖分割方法，所述方法包括：

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

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

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

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

將所述頂點Q的標(biāo)簽與所述鄰接點R的標(biāo)簽交換，得到第一網(wǎng)絡(luò)圖；所述第一網(wǎng)絡(luò)圖中任一頂點與鄰接點的標(biāo)簽不同時，兩者之間通過通信邊通信；

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

當(dāng)所述第一判斷結(jié)果表示不存在滿足交換條件的所述頂點Q的鄰接點時，在所述初始網(wǎng)絡(luò)圖全圖范圍內(nèi)隨機選取一個頂點S，判斷所述頂點Q與所述頂點S是否滿足交換條件，得到第二判斷結(jié)果；

當(dāng)所述第二判斷結(jié)果表示所述頂點Q與所述頂點S滿足交換條件時，將所述頂點Q的標(biāo)簽與所述頂點S的標(biāo)簽交換，得到第二網(wǎng)絡(luò)圖；所述第二網(wǎng)絡(luò)圖中任一頂點與鄰接點的標(biāo)簽不同時，兩者之間通過通信邊通信；

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

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