[發(fā)明專利]一種基于博弈的流圖劃分方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201810108725.0
• 申請日: 2018-02-02
• 公開（公告）號: CN108319698B
• 公開（公告）日: 2021-01-15
• 發(fā)明（設(shè)計）人: 華強(qiáng)勝;石宣化;金海;李陽陽
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06N20/00
• 代理公司: 北京海虹嘉誠知識產(chǎn)權(quán)代理有限公司 11129
• 代理人: 何志欣;侯越玲

1.一種圖數(shù)據(jù)處理方法，其利用分布式系統(tǒng)處理圖數(shù)據(jù)，包括：

基于流處理模型，所述分布式系統(tǒng)中的每個處理器在讀入邊流的同時對流圖進(jìn)行劃分，其特征在于，所述對流圖進(jìn)行劃分的方法包括由所述處理器：

讀取所述流圖的未劃分區(qū)域中含預(yù)設(shè)邊數(shù)的邊流作為子圖；

基于第一預(yù)劃分模型將所述子圖的邊預(yù)劃分到至少兩個劃分塊中作為博弈過程的初始狀態(tài)；通過所述博弈過程序貫地為所述子圖的每條邊選擇其最優(yōu)劃分塊直至所述博弈過程收斂；

并行地進(jìn)行多個子圖的劃分且依據(jù)實時的計算開銷和通信開銷動態(tài)地調(diào)整并行劃分的子圖數(shù)量；

所述博弈過程包括：

將所有劃分塊構(gòu)成的集合視為策略選擇的集合，

博弈過程中的每一輪，進(jìn)行策略選擇的當(dāng)前邊依據(jù)當(dāng)前劃分結(jié)果中其他邊的劃分情況并根據(jù)預(yù)設(shè)的代價函數(shù)計算出其本輪最優(yōu)的策略選擇，

在當(dāng)前邊不處于最優(yōu)的策略選擇對應(yīng)的最優(yōu)劃分塊之時，將所述當(dāng)前邊遷移至其最優(yōu)劃分塊且對應(yīng)更新當(dāng)前劃分結(jié)果作為下一條邊進(jìn)行策略選擇的依據(jù)并在所述子圖的所有邊進(jìn)行策略選擇后以最新的當(dāng)前劃分結(jié)果再次執(zhí)行博弈過程，

在博弈過程的一輪中，在所有邊都沒有發(fā)生遷移的情況下，則此次博弈過程收斂，所述子圖的劃分完成并將本輪博弈過程所依據(jù)的當(dāng)前劃分結(jié)果作為最終劃分結(jié)果；

所述分布式系統(tǒng)中的每個處理器按照所述最終劃分結(jié)果分別處理所述流圖從而實現(xiàn)各個處理器的負(fù)載均衡并減少各個處理器之間的通信。

2.如權(quán)利要求1所述的方法，其特征在于，所述將所述當(dāng)前邊遷移至其最優(yōu)劃分塊且對應(yīng)更新當(dāng)前劃分結(jié)果作為下一條邊進(jìn)行策略選擇的依據(jù)的處理包括：當(dāng)前邊的策略選擇依賴于更新的當(dāng)前劃分結(jié)果中除去當(dāng)前邊之外的其他所有邊的劃分情況。

3.如權(quán)利要求1至2之一所述的方法，其特征在于，所述預(yù)設(shè)的代價函數(shù)為：

記p_min＝argmin_i∈[1，k]c(e_(u，v)，p_i)是取得最小代價函數(shù)值的最優(yōu)劃分塊，當(dāng)邊e_(u，v)所在的劃分塊不是其最優(yōu)劃分塊之時，則將邊e_(u，v)從其所在的劃分塊遷移到其最優(yōu)劃分塊；

