复杂网络中路径优化问题的研究与应用.pdf

分类号 密级

UDC 注 1


学 位 论 文

复杂网络中路径优化问题的研究与应用
（题名和副题名）


冯旻昱
（作者姓名）


指导教师 王晓斌 教授、博士
电子科技大学 成都
尹晓君 高级工程师
四川华能康定水电责任公司 成都
（姓名、职称、单位名称）
申请学位级别 硕士 专业学位类别 工程硕士
工程领域名称 软件工程
提交论文日期 论文答辩日期
学位授予单位和日期 电子科技大学 2013年 6月 28 日
答辩委员会主席
评阅人
注 1：注明《国际十进分类法 UDC》的类号
THE RESEARCH AND APPLICATION OF PATH
OPTIMIZATION ISSUE FOR COMPLEX
NETWORK




A Thesis Submitted to
University of Electronic Science and Technology of China



Major: Software Engineering
Author: Minyu Feng
Advisor: Xiaobin Wang
School:School of Information and Software Engineering
摘 要
上世纪末,随着人类社会中以因特网为代表的信息技术的兴起，复杂网络的研
究逐渐引起了人们的注意力。复杂网络自身的多样的应用价值使其成为科学研究
的一个重要挑战。因此，为了更透彻的了解人类生活中的网络，我们需要更深入
的研究复杂网络的性质。在众多的复杂网络研究领域中，搜索问题是其中最有趣
和实用性的课题。复杂网络的搜索理论解决了许多实际问题，包括社交网络中任
意两个人的关系链的查找，万维网中的网页查找以及 P2P 网络中具体数据或者文
件的查找。
2000 年, 在 Kleinberg 首次证明了复杂网络的可搜索性以后，许多优秀的搜索
算法等被一一提出用来解决上述的搜索问题，比如贪婪算法（GA）、随机游走（RW）
和最大度搜索算法（HDS）。这些经典算法成功地实现了复杂网络中信息的传递，
但是由于这些经典算法自身的局限性使其更适用于部分特定网络，搜索速度也较
缓慢。本论文提出两种新的搜索算法用于提高搜索速度和扩大适用网络范围，它
们分别是：
1. k 步游走最大度算法，该算法在执行最大度搜索的过程中穿插使用随机游
走，这样做可以确保两种算法的