復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究畢業(yè)論文

《復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究畢業(yè)論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究畢業(yè)論文目錄第一章緒論11.1復(fù)雜網(wǎng)絡(luò)的研究背景11.1.1從七橋問(wèn)題開(kāi)始11.1.2復(fù)雜網(wǎng)絡(luò)近代的研究21.2復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)研究的現(xiàn)狀31.3本文的研究?jī)?nèi)容以及文章結(jié)構(gòu)6第二章復(fù)雜網(wǎng)絡(luò)的基本概念以及網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ?2.1復(fù)雜網(wǎng)絡(luò)的基本概念72.1.1網(wǎng)絡(luò)的圖表示72.1.2平均路徑長(zhǎng)度82.1.3聚類系數(shù)82.1.4精準(zhǔn)度92.1.5復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)定義92.2網(wǎng)絡(luò)拓?fù)浠灸Ｐ秃托再|(zhì)102.2.1小世界模型102.2.2無(wú)標(biāo)度網(wǎng)絡(luò)模型112.2.3模塊性與等級(jí)網(wǎng)絡(luò)12第三章復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)143.1分級(jí)聚類143.1.1凝聚算法143.1.

2、2分裂算法153.2迭代二分法153.2.1Kernighan-Lin算法153.2.2譜平分法163.3其他經(jīng)典算法173.3.1GN（Girvan-Newman）算法173.3.2Newman快速算法173.3.3Radicchi算法17II第四章基于隨機(jī)游走的社團(tuán)發(fā)現(xiàn)算法194.1隨機(jī)游走算法的基本原理194.1.1隨機(jī)游走算法的相似度矩陣獲取194.1.2隨機(jī)游走算法的矩陣融合204.1.3矩陣元素融合方式214.2隨機(jī)游走算法的代碼編譯過(guò)程224.2.1隨機(jī)游走算法的相似度矩陣的獲取224.2.2隨機(jī)游走算法的相似度矩陣融合23第五章隨機(jī)游走算法在社團(tuán)劃分中的應(yīng)用25

3、5.1隨機(jī)游走算法對(duì)復(fù)雜網(wǎng)絡(luò)的劃分255.1.1已知社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)255.1.2對(duì)復(fù)雜網(wǎng)絡(luò)的劃分265.2隨機(jī)游走算法的復(fù)雜度28第六章基于隨機(jī)游走算法的程序優(yōu)化296.1隨機(jī)游走算法的復(fù)雜度的優(yōu)化296.2隨機(jī)游走算法的應(yīng)用于加權(quán)網(wǎng)絡(luò)30第七章總結(jié)與展望317.1總結(jié)317.2對(duì)未來(lái)的展望31參考文獻(xiàn)34致謝35II北京郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文）第一章緒論復(fù)雜網(wǎng)絡(luò)一般指節(jié)點(diǎn)眾多、連接關(guān)系復(fù)雜的網(wǎng)絡(luò)。由于其靈活普適的描述能力,能夠廣泛應(yīng)用于各科學(xué)領(lǐng)域?qū)?fù)雜系統(tǒng)進(jìn)行建模、分析,近年來(lái)吸引了越來(lái)越多的人對(duì)其進(jìn)行研究。隨著研究的深入,人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)均具有社團(tuán)結(jié)構(gòu),即整個(gè)網(wǎng)

4、絡(luò)由若干個(gè)社團(tuán)組成,社團(tuán)之間的連接相對(duì)稀疏、社團(tuán)內(nèi)部的連接相對(duì)稠密。社團(tuán)發(fā)現(xiàn)則是利用圖拓?fù)浣Y(jié)構(gòu)中所蘊(yùn)藏的信息從復(fù)雜網(wǎng)絡(luò)中解析出其模塊化的社團(tuán)結(jié)構(gòu),該問(wèn)題的深入研究有助于以一種分而治之的方式研究整個(gè)網(wǎng)絡(luò)的模塊、功能及其演化,更準(zhǔn)確地理解復(fù)雜系統(tǒng)的組織原則、拓?fù)浣Y(jié)構(gòu)與動(dòng)力學(xué)特性,具有十分重要的意義。自2002年Girvan和Newman基于邊介數(shù)提出GN算法以來(lái),國(guó)際上掀起一股社團(tuán)發(fā)現(xiàn)的研究熱潮,來(lái)自生物、物理、計(jì)算機(jī)等各學(xué)科領(lǐng)域的研究者們帶來(lái)了許多新穎的思想和算法,并廣泛應(yīng)用于各個(gè)學(xué)科領(lǐng)域的具體問(wèn)題中。1.1復(fù)雜網(wǎng)絡(luò)研究背景1.1.1從七橋問(wèn)題開(kāi)始近年來(lái)復(fù)雜網(wǎng)絡(luò)研究的興起，使得人