其中，e_(u，v)表示連接頂點u和頂點v的邊，p_i表示編號為i的劃分塊，i∈[1，k]，k是劃分塊的數(shù)量，k≥2且為整數(shù)，α表示負(fù)載均衡度量和平均備份數(shù)度量的相對重要性，α∈(0，1)，β表示度量均一化參數(shù)，l(p_i)表示劃分塊p_i中邊的數(shù)目，d(p_i，u)表示頂點u在劃分塊p_i中的度數(shù)，d(p_i，v)表示頂點v在劃分塊p_i中的度數(shù)。

4.如權(quán)利要求3所述的方法，其特征在于，所述度量均一化參數(shù)β∈其中，|M|是所述子圖的頂點數(shù)量，|E|是所述子圖的邊數(shù)量。

5.如權(quán)利要求1至2之一所述的方法，其特征在于，所述第一預(yù)劃分模型基于隨機(jī)劃分規(guī)則，輪流為所述子圖的邊生成一個隨機(jī)數(shù)R，并將該邊劃分到與該隨機(jī)數(shù)對應(yīng)編號的劃分塊p_R中，

其中，R∈[1，k]且為整數(shù)，k是劃分塊的數(shù)量，k≥2且為整數(shù)。

6.如權(quán)利要求5所述的方法，其特征在于，所述處理器還被配置為：

獲取若干子圖和各子圖的最終劃分結(jié)果作為訓(xùn)練集；

使用所述訓(xùn)練集用于訓(xùn)練第二預(yù)劃分模型；

在訓(xùn)練次數(shù)超過預(yù)設(shè)次數(shù)之后，使用所述第二預(yù)劃分模型代替所述第一預(yù)劃分模型對待劃分的子圖進(jìn)行預(yù)劃分。

7.如權(quán)利要求1至2之一所述的方法，其特征在于，所述讀取所述流圖的未劃分區(qū)域中含預(yù)設(shè)邊數(shù)的邊流作為子圖的步驟是基于流處理模型進(jìn)行的。

8.一種圖數(shù)據(jù)處理系統(tǒng)，所述系統(tǒng)包括分布式多個處理器，基于流處理模型，所述分布式系統(tǒng)中的每個處理器在讀入邊流的同時對流圖進(jìn)行劃分，其特征在于，

所述處理器被配置為：

讀取所述流圖的未劃分區(qū)域中含預(yù)設(shè)邊數(shù)的邊流作為子圖；

基于第一預(yù)劃分模型將所述子圖的邊預(yù)劃分到至少兩個劃分塊中作為博弈過程的初始狀態(tài)；

通過所述博弈過程序貫地為所述子圖的每條邊選擇其最優(yōu)劃分塊直至所述博弈過程收斂；

所述博弈過程包括：

將所有劃分塊構(gòu)成的集合視為策略選擇的集合，

博弈過程中的每一輪，進(jìn)行策略選擇的當(dāng)前邊依據(jù)當(dāng)前劃分結(jié)果中其他邊的劃分情況并根據(jù)預(yù)設(shè)的代價函數(shù)計算出其本輪最優(yōu)的策略選擇，

在當(dāng)前邊不處于最優(yōu)的策略選擇對應(yīng)的最優(yōu)劃分塊之時，將所述當(dāng)前邊遷移至其最優(yōu)劃分塊且對應(yīng)更新當(dāng)前劃分結(jié)果作為下一條邊進(jìn)行策略選擇的依據(jù)并在所述子圖的所有邊進(jìn)行策略選擇后以最新的當(dāng)前劃分結(jié)果再次執(zhí)行博弈過程；

所述系統(tǒng)中的每個處理器按照最終劃分結(jié)果分別處理所述流圖從而實現(xiàn)各個處理器的負(fù)載均衡并減少各個處理器之間的通信；

所述博弈過程還包括：

在博弈過程的一輪中，在所有邊都沒有發(fā)生遷移的情況下，則此次博弈過程收斂，所述子圖的劃分完成并將本輪博弈過程所依據(jù)的當(dāng)前劃分結(jié)果作為最終劃分結(jié)果。