【摘要】：復(fù)雜系統(tǒng)是現(xiàn)實(shí)世界的重要組成部分，復(fù)雜網(wǎng)絡(luò)是對(duì)復(fù)雜系統(tǒng)的抽象。研究并發(fā)掘復(fù)雜網(wǎng)絡(luò)的性質(zhì)可以幫助人們更好的理解復(fù)雜系統(tǒng)。隨著社會(huì)的網(wǎng)絡(luò)化以及計(jì)算機(jī)技術(shù)的不斷發(fā)展，人們對(duì)現(xiàn)實(shí)世界的建模能力較過去有了長(zhǎng)足的發(fā)展，這使得網(wǎng)絡(luò)科學(xué)的工作者所接觸的網(wǎng)絡(luò)模型越來越復(fù)雜，面對(duì)的任務(wù)也越來越重。而社區(qū)結(jié)構(gòu)是人們認(rèn)識(shí)復(fù)雜網(wǎng)絡(luò)的一個(gè)有力工具，從而使得解決復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)挖掘問題成為一項(xiàng)積極有意義的工作。現(xiàn)實(shí)世界中個(gè)人在生活工作中所產(chǎn)生的數(shù)據(jù)急劇增加，同樣它們所需要的信息量也隨之增加。面對(duì)海量數(shù)據(jù)，如何在一個(gè)可接受的時(shí)間內(nèi)挖掘出特定人群所需要的信息是一個(gè)重要的挑戰(zhàn)，分布式成為人們處理海量數(shù)據(jù)的主要方式之一。 文中首先分析了復(fù)雜網(wǎng)絡(luò)的基本特征并以此引出復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特征；然后分析了現(xiàn)有的社區(qū)結(jié)構(gòu)挖掘算法，總結(jié)了算法的優(yōu)缺點(diǎn)�；谌中畔⒌纳鐓^(qū)結(jié)構(gòu)挖掘算法需要利用網(wǎng)絡(luò)的全局信息，因此時(shí)空復(fù)雜度都較高，而且在復(fù)雜網(wǎng)絡(luò)中全局信息并不容易獲得。為此本文研究并實(shí)現(xiàn)了一種基于局部信息的社區(qū)結(jié)構(gòu)挖掘算法，同時(shí)將其推廣到分布式平臺(tái)上進(jìn)行實(shí)現(xiàn)。利用分布式平臺(tái)的優(yōu)勢(shì)，達(dá)到時(shí)間與空間的良好平衡。文中在Clauset提出的局部模塊度概念的基礎(chǔ)上提出了一個(gè)新的衡量節(jié)點(diǎn)是否屬于特定社區(qū)的函數(shù)，應(yīng)用該函數(shù)對(duì)Bagrow算法進(jìn)行改進(jìn)，改進(jìn)的算法考慮了節(jié)點(diǎn)的更多信息，因此在精確度上取得了進(jìn)展，但是算法的迭代速度并沒有提高。隨后文中分析了本地社區(qū)中節(jié)點(diǎn)的特點(diǎn)并提出了兩種啟發(fā)式方法，應(yīng)用啟發(fā)式得出了一種新的算法，新算法在保持準(zhǔn)確度的同時(shí)提高了算法的迭代速度，而后將其以MapReduce的編程模型進(jìn)行實(shí)現(xiàn)，最后在Hadoop開源平臺(tái)上實(shí)現(xiàn)整個(gè)算法，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。 實(shí)驗(yàn)結(jié)果表明改進(jìn)算法較原始的Bagrow算法在精確度上有了一定的進(jìn)步。而算法的MapReduce實(shí)現(xiàn)則證明了在數(shù)據(jù)量逐漸增大時(shí)，分布式計(jì)算是一個(gè)有力的武器。
【圖文】：

