分布式環(huán)境下圖堅(jiān)韌度的計(jì)算.pdf

1、隨著社交網(wǎng)絡(luò)等應(yīng)用的飛速發(fā)展，圖結(jié)構(gòu)數(shù)據(jù)的理論研究，尤其是大規(guī)模圖數(shù)據(jù)在分布式環(huán)境計(jì)算變得十分必要。圖處理作為大數(shù)據(jù)處理領(lǐng)域的一個分支，形成了獨(dú)有的特色：包括較差的局部性，I/O操作頻繁，難以并行化，大規(guī)模的中間結(jié)果等等。圖堅(jiān)韌度是表示圖結(jié)構(gòu)穩(wěn)定性的圖因子，與圖頂點(diǎn)連通度和圖邊連通度相比，堅(jiān)韌度可以提供更多關(guān)于圖的穩(wěn)定程度的信息。給定任意正實(shí)數(shù)k，判斷一個圖是否是k-堅(jiān)韌的是coNP-完全問題。
　　盡管它的計(jì)算是困難的，圖堅(jiān)韌度

2、的概念在交通網(wǎng)絡(luò)分析，社交網(wǎng)絡(luò)分析等問題中仍起著重要作用。本文研究了分布式環(huán)境下圖堅(jiān)韌度的近似計(jì)算問題，結(jié)合圖堅(jiān)韌度與圖的拉普拉斯特征值的關(guān)系，給出了計(jì)算圖堅(jiān)韌度的下界的LowerLap算法。我們設(shè)計(jì)了圖堅(jiān)韌度求解的分布式近似算法：基于廣度優(yōu)先搜索的算法BFS-T和基于拼接短隨機(jī)游走PageRank的PageRank-T算法。
　　我們基于Spark分布式計(jì)算平臺RDD和GraphX通用圖數(shù)據(jù)處理框架，利用道路交通網(wǎng)絡(luò)數(shù)據(jù)和人工合