[發明專利]一種基于滑動窗口的大規模動態圖劃分方法

在審

• 申請號: 201910583072.6
• 申請日: 2019-07-01
• 公開（公告）號: CN110309371A
• 公開（公告）日: 2019-10-08
• 發明（設計）人: 崔煥慶;榮炫宇;賈瑞生;魏永山;張峰;徐強
• 申請（專利權）人: 山東科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 青島智地領創專利代理有限公司 37252
• 代理人: 種艷麗

本發明公開了一種基于滑動窗口的大規模動態圖劃分方法，屬于計算機技術領域。本發明在增加頂點時，在滑動窗口中優先選取度數較高的頂點進行劃分，既能夠使得度數小的頂點向度數大的頂點聚集，又可以在每次劃分時將盡可能多的頂點劃分到適合的分區中，在實現負載均衡的同時降低了割邊數量，從而極大減少圖計算過程中的通信成本；在增加邊時，在滑動窗口中優先選取鄰接邊最多的頂點進行劃分，既能夠有效避免頻繁的頂點遷移，又可以在每次劃分時將盡可能多的鄰接頂點劃分到合適的分區中，從而極大減少了頂點的遷移次數，提高了劃分效率，并實現了負載均衡和割邊數量的最小化。

技術領域

本發明屬于計算機技術領域，具體涉及一種基于滑動窗口的大規模動態圖劃分方法。

背景技術

圖作為一種抽象的數據結構，可以表達復雜的結構和豐富的語義，在社交網絡、通信和科學計算等諸多領域獲得了廣泛應用。近年來隨著數據規模的不斷增長，必須借助分布式圖計算系統才能進行圖數據的分析和處理。

圖劃分是將大規模圖結構數據分布到由大量計算節點組成的分布式計算系統中的技術，是實現分布式圖計算的基礎。在圖劃分中，如果一條邊的兩個頂點被劃分到不同的計算節點上，則稱這條邊為割邊。圖劃分應最小化割邊數量并實現計算節點間的負載均衡。

當前，很多應用場景的圖數據會經常發生變化，如在社交網絡中用戶及相關關系的增加、刪除等，這類圖稱為動態圖。現有的圖劃分算法大多是針對靜態圖的，在劃分前需要將圖數據全部加載到內存后再進行劃分，此類算法用于動態圖劃分時易產生巨大的計算開銷。

發明內容

針對現有技術中存在的上述技術問題，本發明提出了一種基于滑動窗口的大規模動態圖劃分方法，設計合理，克服了現有技術的不足，具有良好的效果。

為了實現上述目的，本發明采用如下技術方案：

一種基于滑動窗口的大規模動態圖劃分方法，包括如下步驟：

步驟1：增加頂點；具體包括如下步驟：

輸入為待增加頂點的集合S_vertex、當前K個分區P_i(i＝1,2,…,K)的各個分區的頂點集合；

步驟1.1：置指定|W_vertex|的上限為L_vertex；

其中，W_vertex為將被劃分的候選頂點集合，其頂點來自S_vertex；

步驟1.2：取N＝min{|S_vertex|,L_vertex-|W_vertex|}，即|S_vertex|和L_vertex-|W_vertex|的最小值，將S_vertex中的前N個頂點增加到W_vertex中，并從S_vertex中刪除這些頂點；

步驟1.3：如果則輸出劃分結果，并結束劃分流程；否則轉步驟1.4；

步驟1.4：取v＝argmax{d_u|u∈W_vertex,d_u是頂點u的度數即與u相鄰接的頂點的個數}，即取W_vertex中度數最大的頂點v，如果有多個度數相同且度數最大的頂點，則任取其中一個；

步驟1.5：取V＝Q＝R＝{v}；V為被選中劃分到某分區的頂點集合，Q為頂點隊列；R為與V中的頂點相鄰的所有頂點的集合；

步驟1.6：若則轉步驟1.8；否則從取Q中取出第1個頂點u，并從Q中刪除該頂點；