發(fā)布時(shí)間：2018-07-21 09:30

【摘要】：現(xiàn)實(shí)生活存在著許多復(fù)雜系統(tǒng),這些系統(tǒng)往往以一種復(fù)雜網(wǎng)絡(luò)的形式展現(xiàn)或者可以轉(zhuǎn)換為復(fù)雜網(wǎng)絡(luò)形式。這些網(wǎng)絡(luò)大多呈現(xiàn)出大小不一的社團(tuán)結(jié)構(gòu)(社區(qū)),所謂社團(tuán)結(jié)構(gòu)就是社團(tuán)內(nèi)部的點(diǎn)之間聯(lián)系緊密,社團(tuán)之間聯(lián)系較為稀疏的一種圖的節(jié)點(diǎn)歸屬劃分。目前,現(xiàn)實(shí)中的社交網(wǎng)絡(luò)的用戶量早已達(dá)到億級別,并且每天呈現(xiàn)爆炸式的數(shù)量增長。因此,在大規(guī)模復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)社團(tuán)結(jié)果在網(wǎng)絡(luò)結(jié)構(gòu)的理論研究和網(wǎng)絡(luò)分析實(shí)際應(yīng)用中具有重要意義。本課題基于Spark分布式計(jì)算框架進(jìn)行大規(guī)模復(fù)雜網(wǎng)絡(luò)的研究,主要有以下幾方面工作:本課題通過對社團(tuán)發(fā)現(xiàn)算法SHRINK研究,結(jié)合邊圖概念提出了一種新的重疊社團(tuán)發(fā)現(xiàn)算法LinkSRHINK算法。該算法結(jié)合了基于密度社團(tuán)發(fā)現(xiàn)算法,基于模塊度優(yōu)化算法和基于層次劃分算法,擁有社團(tuán)發(fā)現(xiàn)結(jié)果唯一確定、可以準(zhǔn)確發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)中的中心點(diǎn)和孤立點(diǎn)和社團(tuán)結(jié)構(gòu)避免過度重疊的優(yōu)點(diǎn)。此外,L inkSHRINK算法還提出一個(gè)新穎概念:社團(tuán)重疊度,從而可以發(fā)現(xiàn)具有不同重疊度的社團(tuán)結(jié)構(gòu)。實(shí)驗(yàn)表明,該算法在真實(shí)網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上表現(xiàn)都優(yōu)于經(jīng)典的重疊社團(tuán)發(fā)現(xiàn)算法。由于LinkSHRINK算法無法在大規(guī)模網(wǎng)絡(luò)中正常運(yùn)行,本課題通過采用圖抽樣和基于Spark分布式計(jì)算框架并行化LinkSHRINK從而提出新算法PLinkSHRINK算法較好地解決該問題。作為對比算法,本課題還實(shí)現(xiàn)了基于Hadoop平臺(tái)并行LinkSRHINK的算法:MLinnkSRHINK算法。實(shí)驗(yàn)證明PLinkSHRINK算法的性能優(yōu)于MLinkSRHINK算法和單機(jī)版的LinkSHRINK算法。最后,本課題基于分布式計(jì)算框架設(shè)計(jì)提出了一個(gè)高效便捷的大規(guī)模圖挖掘系統(tǒng)BDAP。該系統(tǒng)集成了相應(yīng)的圖屬性計(jì)算和社團(tuán)發(fā)現(xiàn)算法,采用工作流模式與用戶交互,方便用戶使用。
[Abstract]:There are many complex systems in real life. These systems are often displayed in the form of a complex network or can be converted into complex network forms. Most of these networks present a community structure of different sizes. The so-called community structure is a close link between the points within the community and a relatively sparse type of association. At present, the user of social networks in reality has already reached hundreds of millions of users, and presents an explosive number of increase every day. Therefore, the discovery of community results in large-scale complex networks is of great significance in the theoretical research of network structure and the practical application of network analysis. This topic is based on Spark distributed computing. The framework of large-scale complex network research, mainly in the following aspects: this topic through the community discovery algorithm SHRINK research, combined with the concept of edge graph proposed a new overlapping community discovery algorithm LinkSRHINK algorithm. This algorithm is based on the density community discovery algorithm, based on modularity optimization algorithm and hierarchy based The L inkSHRINK algorithm also presents a new concept: the overlap degree of the community, so that the community structure with different overlapping degrees can be found. The experiment shows that the algorithm is true. The performance of real network and artificial generation network is better than classical overlapping association discovery algorithm. Because LinkSHRINK algorithm can not run normally in large-scale network, this topic proposes a new algorithm PLinkSHRINK algorithm to solve the problem by using graph sampling and parallel LinkSHRINK based on Spark distributed computing framework. In contrast, this topic also implements a parallel LinkSRHINK based algorithm based on Hadoop platform: MLinnkSRHINK algorithm. The experiment proves that the performance of the PLinkSHRINK algorithm is superior to the MLinkSRHINK algorithm and the single machine version LinkSHRINK algorithm. Finally, a efficient and convenient large-scale graph mining system BDAP. is proposed based on the distributed computing framework design. The system integrates corresponding graph attribute calculation and community discovery algorithm, and uses workflow mode to interact with users to facilitate users.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5;TP301.6

