【摘要】：圖作為非結(jié)構(gòu)化數(shù)據(jù)中的一種重要的類型,比線性表和樹結(jié)構(gòu)在語義和結(jié)構(gòu)方面都有更強(qiáng)的表示能力。很多現(xiàn)實世界中的問題都可以用圖來表示,對圖數(shù)據(jù)的處理以及相關(guān)的應(yīng)用無處不在。而隨著信息爆炸型增長及社會網(wǎng)絡(luò)的大力發(fā)展,需要處理的圖數(shù)據(jù)的規(guī)模與日俱增,這對大規(guī)模圖的高效處理提出了巨大挑戰(zhàn)。云計算是處理海量數(shù)據(jù)挖掘任務(wù)、提升海量數(shù)據(jù)挖掘能力的有效手段之一,本文正是以這個思路為出發(fā)點,設(shè)計并實現(xiàn)了一個基于Pregel-Like架構(gòu)的并行圖挖掘平臺。底層云存儲架構(gòu)選擇HDFS(Hadoop Distributed File System),可以為大規(guī)模圖的存儲提供高效、安全、高容錯的支持。云計算框架使用BSP(Bulk Synchronous Parallel model)模型,其特有的超級步非常適合需要迭代計算的圖算法,使得對大規(guī)模圖數(shù)據(jù)的分析成為可能。平臺集成了各類圖挖掘算法,并對各算法分析結(jié)果及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)提供了可視化展示。本文的主要工作是通過對經(jīng)典圖挖掘算法及相關(guān)改進(jìn)算法的調(diào)研,在底層框架的基礎(chǔ)上設(shè)計并實現(xiàn)了圖屬性分析和圖排序中對經(jīng)典重要算法的改進(jìn)算法,并結(jié)合實際數(shù)據(jù)集對經(jīng)典算法及改進(jìn)算法的結(jié)果做了對比,最后提出了一種新的圖聚類算法。具體內(nèi)容如下:1)設(shè)計并實現(xiàn)了 K-shell分解和半局部中心性兩種圖屬性并行算法,兩者相比于度值可以更好地刻畫節(jié)點重要性,計算復(fù)雜度又要比介數(shù)的計算低,基于公共數(shù)據(jù)集分析了兩者的分布及與度的相關(guān)分布。2)設(shè)計并實現(xiàn)了 LeaderRank 和 SALSA(Stochastic Approach for Link Structure Analysis)兩種圖排序算法,前者相比于PageRank算法收斂更快,能夠更好地識別有影響力的節(jié)點,且抗干擾能力強(qiáng)。后者相比于 HITS(Hypertext-Induced Topic Search)算法,其 hub 值能更好地衡量節(jié)點傳播能力。3)提出了一種基于K-shell值的社團(tuán)發(fā)現(xiàn)算法,通過K-shell分解縮小網(wǎng)絡(luò)規(guī)模提高運行效率,根據(jù)“基準(zhǔn)”網(wǎng)絡(luò)驗證了正確性。
[Abstract]:As an important type of unstructured data, graphs have better semantic and structural representation than linear tables and tree structures. Many real-world problems can be represented by graphs, and the processing of graph data and related applications are everywhere. With the explosive growth of information and the vigorous development of social network, the scale of graph data that needs to be processed is increasing day by day, which poses a great challenge to the efficient processing of large-scale graph. Cloud computing is one of the effective means to deal with the task of massive data mining and to improve the capability of massive data mining. This paper designs and implements a parallel graph mining platform based on Pregel-Like architecture with this idea as the starting point. The underlying cloud storage architecture, HDFS (Hadoop Distributed File System), can provide efficient, secure, and fault-tolerant support for large-scale graph storage. Cloud computing framework uses BSP (Bulk Synchronous Parallel model) model, and its unique super-step is very suitable for graph algorithm which needs iterative computation, which makes it possible to analyze large-scale graph data. The platform integrates all kinds of graph mining algorithms, and provides a visual display of the analysis results and network topology of each algorithm. The main work of this paper is to design and implement an improved algorithm of classical important algorithm in graph attribute analysis and graph sorting based on the investigation of classical graph mining algorithm and related improved algorithm. The results of the classical algorithm and the improved algorithm are compared with the actual data set. Finally, a new graph clustering algorithm is proposed. The main contents are as follows: 1) the parallel algorithms of K-shell decomposition and semi-local centrality are designed and implemented. Compared with the values, the two algorithms can better describe the importance of nodes, and the computational complexity is lower than that of the meshwork. Based on the common data set, we analyze the distribution of the two and the correlation distribution of degree. 2) We design and implement two kinds of graph sorting algorithms: LeaderRank and SALSA (Stochastic Approach for Link Structure Analysis), the former converges faster than the PageRank algorithm, and the former converges faster than the PageRank algorithm. Can better identify influential nodes, and strong anti-interference ability. Compared with HITS (Hypertext-Induced Topic Search), the hub value of the latter can better measure the propagation ability of nodes. 3) A community discovery algorithm based on K-shell value is proposed, which reduces the size of the network and improves the efficiency of operation by K-shell decomposition. The correctness is verified according to the "benchmark" network.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 馬安光;;棋子問題的算法分析——2003年第11期題解[J];程序員;2004年01期

