基于复杂网络拓扑特性的搜索算法的研究

发布时间：2017-08-18 22:31

  本文关键词：基于复杂网络拓扑特性的搜索算法的研究

  更多相关文章： 复杂网络 拓扑特性 最大度 搜索算法

【摘要】：随着以因特网为代表的信息技术的兴起,复杂网络的研究逐渐引起了人们的注意。在众多的复杂网络研究领域中,搜索问题是其中最具有实用性的课题。它涉及网络中指定文件或数据的寻找及网络中节点间最短路径的确定,为互联网中搜索引擎的设计、社交网络中人与人的交往行为等问题的研究提供了理论指导。实际的复杂网络中普遍存在多种拓扑特性,本文将兼顾复杂网络中存在的不同拓扑特性,对搜索算法进行深入的研究、分析和改进。首先,提出了最大度-最小距离搜索算法。该算法针对含有度量空间的实际复杂网络,建立一个参数可调的无标度空间网络模型。在此基础上,将度量距离与度这两个影响搜索性能的度量值相结合,使该算法既可以做到不使传递信息的方向偏离所要搜索的目的节点,又可以把搜索信息传递给含有长程连接的具有较大度的节点。其次,提出了最小聚集系数-最大度搜索算法。通过分析最大度搜索算法缺陷的成因,找到一个分界值,使得对该分界值范围内节点的搜索过程符合“按度序列”搜索的设想。基于该分界值,将节点的度与聚集系数这两个度量值相结合,使该算法既利用了幂率指数在一定范围内最大度搜索算法的明显优势,又兼顾了超出这个范围使用最小聚集系数搜索算法的高效。最后,本文使用C++编程语言,对几个拓扑特征不同的真实复杂网络数据集进行了仿真实验。依据平均搜索时间和平均搜索步数这两个指标,对几个不同复杂网络搜索算法进行了比较、分析和评价,从而验证了最大度-最小距离搜索算法和最小聚集系数-最大度搜索算法的正确性和高效性。
【关键词】：复杂网络 拓扑特性 最大度 搜索算法
【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP391.3
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第1章 绪论10-16
• 1.1 课题背景及研究的目的和意义10-11
• 1.2 国内外研究现状11-14
• 1.3 复杂网络搜索算法中存在的问题14
• 1.4 本文的主要研究内容14-15
• 1.5 本文的组织结构15-16
• 第2章 相关理论与技术16-24
• 2.1 复杂网络拓扑模型16-20
• 2.1.1 小世界网络16-18
• 2.1.2 无标度网络18-20
• 2.2 复杂网络中的搜索算法20-22
• 2.2.1 广度优先搜索算法20-21
• 2.2.2 随机游走搜索算法21-22
• 2.2.3 最大度搜索算法22
• 2.3 本章小结22-24
• 第3章 基于最大度-最短距离的复杂网络搜索方法24-33
• 3.1 引言24-25
• 3.2 相关问题及定义25-27
• 3.2.1 平均路径长度25-26
• 3.2.2 度与度分布26-27
• 3.3 最大度-最小距离算法设计27-30
• 3.3.1 无标度空间网络模型的建立27-28
• 3.3.2 搜索过程描述28-29
• 3.3.3 算法描述29-30
• 3.4 最大度-最小距离算法分析30-32
• 3.4.1 节点间距离的确定30
• 3.4.2 贪婪算法的缺陷30-31
• 3.4.3 算法性能分析31-32
• 3.5 本章小结32-33
• 第4章 基于最小聚集系数-最大度的复杂网络搜索方法33-43
• 4.1 引言33-34
• 4.2 相关问题及定义34-38
• 4.2.1 幂律分布特性34-35
• 4.2.2 聚集系数35-38
• 4.3 最小聚集系数-最大度算法设计38-41
• 4.3.1 最大度搜索算法的缺陷38-39
• 4.3.2 算法描述39-41
• 4.4 最小聚集系数-最大度算法分析41-42
• 4.4.1 分界值k0值的选取41
• 4.4.2 算法性能分析41-42
• 4.5 本章小结42-43
• 第5章 实验与结果分析43-54
• 5.1 最大度-最小距离搜索算法43-47
• 5.1.1 环境及数据集的设置43
• 5.1.2 实际复杂网络中的搜索效果43-47
• 5.2 最小聚集系数-最大度算法47-54
• 5.2.1 环境及数据集的设置47-48
• 5.2.2 分界值k_0的选取48-50
• 5.2.3 实际复杂网络中的搜索效果50-54
• 结论54-56
• 参考文献56-60
• 攻读硕士学位期间承担的科研任务与主要成果60-61
• 致谢61-62
• 作者简介62

【参考文献】

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

1 汤蓉;唐常杰;徐开阔;杨宁;;基于局部聚合的复杂网络自动聚簇算法[J];电子科技大学学报;2014年03期

2 邓小清;周竹荣;程向荣;;基于蚂蚁算法的网格资源发现模型[J];计算机应用;2007年10期

3 秦李;杨子龙;黄曙光;;复杂网络的节点重要性综合评价[J];计算机科学;2015年02期

4 吴泓润;覃俊;易云飞;李德毅;郑波尽;;基于优化理论的社区无标度网络模型[J];计算机学报;2015年02期

5 程晓涛;刘彩霞;刘树新;;基于局域信息的社交网络信息传播模型[J];计算机应用;2015年02期

6 张方风;刘军;;复杂网络拓扑结构与演化模型研究综述(一)[J];系统科学学报;2014年02期

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

1 俞峰;复杂动态随机网络最短路径问题研究[D];浙江大学;2009年

，

本文编号：697178