5、們開(kāi)始廣泛關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性及其與網(wǎng)絡(luò)行為之間的關(guān)系，要研究各種不同的復(fù)雜網(wǎng)絡(luò)在結(jié)構(gòu)上的共性，首先需要有一種描述網(wǎng)絡(luò)的統(tǒng)一工具。這種工具在數(shù)學(xué)上成為圖(graph).任何一個(gè)網(wǎng)絡(luò)都可以看做是由一些節(jié)點(diǎn)按某種方式連接而構(gòu)成的一個(gè)系統(tǒng)。具體網(wǎng)絡(luò)的抽象圖表示，就是用抽象的點(diǎn)表示具體網(wǎng)絡(luò)中的節(jié)點(diǎn)，并用節(jié)點(diǎn)之間的連線表示具體網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接關(guān)系。實(shí)際網(wǎng)絡(luò)的圖表示法可以追溯到18世紀(jì)偉大的數(shù)學(xué)家歐拉(Euler)對(duì)著名的“Konigsberg七橋問(wèn)題”的研究。Konigsberg是東普魯士（現(xiàn)俄羅斯）的一個(gè)城鎮(zhèn)，城中有一條橫貫城區(qū)的河流，河中有兩座島，兩岸和兩島間共有七座橋，一個(gè)人能否在

6、一次散步中走過(guò)所有的七座橋，而且每座橋只經(jīng)過(guò)一次，最后返回原地？1736年，歐拉仔細(xì)的研究了這個(gè)問(wèn)題。他用數(shù)學(xué)抽象法，將被河流分隔開(kāi)的四塊陸地抽象為四個(gè)點(diǎn)，分別用A、B、C和D表示，而將七座橋抽象為連接四個(gè)點(diǎn)的七條線，分別用a、b、c、d、e、f、g表示，這樣就得到了四個(gè)點(diǎn)和七條線構(gòu)成的一個(gè)圖，如圖（圖1-1）所示。35北京郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文）圖1-1七橋問(wèn)題于是歐拉考慮如果一筆畫(huà)出圖1-1，則七橋問(wèn)題迎刃而解?？梢韵胂?，能一筆畫(huà)出的圖形，一定只有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)（這里要求起點(diǎn)和終點(diǎn)重合），中間經(jīng)過(guò)的每一點(diǎn)總是包含進(jìn)去的一條線和出去的一條線，這樣除了終點(diǎn)和起點(diǎn)外，每一

7、點(diǎn)都只能有偶數(shù)條線與之相連。因此，如果要求起點(diǎn)和終點(diǎn)重合的話，那么能夠一筆畫(huà)出的圖形中所有的點(diǎn)都必然有偶數(shù)條線與之相連。從圖1-1中四個(gè)點(diǎn)看，每個(gè)點(diǎn)都是有三條或五條線通過(guò)，所以不能一筆畫(huà)出這個(gè)圖形，就是說(shuō)不重復(fù)的一次走遍七座橋是據(jù)對(duì)不可能的。歐拉的七橋問(wèn)題的抽象和論證思想，開(kāi)創(chuàng)了數(shù)學(xué)中的一個(gè)分支----圖論（graphtheory）的研究。因此，歐拉被公認(rèn)為圖論只父，而圖1-1被稱為歐拉圖。事實(shí)上，今天人們關(guān)于復(fù)雜網(wǎng)絡(luò)的研究與歐拉當(dāng)年關(guān)于七橋問(wèn)題的研究在某種程度上是一脈相承的，即網(wǎng)絡(luò)結(jié)構(gòu)域網(wǎng)