【相似文獻(xiàn)】

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

1 馮成進(jìn);;0—1規(guī)劃新算法的改進(jìn)[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年02期

2 鄒汪平;;一種基于網(wǎng)絡(luò)安全控制的蜂群算法應(yīng)用研究[J];吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

3 郭毅可;韓銳;;云計(jì)算中的彈性算法:概要和展望[J];上海大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

4 劉江華;戴新喜;白似雪;;基于模式矩陣的P_Matrix算法[J];南昌大學(xué)學(xué)報(bào)(理科版);2007年05期

5 胡俊鵬;;基于雙向選擇的蟻群相遇算法的優(yōu)化[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年01期

6 張麗;;關(guān)聯(lián)規(guī)則挖掘算法的研究[J];赤峰學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年02期

7 吳秋峰;尹海東;孟翔燕;;基于和積和最大積的信念傳播算法的收斂性分析[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2011年09期

8 趙吉東;;蟻群算法的改進(jìn)策略研究[J];中國科技信息;2012年12期

9 胡森森;周賢善;;一種改進(jìn)蟻群算法的研究[J];長江大學(xué)學(xué)報(bào)(自科版);2006年10期

10 王恒娜;趙曉靜;;基于屬性覆蓋的關(guān)聯(lián)規(guī)則挖掘算法[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年03期

相關(guān)會(huì)議論文 前10條

1 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)——2004年學(xué)術(shù)年會(huì)論文集[C];2004年

2 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)2004年學(xué)術(shù)年會(huì)論文集[C];2004年

3 符麗錦;覃華;鄧海;孫欣;;一種改進(jìn)的Apriori算法的研究[A];廣西計(jì)算機(jī)學(xué)會(huì)2012年學(xué)術(shù)年會(huì)論文集[C];2012年

4 王東鋒;王軍民;陳英武;;模糊定性仿真理論研究與算法實(shí)現(xiàn)[A];'2000系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文集[C];2000年

5 ;Study on the spark discharge plasma jet driven by nanosecond pulses[A];第十五屆全國等離子體科學(xué)技術(shù)會(huì)議會(huì)議摘要集[C];2011年

6 趙唯;;晶粒度評級的改進(jìn)算法[A];中國圖象圖形科學(xué)技術(shù)新進(jìn)展——第九屆全國圖象圖形科技大會(huì)論文集[C];1998年

7 劉啟文;;可擴(kuò)展的圖形學(xué)算法演示系統(tǒng)的研究[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

8 Osamu Fujiwara;;Effect of Approaching Contact Speed of Hand-Held Metal Piece on Characteristics of Discharge Current from Charged Human Body[A];第二屆貴州省自然科學(xué)優(yōu)秀學(xué)術(shù)論文評選獲獎(jiǎng)?wù)撐募?007年）[C];2007年

9 佘智;蔣泰;朱延生;;基于Type C協(xié)議的防沖突改進(jìn)算法[A];廣西計(jì)算機(jī)學(xué)會(huì)25周年紀(jì)念會(huì)暨2011年學(xué)術(shù)年會(huì)論文集[C];2011年

10 ;β_1- but not β_2-adrenergic signaling accelerates the ryanodine receptor response to a single L-type Ca~(2+) channel in heart ceils[A];中國生理學(xué)會(huì)第23屆全國會(huì)員代表大會(huì)暨生理學(xué)學(xué)術(shù)大會(huì)論文摘要文集[C];2010年

相關(guān)重要報(bào)紙文章 前8條

1 楊娜;雪佛蘭SPARK詮釋微車[N];中國工業(yè)報(bào);2003年

2 ;雪佛蘭SPARK技術(shù)參數(shù)表[N];中國商報(bào);2003年

3 若冰;雪佛蘭Spark小車中的精靈[N];中國商報(bào);2003年

4 記者 姬旺芳;天水星火SPARK商標(biāo)獲“中國馳名商標(biāo)”[N];天水日報(bào);2010年

5 記者 曉瑗;新西蘭電信將更名為Spark[N];人民郵電;2014年

6 本報(bào)記者 那罡;微軟Spark計(jì)劃再添新成員[N];中國計(jì)算機(jī)報(bào);2009年

7 ;上汽通用五菱SPARK引發(fā)微車新熱浪[N];中國質(zhì)量報(bào);2003年

8 黃靜潔;08款SPARK樂馳上市 能否突圍微轎市場？[N];東方早報(bào);2008年

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

1 鐘永騰;基于近場MUSIC算法的復(fù)合材料結(jié)構(gòu)健康監(jiān)測研究[D];南京航空航天大學(xué);2014年

2 劉燕;入侵雜草優(yōu)化算法在陣列天線綜合中的應(yīng)用[D];西安電子科技大學(xué);2015年

3 苗義烽;突發(fā)事件下的列車運(yùn)行調(diào)度模型與算法研究[D];中國鐵道科學(xué)研究院;2015年

4 楊玉婷;頭腦風(fēng)暴優(yōu)化算法與基于視頻的非接觸式運(yùn)動(dòng)定量分析方法研究[D];浙江大學(xué);2015年

5 劉杰;全局優(yōu)化問題的幾類新算法[D];西安電子科技大學(xué);2015年

6 柏靜;基于多種混合策略的人工蜂群算法改進(jìn)研究[D];山東師范大學(xué);2016年

7 孔翔宇;幾類優(yōu)化問題的人工蜂群算法[D];西安電子科技大學(xué);2016年

8 匡立;分形網(wǎng)絡(luò)的理論、算法及應(yīng)用研究[D];武漢大學(xué);2015年

9 孫磊磊;AP聚類算法研究及其在電子病歷挖掘中的應(yīng)用[D];大連理工大學(xué);2017年

10 單美靜;求解非線性實(shí)代數(shù)系統(tǒng)的混合算法研究[D];華東師范大學(xué);2008年

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

1 尹丁藝;基于Spark的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的設(shè)計(jì)與實(shí)現(xiàn)[D];北京郵電大學(xué);2017年

2 安世勇;命題邏輯中隨機(jī)3-SAT問題算法研究[D];西南交通大學(xué);2015年

3 畢曉慶;油氣探礦權(quán)競爭性出讓系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];中國地質(zhì)大學(xué)(北京);2015年

4 王明明;鐵路大機(jī)與線路固定設(shè)施間距檢測算法研究[D];西南交通大學(xué);2015年

5 李靜;基于視頻圖像序列的運(yùn)動(dòng)目標(biāo)檢測與跟蹤算法研究[D];寧夏大學(xué);2015年

6 劉貝玲;基于天地圖的租房平臺(tái)開發(fā)及其關(guān)鍵技術(shù)研究[D];西南交通大學(xué);2015年

7 曹海鋒;IDS中串匹配臭算法并行優(yōu)化研究[D];西安建筑科技大學(xué);2015年

8 周攀;基于蟻群算法的山區(qū)高速鐵路隧道火災(zāi)應(yīng)急疏散最優(yōu)路徑研究[D];西南交通大學(xué);2015年

9 張路奇;基于改進(jìn)蟻群算法的WSN路由協(xié)議的研究[D];中國地質(zhì)大學(xué)(北京);2015年

10 王曉晨;入侵雜草優(yōu)化算法的應(yīng)用與改進(jìn)[D];長安大學(xué);2015年

，

本文編號(hào)：2135089