本文關(guān)鍵詞：利用鄰接矩陣研究復(fù)雜網(wǎng)絡(luò)的控制與搜索

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 搜索 鄰接矩陣 節(jié)點(diǎn)重要性 最大度改進(jìn)算法

【摘要】：自2000年,Kleinberg首次證明了復(fù)雜網(wǎng)絡(luò)的可搜索性后,許多優(yōu)秀的搜索算法被一一提出。這些經(jīng)典算法使用在當(dāng)時復(fù)雜網(wǎng)絡(luò)信息傳遞中,但隨著對復(fù)雜網(wǎng)絡(luò)的應(yīng)用逐步深入,傳統(tǒng)算法不能適用更多的網(wǎng)絡(luò),應(yīng)用的普遍性不足。為了適用于更多的網(wǎng)絡(luò)環(huán)境,本文對基于鄰接矩陣各次冪的復(fù)雜網(wǎng)絡(luò)搜索進(jìn)行了研究。本文所做的工作：1)提出基于鄰接矩陣各次冪信息的最大度搜索策略的改進(jìn)方法。最大度算法可以看成是對鄰接矩陣二次冪A2信息的運(yùn)用,一些改進(jìn)的基于聚類系數(shù)與最大度搜索的算法是對鄰接矩陣二次冪和三次冪信息的運(yùn)用。而本人是對矩陣各次冪求和,考慮的因素更多。2)用鄰接矩陣方法整體描述節(jié)點(diǎn)之間的內(nèi)在聯(lián)系。常用來度量網(wǎng)絡(luò)節(jié)點(diǎn)重要性的指標(biāo)有度中心性、介數(shù)中心性和特征向量中心性。本文用鄰接矩陣各次冪求和作為度量節(jié)點(diǎn)重要性的新指標(biāo),改變了最大度算法在選擇下一節(jié)點(diǎn)的策略。3)在對新方法原理分析的基礎(chǔ)上進(jìn)行了仿真實(shí)驗。將改進(jìn)后的算法與最大度算法在不同網(wǎng)絡(luò)中進(jìn)行仿真比較,然后改變網(wǎng)絡(luò)規(guī)模和聚類系數(shù),比較改進(jìn)后的算法與現(xiàn)存的算法的變化情況。本文新的思想與方法有：提出利用矩陣各次冪信息來作為搜索復(fù)雜網(wǎng)絡(luò)的方法。通過對鄰接矩陣各次冪求和來度量節(jié)點(diǎn)重要性,提出了對最大度改進(jìn)的算法。改變最大度算法簡單依靠鄰居節(jié)點(diǎn)度分布情況的選擇策略。鄰接矩陣各次冪整體地描述了節(jié)點(diǎn)之間相互到達(dá)需要的路徑數(shù),利用這些可以更有效地區(qū)分網(wǎng)絡(luò)的中心節(jié)點(diǎn)與邊緣節(jié)點(diǎn)。將其作為節(jié)點(diǎn)重要性的度量,優(yōu)先搜索通過路徑數(shù)大的節(jié)點(diǎn),可以改善最大度在搜索過程中易陷入網(wǎng)絡(luò)的局部中心。通過在不同網(wǎng)絡(luò)中,仿真比較最大度改進(jìn)算法與常用算法,結(jié)果顯示改進(jìn)的算法能較快地到達(dá)網(wǎng)絡(luò)中心,平均搜索步數(shù)較少,適應(yīng)的網(wǎng)絡(luò)較廣。本文的工作,體現(xiàn)了鄰接矩陣在研究復(fù)雜網(wǎng)絡(luò)中的有效性。本文提出的復(fù)雜網(wǎng)絡(luò)的搜索算法,具有一定的參考價值。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 搜索 鄰接矩陣 節(jié)點(diǎn)重要性 最大度改進(jìn)算法
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 緒論10-12
• 第一章 復(fù)雜網(wǎng)絡(luò)12-22
• 1.1 復(fù)雜網(wǎng)絡(luò)的定義12-13
• 1.2 復(fù)雜網(wǎng)絡(luò)的統(tǒng)計性質(zhì)13-15
• 1.2.1 平均路徑長度13-14
• 1.2.2 聚類系數(shù)14-15
• 1.2.3 度與度分布15
• 1.3 基本模型15-21
• 1.3.1 random network模型16-17
• 1.3.2 small-world模型17-20
• 1.3.3 scale-free network模型20-21
• 1.4 本章小結(jié)21-22
• 第二章 控制復(fù)雜網(wǎng)絡(luò)中用到的矩陣知識22-24
• 2.1 對結(jié)構(gòu)可控性的改進(jìn)22-23
• 2.2 仿真實(shí)驗23
• 2.3 本章小結(jié)23-24
• 第三章 利用鄰接矩陣對搜索復(fù)雜網(wǎng)絡(luò)的改進(jìn)24-35
• 3.1 搜索背景24-25
• 3.1.1 廣度優(yōu)先搜索策略24-25
• 3.1.2 隨機(jī)游走搜索策略25
• 3.1.3 最大度搜索策略25
• 3.2 研究現(xiàn)狀25-26
• 3.3 研究意義26
• 3.4 無向網(wǎng)絡(luò)節(jié)點(diǎn)重要性指標(biāo)26-29
• 3.4.1 度中心性27
• 3.4.2 介數(shù)中心性27-28
• 3.4.3 特征向量中心性28-29
• 3.5 提出度量節(jié)點(diǎn)重要性的新指標(biāo)29-31
• 3.6 最大度改進(jìn)算法的推導(dǎo)31-32
• 3.7 改進(jìn)算法的過程32-34
• 3.8 本章小結(jié)34-35
• 第四章 最大度改進(jìn)算法的分析35-42
• 4.1 算法比較分析35-39
• 4.1.1 最大度策略的局限性35-37
• 4.1.2 改進(jìn)分析比較37-39
• 4.2 算法性能分析39-40
• 4.2.1 最好的情況分析39
• 4.2.2 最壞的情況分析39
• 4.2.3 平均情況分析39-40
• 4.3 算法優(yōu)缺點(diǎn)40-41
• 4.3.1 算法的優(yōu)點(diǎn)40
• 4.3.2 算法的缺點(diǎn)40-41
• 4.4 本章小結(jié)41-42
• 第五章 最大度改進(jìn)算法的仿真42-51
• 5.1 搜索代價42-43
• 5.2 仿真環(huán)境設(shè)置43-45
• 5.3 相同條件下的比較45-47
• 5.4 改變網(wǎng)絡(luò)規(guī)模的比較47
• 5.5 改變聚類系數(shù)的比較47-50
• 5.6 本章小結(jié)50-51
• 第六章 結(jié)論與展望51-52
• 6.1 全文總結(jié)51
• 6.2 展望51-52
• 參考文獻(xiàn)52-55
• 致謝55

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 張金魁;哈密爾頓回路(通路)與鄰接矩陣的一個關(guān)系[J];昌吉學(xué)院學(xué)報;2002年02期

