[發明專利]基于頂點切割的動態冪律圖實時重劃分方法

有效

• 申請號: 201910559823.0
• 申請日: 2019-06-26
• 公開（公告）號: CN110264467B
• 公開（公告）日: 2022-12-06
• 發明（設計）人: 李賀;袁航;黃健斌
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06T7/10
• 分類號: G06T7/10
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

1.一種基于頂點切割的動態冪律圖實時重劃分方法，其特征在于，實時分配每條新邊，構造邊集合，將邊集合轉移到待接收該邊集合的計算機，該方法的步驟如下：

(1)對動態冪律圖進行初始劃分：

(1a)將一個持續產生新邊的動態冪律圖上傳到由k個計算機組成的分布式圖處理系統中，通過該系統內部的圖劃分技術，將持續產生新邊的動態冪律圖劃分為h個子圖，得到頂點允許被復制到多個子圖中的初始劃分后的動態冪律圖，其中h與k的取值相等，且k與h均為不小于2的整數；

(1b)將每個子圖加載到一個對應的計算機中；

(2)實時分配每條新邊：

(2a)若初始劃分后的動態冪律圖產生的新邊所連接的兩個頂點同時被復制到多個子圖中，每個子圖對應一個計算機，則將該新邊分配到其中負載最小的計算機包含的子圖中；

(2b)若初始劃分后的動態冪律圖產生的新邊所連接的兩個頂點不在同一個子圖中，則利用啟發式公式，得到一個待接收新邊的計算機，復制該新邊所連接的不在待接收新邊的計算機的頂點，并將該新邊和被復制的頂點分配到待接收新邊的計算機包含的子圖中；

(2c)若初始劃分后的動態冪律圖產生的新邊所連接的一個頂點被復制到多個子圖中，每個子圖對應一個計算機，另一個頂點是新頂點，則將該新邊和新頂點分配到其中負載最小的計算機包含的子圖中；

(2d)若初始劃分后的動態冪律圖產生的新邊所連接的兩個頂點均為新頂點，則將該新邊和兩個新頂點分配到所有計算機中負載最小的計算機包含的子圖中；

(3)構造邊集合：

(3a)每條新邊被分配到對應子圖后，將所有該新邊連接的頂點所在的子圖放入一個集合中；

(3b)從集合中選擇一個未選過的子圖，在該子圖對應的計算機中建立一個空的頂點集合；

(3c)將新邊連接的被復制的頂點和該頂點的相鄰頂點加入到頂點集合中，分別統計頂點集合中復制到其他各個子圖的頂點數，以每個子圖中包含的頂點集合中的頂點數作為元素組成一個數組，將數組中頂點集合所在的計算機包含的子圖和負載超過閾值的計算機包含的子圖對應的元素設置為0；

(3d)從數組中選取一個最大值元素，在頂點集合中移除沒有被復制到最大值元素對應的子圖中的頂點；

(3e)統計頂點集合中的內部點割數，所述內部點割數指的是在子圖中有相鄰頂點不在頂點集合中的頂點總數；

(3f)建立一個空的邊集合，將所有連接頂點集合中的頂點的邊加入到邊集合中，用數組中元素的最大值減去內部點割數，得到了邊集合的增益值；

(3g)判斷邊集合的增益值是否大于0，若是，則將該增益值保存到邊集合中，否則，清空邊集合；

(3h)判斷是否選完集合中所有的子圖，若是，則執行步驟(4)，否則，執行步驟(3b)；

(4)轉移邊集合：

(4a)將每條被分配的新邊對應的所有邊集合，按照增益值降序排列成一個隊列；

(4b)從隊列的頭部選取一個邊集合；

(4c)將所選邊集合中的所有邊轉移到邊集合增益值對應的計算機包含的子圖中；

(4d)在所選邊集合所在的計算機包含的子圖中刪除沒有相鄰頂點的所有頂點；

(4e)判斷隊列是否為空，若是，則執行步驟(5)，否則，執行步驟(4b)；

(5)完成了動態冪律圖的重劃分。

2.根據權利要求1所述的基于頂點切割的動態冪律圖實時重劃分方法，其特征在于：步驟(2a)、步驟(2c)、步驟(2d)、步驟(3c)中所述的負載是指計算機包含的子圖中邊的總數。