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

  更多相關文章： 復雜網(wǎng)絡 搜索 鄰接矩陣 節(jié)點重要性 最大度改進算法

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 高碩;拓撲—量子鍵鄰接矩陣的構(gòu)建及其在有機物定量構(gòu)效關系研究中的應用[D];中南大學;2008年

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

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

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

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

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

5 秦導;管道網(wǎng)絡拓撲模型分析計算與應用[D];北京化工大學;2001年

，

本文編號：1059724