2 熊文海;高齊圣;張嗣瀛;;復(fù)雜網(wǎng)絡(luò)的鄰接矩陣及其特征譜[J];武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版);2009年01期

3 屈長青;鄰接矩陣的應(yīng)用[J];郴州師范高等�？茖W(xué)校學(xué)報;2000年06期

4 王振軍;王寧寧;李鴻;牛洪亮;;基于鄰接矩陣的公交換乘算法的研究[J];徐州工程學(xué)院學(xué)報;2006年03期

5 于言坤;;哈密爾頓圖的矩陣判定法[J];吉林省教育學(xué)院學(xué)報(下旬);2012年09期

6 鄧化宇;;鄰接矩陣在數(shù)學(xué)建模中的應(yīng)用[J];科技信息;2010年23期

7 劉一平;線鄰接矩陣和線符號圖[J];南京師大學(xué)報(自然科學(xué)版);1985年02期

8 邱英漢;;投影圖鄰接矩陣生成算法[J];佛山大學(xué)學(xué)報;1997年04期

9 張德龍,譚尚旺;圖的鄰接矩陣的奇異性[J];廣西工學(xué)院學(xué)報;1999年04期

10 劉亞國;;圖論中鄰接矩陣的應(yīng)用[J];忻州師范學(xué)院學(xué)報;2008年02期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 石恒華;何涇沙;許鑫;;基于鄰接矩陣的網(wǎng)絡(luò)流量檢測點(diǎn)設(shè)置算法[A];第八屆全國信息隱藏與多媒體安全學(xué)術(shù)大會湖南省計算機(jī)學(xué)會第十一屆學(xué)術(shù)年會論文集[C];2009年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 高碩;拓?fù)洹孔渔I鄰接矩陣的構(gòu)建及其在有機(jī)物定量構(gòu)效關(guān)系研究中的應(yīng)用[D];中南大學(xué);2008年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前5條

1 周波;利用鄰接矩陣研究復(fù)雜網(wǎng)絡(luò)的控制與搜索[D];華中師范大學(xué);2015年

2 張偉;結(jié)構(gòu)建模中求取鄰接矩陣的信息保留法[D];大連理工大學(xué);2003年

3 向錦;基于二分圖鄰接矩陣的壓縮傳感圖像重建算法研究[D];湖南師范大學(xué);2011年

4 王忠寶;基于有機(jī)分子結(jié)構(gòu)的變胞機(jī)構(gòu)設(shè)計[D];北京郵電大學(xué);2015年

5 秦導(dǎo);管道網(wǎng)絡(luò)拓?fù)淠Ｐ头治鲇嬎闩c應(yīng)用[D];北京化工大學(xué);2001年

，

本文編號：1059724