[發明專利]一種基于博弈的流圖劃分方法和系統

有效

• 申請號: 201810108725.0
• 申請日: 2018-02-02
• 公開（公告）號: CN108319698B
• 公開（公告）日: 2021-01-15
• 發明（設計）人: 華強勝;石宣化;金海;李陽陽
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06N20/00
• 代理公司: 北京海虹嘉誠知識產權代理有限公司 11129
• 代理人: 何志欣;侯越玲

本發明涉及一種基于博弈的流圖劃分方法和系統，該方法包括：由一個或多個處理器對流圖進行劃分，一個或多個處理器被配置為：讀取流圖的未劃分區域中含預設邊數的邊流作為子圖；基于第一預劃分模型將子圖的邊預劃分到至少兩個劃分塊中作為博弈過程的初始狀態；通過博弈過程序貫地為子圖的每條邊選擇其最優劃分塊直至博弈過程收斂；本發明提供的方法和系統可以利用流圖的局部信息進行劃分，劃分過程不用將整個流圖載入內存，具有很好的擴展性，同時支持動態圖劃分；本發明提供的劃分方法和系統能基于博弈過程獲得更好的劃分結果。

技術領域

本發明涉及流圖處理領域，尤其涉及一種基于博弈的流圖劃分方法和系統。

背景技術

圖數據挖掘是當前研究的熱門問題。從給定的圖數據集找到求解如PageRank，聯通分量(CC)，介數中心度(Betweeness centrality)等圖性質，是圖挖掘的主要研究問題。這些性質可以用來衡量圖中點的重要程度，比如搜索引擎用PageRank做網頁重要程度排名，介數中心度用來衡量用戶在社交網絡中影響力等，這些圖性質都有廣泛的應用場景。

普通單機受內存限制，不能處理大圖數據。這是就需要借助分布式系統進行處理。在分布式系統中處理圖數據，一個很自然的問題就是如何將圖數據合理地布局在分布式系統中的各臺機器上。這也是圖劃分問題的典型應用場景。提高分布式系統性能的兩種重要方法就是：1、保證各臺機器上的計算負載均衡(每臺機器上邊的數目盡可能一樣多)；2、各臺機器間的通信盡可能少(跨越不同機器的鏈接數盡可能少，詳見圖1示例說明)。兩點對應到圖劃分的語境下，就是經典圖劃分問題的兩個準則：1、各個劃分塊的邊(頂點)盡可能一樣多；2、跨越不同劃分塊的點(邊)盡可能少。

然而經典的圖劃分問題，無論是邊劃分還是頂點劃分，都是NP難問題。目前實際采用的劃分方法都是啟發式算法。這些算法按照是否需要將獲得圖的全局信息才能劃分，又分為流式圖劃分和非流式圖劃分。非流式圖劃分方法需要將整個圖都載入內存中，需要獲得如頂點度數這類圖的全局信息，才能劃分。典型的非流式圖劃分如METIS。其基本思想是將圖中多個頂點凝結為一個頂點，這樣可以大大減少圖中點的數目。然后在粗化后的圖中采用復雜度較高的K.L.算法進行劃分，最后將劃分好的粗化圖還原到原始圖。雖然該方法具有較好的劃分結果，但是除去圖數據本身占用的內存外，METIS的粗化過程需要存放大量的中間結果。因此，該方法只適用于圖數據集較小的情形，可擴展性較差。

流式圖劃分方法基于流處理模型，圖通過邊流或者頂點流(包括其鄰接點)方式到達，對每條邊(頂點)的劃分只需要根據當前邊(頂點)和已經到達的邊(頂點)決定。具有很好的可擴展性，同時支持動態圖(允許圖動態的增加邊或頂點)，基于頂點流的典型算法如LDG、FENNEL，基于邊流的典型算法如HDRF。當前流式圖劃分方法的缺陷在于，每條邊只計算一輪最小代價函數，就做出策略選擇，這樣獲得的局部最優值是較差的。

發明內容

針對現有技術之不足，本發明提供了一種基于博弈的流圖劃分方法和系統，本發明能夠規避非流式圖劃分方法內存占用大，可擴展性差的缺點，同時在流式劃分過程中，通過博弈過程，充分利用當前輪中其它玩家的策略選擇信息，即當前其他邊和/或頂點被放置在哪個劃分塊中，從而更好地做出決策，達到更好的劃分結果。

根據一個優選實施方式，一種基于博弈的流圖劃分方法，所述方法包括：

由一個或多個處理器對流圖進行劃分，所述一個或多個處理器被配置為：