2 馮舜璽;;新書推薦:《算法分析導(dǎo)論》[J];計算機(jī)教育;2006年05期

3 張力,慕曉冬;計算機(jī)算法分析淺談[J];武警工程學(xué)院學(xué)報;2002年04期

4 馬安光;;飛彈問題的算法分析——2003年第10期題解[J];程序員;2003年12期

5 蘇運霖;;《算法分析導(dǎo)論》評介[J];計算機(jī)教育;2006年07期

6 朱力強(qiáng);;培養(yǎng)學(xué)生創(chuàng)新思維與能力的算法分析案例[J];計算機(jī)與信息技術(shù);2007年11期

7 汪菊琴;;幾種常見特殊方陣的算法分析與實現(xiàn)[J];無錫職業(yè)技術(shù)學(xué)院學(xué)報;2009年05期

8 李涵;;“算法分析與設(shè)計”課程教學(xué)改革和實踐[J];中國電力教育;2010年16期

9 劉寧;管濤;;淺析案例教學(xué)法在算法分析與設(shè)計課程中的應(yīng)用[J];科技風(fēng);2011年07期

10 胡峰;王國胤;;“算法分析與設(shè)計”教學(xué)模式探索[J];當(dāng)代教育理論與實踐;2011年12期

相關(guān)會議論文 前6條

1 陳洪陶;王生原;武繼剛;朱智林;楊慶德;;BSP在分布式數(shù)據(jù)庫系統(tǒng)規(guī)范中的應(yīng)用[A];第九屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集(上)[C];1990年

2 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

3 周顥;劉振華;趙保華;;構(gòu)造型的D~2FA生成算法[A];中國通信學(xué)會通信軟件技術(shù)委員會2009年學(xué)術(shù)會議論文集[C];2009年

4 賴桃桃;馮少榮;張東站;;一種基于劃分和密度的快速聚類算法[A];第二十五屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（一）[C];2008年

5 劉遠(yuǎn)新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺下物流運輸配送系統(tǒng)算法分析[A];第二十六屆中國控制會議論文集[C];2007年

6 王樹西;白碩;姜吉發(fā);;模式合一的“減首去尾”算法[A];第二屆全國學(xué)生計算語言學(xué)研討會論文集[C];2004年

相關(guān)博士學(xué)位論文 前10條

1 魏哲學(xué);樣本斷點距離問題的算法與復(fù)雜性研究[D];山東大學(xué);2015年

2 劉春明;基于增強(qiáng)學(xué)習(xí)和車輛動力學(xué)的高速公路自主駕駛研究[D];國防科學(xué)技術(shù)大學(xué);2014年

3 張敏霞;生物地理學(xué)優(yōu)化算法及其在應(yīng)急交通規(guī)劃中的應(yīng)用研究[D];浙江工業(yè)大學(xué);2015年

4 李紅;流程挖掘算法研究[D];云南大學(xué);2015年

5 卜晨陽;演化約束優(yōu)化及演化動態(tài)優(yōu)化求解算法研究[D];中國科學(xué)技術(shù)大學(xué);2017年

6 陳拉明;基于非凸優(yōu)化的稀疏重建理論與算法[D];清華大學(xué);2016年

7 劉新旺;多核學(xué)習(xí)算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

8 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學(xué);2006年

9 曾國強(qiáng);改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問題中的應(yīng)用研究[D];浙江大學(xué);2011年

10 肖永豪;蜂群算法及在圖像處理中的應(yīng)用研究[D];華南理工大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 王陽;基于Pregel-Like架構(gòu)的并行圖挖掘平臺研究與實現(xiàn)[D];北京郵電大學(xué);2016年

2 薛婧杰;多元架構(gòu)領(lǐng)導(dǎo)力模型在A集團(tuán)中的應(yīng)用研究[D];中國地質(zhì)大學(xué)(北京);2017年

3 武雅卉;網(wǎng)絡(luò)架構(gòu)中柔性結(jié)構(gòu)的研究[D];大連理工大學(xué);2017年

4 李妮莎;關(guān)于珠江公司組織架構(gòu)優(yōu)化的研究[D];廣東外語外貿(mào)大學(xué);2017年

5 黃廈;基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題研究[D];昆明理工大學(xué);2015年

6 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學(xué);2015年

7 趙官寶;基于位表的關(guān)聯(lián)規(guī)則挖掘算法研究[D];昆明理工大學(xué);2015年

8 殷文華;移動容遲網(wǎng)絡(luò)中基于社會感知的多播分發(fā)算法研究[D];內(nèi)蒙古大學(xué);2015年

9 徐翔燕;人工魚群優(yōu)化算法及其應(yīng)用研究[D];西南交通大學(xué);2015年

10 李德福;基于小世界模型的啟發(fā)式尋路算法研究[D];華中師范大學(xué);2015年

，

本文編號：2432950