隨著大數(shù)據(jù)時(shí)代的到來,數(shù)據(jù)成爆炸式增長,隨之出現(xiàn)的網(wǎng)絡(luò)規(guī)模越來越大,網(wǎng)絡(luò)結(jié)構(gòu)也越來越復(fù)雜。在大規(guī)模復(fù)雜關(guān)系網(wǎng)絡(luò)中蘊(yùn)含著巨大的研究價(jià)值,其中求解全源最短路徑(All Pairs Shortest Paths,APSP)是研究大規(guī)模復(fù)雜網(wǎng)絡(luò)的一個(gè)基本問題。傳統(tǒng)的求解APSP的算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)下效率不高,而引入路徑阻斷的算法相對(duì)于傳統(tǒng)的算法在復(fù)雜網(wǎng)絡(luò)下表現(xiàn)出較好的性能。由于大規(guī)模復(fù)雜網(wǎng)絡(luò)中,數(shù)據(jù)量較大,在單機(jī)下計(jì)算速度較慢,因此,本文提出分布式環(huán)境下引入路徑阻斷的BFS算法來解決大規(guī)模復(fù)雜網(wǎng)絡(luò)下求解APSP的問題。首先本課題在志愿計(jì)算框架下對(duì)引入路徑阻斷的算法進(jìn)行闡述,并通過實(shí)驗(yàn)證明,在大規(guī)模復(fù)雜網(wǎng)絡(luò)下,引入路徑阻斷的算法比傳統(tǒng)的算法效率要高。其次,通過對(duì)引入路徑阻斷的算法進(jìn)行分析,我們提出三種優(yōu)化策略,即基于層數(shù),基于入隊(duì)個(gè)數(shù),以及基于層數(shù)和入隊(duì)個(gè)數(shù)。這三種優(yōu)化策略通過嚴(yán)格阻斷點(diǎn)條件,阻止不適合的阻斷點(diǎn)進(jìn)入阻斷過程,從而提高算法效率。最后,本課題通過實(shí)驗(yàn)對(duì)上述算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。本文通過多個(gè)公開數(shù)據(jù)集對(duì)上述方法進(jìn)行實(shí)驗(yàn)驗(yàn)證,這些數(shù)據(jù)集都是公開且真實(shí)的。實(shí)驗(yàn)結(jié)果表明在大規(guī)模復(fù)雜網(wǎng)絡(luò)下,用志愿...

【文章頁數(shù)】：71 頁

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

【部分圖文】：

圖３－１網(wǎng)絡(luò)節(jié)點(diǎn)圖??Ｆｉ．３－１?Ｔｈｅ?ｎｏｄｅ?ｏｆ?ｎｅｔｗｏｒｋ??

圖３－１網(wǎng)絡(luò)節(jié)點(diǎn)圖??Ｆｉｇ．３－１?Ｔｈｅ?ｎｏｄｅ?ｏｆ?ｎｅｔｗｏｒｋ??圖３－１表示我們將要進(jìn)行計(jì)算的圖，其中圖的節(jié)點(diǎn)用英文字母標(biāo)識(shí)的圓圈來代表，??這些節(jié)點(diǎn)通過以實(shí)線表示的邊進(jìn)行連接，通過這些，構(gòu)成了一個(gè)簡單的無權(quán)無向圖。??在這些節(jié)點(diǎn)中，節(jié)點(diǎn)ｖ表示我們需要求解單源最短....

圖３－２阻斷點(diǎn)為ｕ的圖??－

?〇??圖３－１網(wǎng)絡(luò)節(jié)點(diǎn)圖??Ｆｉｇ．３－１?Ｔｈｅ?ｎｏｄｅ?ｏｆ?ｎｅｔｗｏｒｋ??圖３－１表示我們將要進(jìn)行計(jì)算的圖，其中圖的節(jié)點(diǎn)用英文字母標(biāo)識(shí)的圓圈來代表，??這些節(jié)點(diǎn)通過以實(shí)線表示的邊進(jìn)行連接，通過這些，構(gòu)成了一個(gè)簡單的無權(quán)無向圖。??在這些節(jié)點(diǎn)中，節(jié)點(diǎn)ｖ表示我們需要求解....

圖３－３阻斷點(diǎn)為ｄ的圖??Ｆｉｇ．３－３?Ｂｌｏｃｋｉｎｇ?Ｇｒａｐｈ?ｗｉｔｈ?ｔｈｅ?ｎｏｄｅ?ｄ??

最短路徑為ｄｉｖ［ｄ］［ｖ］＋ｄｉｖ［ｄ］［ｂ］，而根據(jù)圖我們司以明顯看出，從節(jié)點(diǎn)ｖ到節(jié)點(diǎn)ｂ的最??短路徑是ｖ－ｕ－ａ－ｂ。因此，用節(jié)點(diǎn)ｄ作為阻斷點(diǎn)計(jì)算節(jié)點(diǎn)ｖ的單源最短路徑時(shí)，得到的??結(jié)果是不準(zhǔn)確的。如圖３－３所示，其中灰色標(biāo)注的節(jié)點(diǎn)ｄ為阻斷點(diǎn)。??〇??圖３－３阻斷點(diǎn)為ｄ的圖....

圖4-4Levelblock和enqueue_卜lock比較

通過圖４－３，我們可知，利用入隊(duì)個(gè)數(shù)進(jìn)行優(yōu)化的算法在分布式系統(tǒng)下優(yōu)于引入??路徑阻斷的算法。同時(shí)，對(duì)圖４－４進(jìn)行觀察分析，可知，根據(jù)層數(shù)和根據(jù)入隊(duì)個(gè)數(shù)兩??３９??

本文編號(hào)：4041631