發(fā)布時(shí)間：2025-01-04 03:47

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

【文章頁(yè)數(shù)】：70 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

本文編號(hào)：4022857