本文關(guān)鍵詞：分布式環(huán)境下圖堅(jiān)韌度的計(jì)算

  更多相關(guān)文章： 分布式計(jì)算 圖堅(jiān)韌度 Spark

【摘要】：隨著社交網(wǎng)絡(luò)等應(yīng)用的飛速發(fā)展,圖結(jié)構(gòu)數(shù)據(jù)的理論研究,尤其是大規(guī)模圖數(shù)據(jù)在分布式環(huán)境計(jì)算變得十分必要。圖處理作為大數(shù)據(jù)處理領(lǐng)域的一個(gè)分支,形成了獨(dú)有的特色:包括較差的局部性,I/O操作頻繁,難以并行化,大規(guī)模的中間結(jié)果等等。圖堅(jiān)韌度是表示圖結(jié)構(gòu)穩(wěn)定性的圖因子,與圖頂點(diǎn)連通度和圖邊連通度相比,堅(jiān)韌度可以提供更多關(guān)于圖的穩(wěn)定程度的信息。給定任意正實(shí)數(shù)k,判斷一個(gè)圖是否是k-堅(jiān)韌的是co NP-完全問題。盡管它的計(jì)算是困難的,圖堅(jiān)韌度的概念在交通網(wǎng)絡(luò)分析,社交網(wǎng)絡(luò)分析等問題中仍起著重要作用。本文研究了分布式環(huán)境下圖堅(jiān)韌度的近似計(jì)算問題,結(jié)合圖堅(jiān)韌度與圖的拉普拉斯特征值的關(guān)系,給出了計(jì)算圖堅(jiān)韌度的下界的Lower Lap算法。我們?cè)O(shè)計(jì)了圖堅(jiān)韌度求解的分布式近似算法:基于廣度優(yōu)先搜索的算法BFS-T和基于拼接短隨機(jī)游走PageRank的Page Rank-T算法。我們基于Spark分布式計(jì)算平臺(tái)RDD和Graph X通用圖數(shù)據(jù)處理框架,利用道路交通網(wǎng)絡(luò)數(shù)據(jù)和人工合成圖數(shù)據(jù)評(píng)測(cè)了圖堅(jiān)韌度在交通網(wǎng)絡(luò)分析和復(fù)雜網(wǎng)絡(luò)分析中的效果,驗(yàn)證了上述算法的有效性。此外,我們?cè)O(shè)計(jì)和實(shí)現(xiàn)了資源監(jiān)測(cè)優(yōu)化系統(tǒng),通過調(diào)整圖數(shù)據(jù)劃分,初始點(diǎn)選擇,分析系統(tǒng)瓶頸,進(jìn)一步提升了圖堅(jiān)韌度的計(jì)算效率。
【關(guān)鍵詞】：分布式計(jì)算 圖堅(jiān)韌度 Spark
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-5
• ABSTRACT5-8
• 第1章 緒論8-18
• 1.1 課題背景及研究的目的和意義8-9
• 1.2 相關(guān)理論的發(fā)展概況9-16
• 1.2.1 圖堅(jiān)韌度理論10
• 1.2.2 相關(guān)概念10-13
• 1.2.3 分布式計(jì)算系統(tǒng)13-16
• 1.2.4 本文符號(hào)16
• 1.3 本文的主要研究內(nèi)容16-18
• 第2章 圖堅(jiān)韌度的下界估計(jì)18-27
• 2.1 圖堅(jiān)韌度18-20
• 2.2 堅(jiān)韌度下界估計(jì)算法20-26
• 2.2.1 堅(jiān)韌度與獨(dú)立集20-22
• 2.2.2 基于拉普拉斯特征值的堅(jiān)韌度下界估計(jì)算法22-26
• 2.3 本章小結(jié)26-27
• 第3章 分布式堅(jiān)韌度算法設(shè)計(jì)27-43
• 3.1 問題定義27-28
• 3.2 基于廣度優(yōu)先搜索的算法28-32
• 3.3 基于隨機(jī)游走PAGERANK的算法32-35
• 3.4 實(shí)驗(yàn)結(jié)果及分析35-42
• 3.4.1 實(shí)驗(yàn)環(huán)境36-38
• 3.4.2 實(shí)驗(yàn)數(shù)據(jù)38-39
• 3.4.3 實(shí)驗(yàn)結(jié)果及分析39-42
• 3.5 本章小結(jié)42-43
• 第4章 基于SPARK的圖堅(jiān)韌度計(jì)算43-60
• 4.1 SPARK系統(tǒng)框架43-47
• 4.1.1 彈性分布式數(shù)據(jù)集RDD43-45
• 4.1.2 圖數(shù)據(jù)處理框架Graph X45-47
• 4.2 系統(tǒng)監(jiān)測(cè)與優(yōu)化47-59
• 4.2.1 圖劃分策略47-51
• 4.2.2 磁盤、網(wǎng)絡(luò)、CPU51-58
• 4.2.3 采樣策略58-59
• 4.3 本章小結(jié)59-60
• 結(jié)論60-61
• 參考文獻(xiàn)61-66
• 致謝66

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前7條

1 肖恩利,束金龍,聞人凱;圖的代數(shù)連通度及其點(diǎn)連通度[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年04期

2 喻祥明;黃曉暉;;修正泡序圖的限制性點(diǎn)連通度(英文)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

3 侯學(xué)慧;;2-邊-軌道圖的點(diǎn)連通性[J];山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年03期

4 雷瀾,王斌;L(G)圖的若干性質(zhì)[J];重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年01期

5 李峰;曹世鵬;賈媛媛;;兩個(gè)網(wǎng)絡(luò)的可靠性比較[J];青海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

6 閆飛龍;賈子英;;基于復(fù)雜網(wǎng)絡(luò)的機(jī)降作戰(zhàn)目標(biāo)選擇方法[J];火力與指揮控制;2014年04期

7 ;[J];;年期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前7條

1 黃達(dá);有向笛卡爾乘積圖的圈點(diǎn)連通度[D];新疆大學(xué);2011年

2 吳彭;泡序圖的條件點(diǎn)連通度[D];清華大學(xué);2011年

3 韓洋;機(jī)會(huì)傳感網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)連通度及其影響因素的研究[D];南昌航空大學(xué);2014年

4 王國亮;完全對(duì)換網(wǎng)絡(luò)和三角塔網(wǎng)絡(luò)的若干性質(zhì)[D];西北師范大學(xué);2014年

5 于志華;完全多部圖的一致最可靠性與星圖的圈點(diǎn)連通度[D];新疆大學(xué);2010年

6 侯學(xué)慧;2-邊—軌道圖的連通性[D];新疆大學(xué);2011年

7 任強(qiáng);分布式環(huán)境下圖堅(jiān)韌度的計(jì)算[D];哈爾濱工業(yè)大學(xué);2015年

，

本文編號(hào)：637792