利用邻接矩阵研究复杂网络的控制与搜索

发布时间：2017-10-19 07:10

  本文关键词：利用邻接矩阵研究复杂网络的控制与搜索

  更多相关文章： 复杂网络 搜索 邻接矩阵 节点重要性 最大度改进算法

【摘要】：自2000年,Kleinberg首次证明了复杂网络的可搜索性后,许多优秀的搜索算法被一一提出。这些经典算法使用在当时复杂网络信息传递中,但随着对复杂网络的应用逐步深入,传统算法不能适用更多的网络,应用的普遍性不足。为了适用于更多的网络环境,本文对基于邻接矩阵各次幂的复杂网络搜索进行了研究。本文所做的工作：1)提出基于邻接矩阵各次幂信息的最大度搜索策略的改进方法。最大度算法可以看成是对邻接矩阵二次幂A2信息的运用,一些改进的基于聚类系数与最大度搜索的算法是对邻接矩阵二次幂和三次幂信息的运用。而本人是对矩阵各次幂求和,考虑的因素更多。2)用邻接矩阵方法整体描述节点之间的内在联系。常用来度量网络节点重要性的指标有度中心性、介数中心性和特征向量中心性。本文用邻接矩阵各次幂求和作为度量节点重要性的新指标,改变了最大度算法在选择下一节点的策略。3)在对新方法原理分析的基础上进行了仿真实验。将改进后的算法与最大度算法在不同网络中进行仿真比较,然后改变网络规模和聚类系数,比较改进后的算法与现存的算法的变化情况。本文新的思想与方法有：提出利用矩阵各次幂信息来作为搜索复杂网络的方法。通过对邻接矩阵各次幂求和来度量节点重要性,提出了对最大度改进的算法。改变最大度算法简单依靠邻居节点度分布情况的选择策略。邻接矩阵各次幂整体地描述了节点之间相互到达需要的路径数,利用这些可以更有效地区分网络的中心节点与边缘节点。将其作为节点重要性的度量,优先搜索通过路径数大的节点,可以改善最大度在搜索过程中易陷入网络的局部中心。通过在不同网络中,仿真比较最大度改进算法与常用算法,结果显示改进的算法能较快地到达网络中心,平均搜索步数较少,适应的网络较广。本文的工作,体现了邻接矩阵在研究复杂网络中的有效性。本文提出的复杂网络的搜索算法,具有一定的参考价值。
【关键词】：复杂网络 搜索 邻接矩阵 节点重要性 最大度改进算法
【学位授予单位】：华中师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 绪论10-12
• 第一章 复杂网络12-22
• 1.1 复杂网络的定义12-13
• 1.2 复杂网络的统计性质13-15
• 1.2.1 平均路径长度13-14
• 1.2.2 聚类系数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 本章小结21-22
• 第二章 控制复杂网络中用到的矩阵知识22-24
• 2.1 对结构可控性的改进22-23
• 2.2 仿真实验23
• 2.3 本章小结23-24
• 第三章 利用邻接矩阵对搜索复杂网络的改进24-35
• 3.1 搜索背景24-25
• 3.1.1 广度优先搜索策略24-25
• 3.1.2 随机游走搜索策略25
• 3.1.3 最大度搜索策略25
• 3.2 研究现状25-26
• 3.3 研究意义26
• 3.4 无向网络节点重要性指标26-29
• 3.4.1 度中心性27
• 3.4.2 介数中心性27-28
• 3.4.3 特征向量中心性28-29
• 3.5 提出度量节点重要性的新指标29-31
• 3.6 最大度改进算法的推导31-32
• 3.7 改进算法的过程32-34
• 3.8 本章小结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 算法优缺点40-41
• 4.3.1 算法的优点40
• 4.3.2 算法的缺点40-41
• 4.4 本章小结41-42
• 第五章 最大度改进算法的仿真42-51
• 5.1 搜索代价42-43
• 5.2 仿真环境设置43-45
• 5.3 相同条件下的比较45-47
• 5.4 改变网络规模的比较47
• 5.5 改变聚类系数的比较47-50
• 5.6 本章小结50-51
• 第六章 结论与展望51-52
• 6.1 全文总结51
• 6.2 展望51-52
• 参考文献52-55
• 致谢55

【相似文献】

中国期刊全文数据库 前10条

1 张金魁;哈密尔顿回路(通路)与邻接矩阵的一个关系[J];昌吉学院学报;2002年02期

2 熊文海;高齐圣;张嗣瀛;;复杂网络的邻接矩阵及其特征谱[J];武汉理工大学学报(交通科学与工程版);2009年01期

3 屈长青;邻接矩阵的应用[J];郴州师范高等专科学校学报;2000年06期

4 王振军;王宁宁;李鸿;牛洪亮;;基于邻接矩阵的公交换乘算法的研究[J];徐州工程学院学报;2006年03期

5 于言坤;;哈密尔顿图的矩阵判定法[J];吉林省教育学院学报(下旬);2012年09期

6 邓化宇;;邻接矩阵在数学建模中的应用[J];科技信息;2010年23期

7 刘一平;线邻接矩阵和线符号图[J];南京师大学报(自然科学版);1985年02期

8 邱英汉;;投影图邻接矩阵生成算法[J];佛山大学学报;1997年04期

9 张德龙,谭尚旺;图的邻接矩阵的奇异性[J];广西工学院学报;1999年04期

10 刘亚国;;图论中邻接矩阵的应用[J];忻州师范学院学报;2008年02期

中国重要会议论文全文数据库 前1条

1 石恒华;何泾沙;许鑫;;基于邻接矩阵的网络流量检测点设置算法[A];第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集[C];2009年

中国博士学位论文全文数据库 前1条

1 高硕;拓扑—量子键邻接矩阵的构建及其在有机物定量构效关系研究中的应用[D];中南大学;2008年

中国硕士学位论文全文数据库 前5条

1 周波;利用邻接矩阵研究复杂网络的控制与搜索[D];华中师范大学;2015年

2 张伟;结构建模中求取邻接矩阵的信息保留法[D];大连理工大学;2003年

3 向锦;基于二分图邻接矩阵的压缩传感图像重建算法研究[D];湖南师范大学;2011年

4 王忠宝;基于有机分子结构的变胞机构设计[D];北京邮电大学;2015年

5 秦导;管道网络拓扑模型分析计算与应用[D];北京化工大学;2001年

，

本文编号：1059724