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

有效

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

本發明公開了基于頂點切割的動態冪律圖實時重劃分方法。本發明能夠在Powergraph和GrapH等分布式圖處理系統中對動態冪律圖進行基于頂點切割的實時重劃分，從而提升分布式圖處理系統計算動態冪律圖的效率。本發明實現的步驟包括：對動態冪律圖進行初始劃分；實時分配每條新邊；構造邊集合；轉移邊集合；完成了動態冪律圖的重劃分。本發明能夠處理真實世界中的動態冪律圖中持續產生的新邊，通過構造并轉移邊集合實時降低了各計算機之間的通信量，且重劃分中的轉移代價較低，重劃分效率較高。

技術領域

本發明屬于計算機科學技術領域，更進一步涉及圖數據處理技術領域中的一種基于頂點切割的動態冪律圖實時重劃分方法。該方法能夠在Powergraph和GrapH等分布式圖處理系統中對動態冪律圖進行基于頂點切割的實時重劃分，從而提升分布式圖處理系統計算動態冪律圖的效率。

背景技術

在圖數據處理技術領域中，很多分布式圖處理系統通過圖劃分技術將大規模的圖劃分成多個規模幾乎相同的子圖，將它們分配到不同的計算機中并行計算。最初Google的Pregel和CMU的GraphLab使用基于邊切割的圖劃分技術，使各子圖之間被切割的邊的數量達到最少。實際上，真實世界中的圖大多數是冪律圖，冪律圖中存在大量鄰居較少的頂點和少量鄰居較多的超級頂點。這些超級頂點導致了計算機的負載不均衡，從而降低了圖計算的效率。為了高效地處理冪律圖，CMU的Powergraph采用基于頂點切割的圖劃分技術，將頂點復制到多個計算機中分攤計算量，從而使各個計算機負載均衡。然而Powergraph等基于頂點切割的分布式圖處理系統都只提供了靜態劃分算法，忽視了真實世界中冪律圖的實時動態性，例如：社交網絡中實時增加的好友關系，學術網絡中增加的作者合作關系。冪律圖中動態增加的新邊增大了計算機之間的通信量，從而降低了圖計算的性能，這就涉及到了動態冪律圖的重劃分問題。

華中科技大學在其申請的專利文獻“一種基于頂點切割與社區聚集的大規模圖劃分方法”(申請號201310686371.5，公開號CN 103699606 A)中公開了一種基于頂點切割與社區聚集的冪律圖劃分方法。該方法首先將影響任務完成時間較大的一些頂點進行切割，然后利用基于標簽傳播的社區聚集算法迭代地將切割之后的圖進行標簽傳播，將圖的各個頂點的標簽確定，得到各個頂點所在社區，最后用傳統的多層k-way圖劃分算法進行劃分。但是，該方法仍然存在的不足之處是，它忽略了真實世界的冪律圖的動態性，無法處理冪律圖中動態產生的新邊，導致分區之間的通信量隨著冪律圖的動態變化而快速增加，從而降低了圖計算的效率。

Dinesh Kumar等人在其發表的論文“GraphSteal:Dynamic Re-partitioning forEfficient Graph Processing in Heterogeneous Clusters”(2017IEEE 10thInternational Conference on Cloud Computing(CLOUD).IEEE,2017:439-446)中公開了一種用于異構集群的冪律圖動態重劃分方法。該方法首先在分布式圖處理系統中將執行時間低于平均值的計算節點歸類為快節點，將執行時間高于平均值的計算節點歸類為慢節點。然后使用重劃分器將慢節點中的邊轉移到快節點中，來平衡各個計算節點之間的計算負載。但是，該方法仍然存在的不足之處是，它在重劃分時沒有考慮各計算節點之間的通信量，導致重劃分的轉移代價較高，各計算節點之間的通信量較高，從而降低了圖計算的效率。

發明內容

本發明的目的在于針對上述已有技術的不足，提出了一種基于頂點切割的動態冪律圖實時重劃分方法。該方法可以解決包括動態學術網絡關系圖和動態社交網絡關系圖在內的大規模動態冪律圖劃分問題。

實現本發明目的的思路是，由于真實世界中的動態冪律圖持續生成新邊，導致分布式圖處理系統中越來越多的頂點被切割，從而增加了計算機之間的通信量，因此需要實時重劃分技術來減少動態冪律圖中被切割的頂點。動態冪律圖中的新邊只對它相鄰的頂點和邊產生影響，因此在新邊所在的局部進行實時重劃分，通過轉移邊集合來減少被切割的頂點，從而降低計算機間的通信量，提升圖計算的效率。