圖結構因其能較為準確地表示現實世界中實體間的關系,而被廣泛應用于社交網絡、生物信息網絡、智能交通網等眾多領域。隨著信息技術的飛速發(fā)展,圖數據規(guī)模日益增大,分布式并行計算成為解決大規(guī)模圖數據處理的有效方法,而應用分布式并行計算的前提是快速有效地將圖分割并分配到若干臺計算機中,并盡可能保證負載平衡,避免因較大偏差造成存儲空間的浪費。同時,現實應用中,圖常隨時間而動態(tài)變化,如何對大規(guī)模動態(tài)圖進行有效地分割成為處理圖數據的關鍵,因而成為當前圖數據處理技術的研究熱點之一。本文針對當前圖分割問題進行了深入研究,發(fā)現在當前數據增長的規(guī)模與速度背景下,現實應用對圖分割效率、分割結果優(yōu)劣以及分割中的冗余存儲等方面提出了更高的要求,現有的圖分割方法已無法有效地解決大規(guī)模動態(tài)圖的分割問題。針對上述問題,本文根據相鄰兩時刻,圖的分區(qū)結構具有一定相似性的短暫平滑效應,將動態(tài)圖分割問題分為兩個階段進行解決。首先針對初始圖的靜態(tài)結構,基于分層劃分思想框架,針對初始分割階段提出了一種利用部分節(jié)點交換的算法來進行劃分,以盡可能保證負載均衡,即MPA-S方法。其次針對動態(tài)圖結構,為避免重新分割造成的巨大開銷,本文提出一種有...

【文章頁數】：70 頁

【學位級別】：碩士

【部分圖文】：

圖3-1多層次圖分割方法的基本思想步驟在整個粗化階段，原始圖的所有節(jié)點以及邊的權重都會在圖規(guī)�？s小的過程中進行累計，最終形成最小規(guī)模的縮小圖結構

節(jié)點間聯系較少，則節(jié)點間的邊的權值越小。一般來說，一個加權圖可以由G(V,E,W)三元組來表示，其中V表示的是圖G中所有節(jié)點的集合；E表示圖G中所有節(jié)點間邊的集合；W則代表圖中邊上的權重值的集合。如圖3-1所示，原圖在

本文編號：4022857