结合最大度与随机游走策略的复杂网络搜索技术研究

论文摘要

现实生活的不同领域中存在着形形色色的复杂网络,在复杂网络理论体系中,搜索问题一直是重要的研究课题之一,并且有着大量的实际应用。很多实际网络中的搜索,例如万维网中网页的搜索,目标节点没有任何可以利用的全局信息,因此各节点只能使用一些诸如邻居节点的身份或度等局部信息进行搜索,寻找最短路径或者较短路径。因此,对复杂网络中搜索问题的研究主要是对局部搜索策略的研究,而局部搜索策略的性能直接影响到搜索的效率和成本,具有重要的现实意义。本文介绍了复杂网络模型的拓扑与演化特性,对已有的搜索策略进行了详细分析,编程实现这些搜索策略。并基于最大度不适用均匀网络的成因,设计有效的搜索策略,利用已有数据集验证其性能的优劣。通过仿真,将本文设计的搜索策略同与其关系密切的五种搜索策略进行实验对比。具体研究工作如下：一、从基本的网络模型和局部搜索策略出发,了解复杂网络的特性和各局部搜索策略的性能,对现有的局部搜索策略进行改进,提出将最大度与随机游走搜索策略相结合的设计思想。借助随机游走单步处理时间短、向前移动快的特性,通过缩短在不满足条件节点上的处理时间,以达到优化平均搜索时间的最终目的,并通过仿真证明了该设想在大规模真实网络数据集中的有效性。二、针对新策略在平均搜索步数方面所表现出的不足,进一步研究,总结此类混合策略的共同点,发现算法的设计都是在节点不满足条件的情况下,找了一种替代算法和最大度配合使用,但却没有将下一跳节点是否满足条件考虑其中,因此提出了改进搜索策略,仍然将最大度和随机游走结合使用,一方面加入对下一跳节点的考虑,一方面降低随机游走的使用频率,以优化平均搜索步数,通过仿真证实了算法设计的合理性。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究目的及意义
• 1.2 研究现状
• 1.3 研究任务与论文内容安排
• 第2章 复杂网络研究概述
• 2.1 基本理论
• 2.1.1 平均路径长度
• 2.1.2 度分布
• 2.1.3 聚类系数
• 2.1.4 小世界效应
• 2.1.5 无标度特性
• 2.2 基本模型
• 2.2.1 规则网络模型
• 2.2.2 随机模型
• 2.2.3 小世界模型
• 2.2.4 无标度模型
• 第3章 复杂网络搜索技术研究
• 3.1 广度优先
• 3.2 随机游走
• 3.3 最大度
• 3.4 各种改进的搜索策略
• 3.4.1 改进的广度优先搜索
• 3.4.2 改进的随机游走搜索
• 3.4.3 改进的最大度搜索
• 第4章 算法设计与实现
• 4.1 结合最大度与随机游走搜索策略
• 4.1.1 问题的提出
• 4.1.2 DSARW算法设计思想
• 4.2 预处理
• 4.2.1 文件格式转换及处理
• 4.2.2 数据结构设计与实现
• 4.3 仿真设计
• 4.3.1 评价指标
• 4.3.2 对比方案
• 4.3.3 对比算法
• 4.3.4 仿真实验流程
• 4.4 DSARW仿真实验
• 4.4.1 临界值选取
• 4.4.2 实验对比
• 4.4.3 结果分析
• 4.5 改进的搜索策略
• 4.5.1 分析DSARW缺陷的必然性
• 4.5.2 DSARW2算法设计思想
• 4.6 DSARW2仿真实验
• 4.6.1 临界值选取
• 4.6.2 实验对比
• 4.6.3 结果分析
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