率 p 重新將該邊和頂點(diǎn)（從環(huán)上隨機(jī)選擇一個(gè)頂點(diǎn)）連接起來，相平行的邊的出現(xiàn)，即從一個(gè)頂點(diǎn)開始到另一個(gè)相同的頂點(diǎn)有兩個(gè)方面衡量圖的結(jié)構(gòu)特征，路徑長(zhǎng)度 L ( p )和聚類系數(shù) C ( p )。其離程度，而 C ( p )衡量相鄰節(jié)點(diǎn)之間的社區(qū)性。當(dāng) p 0時(shí)有L 當(dāng) p 1時(shí) 有 L ln n lnk， 且 C k n 0。 以 上 各 式 n) 1，其中 k ln( n)是為了保證隨機(jī)圖是連接的。綜上，得出以是高聚類，大世界（big world）的,這是因?yàn)?L 隨著 n 的增長(zhǎng)呈線圖是低聚類，小世界（small world）的，因?yàn)長(zhǎng)隨著n的增長(zhǎng)只呈會(huì)令人產(chǎn)生這樣的懷疑:值較大的L總是和值較大的C 相聯(lián)系。 2.2 揭示了直覺與事實(shí)是相反的。從圖中可以看出 p 有一個(gè)取值域里 L ( p )總是維持一個(gè)很小的值randomL 而與此同時(shí) ( )randC p C在正說明了網(wǎng)絡(luò)的小世界性是存在的。通過對(duì)自然存在的網(wǎng)絡(luò)的了這一區(qū)域，從而說明網(wǎng)絡(luò)中的小世界性是普遍存在的。

很多鄰居節(jié)點(diǎn)的節(jié)點(diǎn)。這兩個(gè)特性László和Réka提出了一個(gè)網(wǎng)絡(luò)增長(zhǎng)模型來說明網(wǎng)絡(luò)中節(jié)。該模型的過程是這樣的，模型中初始具有0m 個(gè)節(jié)點(diǎn)，每一步加入一入的節(jié)點(diǎn)有0m ( m m)條邊，連接模型中已有的 m 個(gè)節(jié)點(diǎn)。假設(shè)一個(gè)模型中節(jié)點(diǎn)i的概率 p 取決于節(jié)點(diǎn)i的度ik ，于是有 ( )i i jp k k k，，中擁有0t m個(gè)節(jié)點(diǎn)和 mt 條邊。這樣一來整個(gè)網(wǎng)絡(luò)就將進(jìn)入一個(gè)無標(biāo)中的一個(gè)節(jié)點(diǎn)具有k 條邊的概率服從指數(shù)為 Y 2.9 0.1的冪律分布。
【學(xué)位授予單位】：哈爾濱工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：N941.4;TP311.13

【參考文獻(xiàn)】

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

1 李曉佳;張鵬;狄增如;樊瑛;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2008年03期

2 萬(wàn)雪飛;陳端兵;傅彥;;一種重疊社區(qū)發(fā)現(xiàn)的啟發(fā)式算法[J];計(jì)算機(jī)工程與應(yīng)用;2010年03期

3 王立敏;高學(xué)東;馬紅權(quán);;基于最大節(jié)點(diǎn)接近度的局部社團(tuán)結(jié)構(gòu)探測(cè)算法[J];計(jì)算機(jī)工程;2010年01期

4 郎君;秦兵;宋巍;劉龍;劉挺;李生;;基于社會(huì)網(wǎng)絡(luò)的人名檢索結(jié)果重名消解[J];計(jì)算機(jī)學(xué)報(bào);2009年07期

5 陳瓊;李輝輝;肖南峰;;基于節(jié)點(diǎn)動(dòng)態(tài)屬性相似性的社會(huì)網(wǎng)絡(luò)社區(qū)推薦算法[J];計(jì)算機(jī)應(yīng)用;2010年05期

6 吳玲玉;高學(xué)東;;考慮對(duì)象屬性信息的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2010年24期

7 朱永真;夏正友;卜湛;劉新建;;虛擬社區(qū)中的社團(tuán)結(jié)構(gòu)研究與分析[J];計(jì)算機(jī)技術(shù)與發(fā)展;2011年01期

本文編號(hào)：2682551