基于随机行走的搜索模式研究

目??? 录????????????????????????????????? 1? 引言?? ?11.1? 课题的研究背景及意义?? ?11.2? 随机行走模型简介?? ?21.3 文章主要内容?? ?62? 随机行走模型概述?? ?72.1? 网络随机行走的理论进展?? ?72.2? 随机行走模型的应用研究?? ?83? 随机行走模型在实际中的应用?? ?123.1? 地球物理学中的随机行走模型?? ?123.2? 经济学中的随机行走模型?? ?133.3? 图论中的随机行走模型?? ?144? 基于蚁群算法的P2P网络搜索机制?? ?174.1? P2P搜索机制?? ?174.2? 蚁群算法?? ?184.2.1? 算法原理?? ?184.2.2? 系统模型?? ?184.2.3? 实现步骤?? ?194.2.4 算法的特点?? ?204.3? 蚁群算法在P2P网络中的应用?? ?204.3.1? 适合P2P的蚁群算法设计思想?? ?204.3.2? 基于蚁群算法的P2P研究框架?? ?214.4? 信息推荐算法?? ?254.5? 实验仿真?? ?274.5.1? 实验方法?? ?274.5.2? 实验结果?? ?274.5.3? 实验参数分析?? ?285? 结论?? ?30致? 谢?? ?31参 考 文 献?? ?32 v:* {behavior:url(#default#VML);} o:* {behavior:url(#default#VML);} w:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} 课题的研究背景及意义 随机行走模型具有悠久的研究历史，其起源可以追溯到人们对布朗运动的研究。随着时间的推移，随机行走模型的研究领域也逐渐从最初的物理学逐渐扩展开来，成为在计算机科学、生态学、经济学以及其他学科领域进行应用和分析的一个基本模型，并取得了卓越的成绩。 1826年，英国植物学家布朗发现水中的花粉及其它悬浮的微小颗粒不停地作不规则的曲线运动，称为布朗运动。当时，对于这一新奇的现象，人们产生了浓厚的兴趣。它产生的原理是什么?它运动的轨迹能够用什么样的数学形式来描述?在随后的研究中，布朗运动被证明其最简单的数学模型就是一个简单的对称随机行走。随着研究的不断深入，随机行走模型已经不再局限于从理论上探讨物体的运动规律这一层面，而是更多地与实际结合起来，被广泛应用于地球物理学的各个领域的研究当中。 随机行走模型在经济学领域也得到了相当大的重视。股票以及期货市场的价格变动情况是经济学中一个重要的研究内容。大量的实验结果表明，随机行走模型能够非常好的反映价格波动的特性，能够有效的支持经济学中的许多价格假说理论。随机行走模型已经成为经济学上一个非常重要的模型。运用随机行走模型可以将经济学中纷繁复杂的数据简单抽象出来，帮助人们更好地寻求经济学中蕴含的变化规律。 近年来，随机行走模型在图论中得到了长足的发展[2，3]，在算法理论上的表现尤为抢眼，帮助解决了一些NP-困难(NP-Hard)问题。而利用有限图上的随机行走设计优化算法更是当前最热门的课题之一。作为图论的一个分支学科，在复杂网络的研究中也随处可见随机行走模型的踪影，合理得运用该模型，可以很好地解决复杂网络中路径搜索的相关问题。 互联网的出现，开创人类文化的又一新篇章—信息化时代。它是一个全球性、巨大的计算机交互网络体系，把全球数万个计算机网络，数千万台主机连接起来。在其面向公众开放的短短时间内，所容纳的信息资源比任何一个图书馆或任何一个信息存储机构都要多，同时这种巨大的信息量正以惊人的速度增长。人类的生活、工作、学习、娱乐无不打上“网络”的烙印。因此如何在这庞大的网络上获得有价值的信息已成为人们日益关注的问题。搜索引擎的出现为人们快速找到所需信息带来了福音。搜索引擎是一种用于帮助互联网用户查询所需信息的搜索工具，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，从而起到信息导航的目的[1]。据CNNIC(中国互联网络信息中心)2004年发布的调查报告表明：搜索引擎成为仅次于电子邮件的第二大“用户最常使用的网络服务”[2]。而在“用户得知新网站的主要途径”调查中，搜索引擎排名第一，占83.4%。如果说网络改变了人类的生活，那么搜索引擎正是改变人类生活的工具。 P2P网络是目前计算机研究的热点。一方面它决定了服务的可靠性，即较高的搜索成功率可以回应较多的搜索结果；另一方面，它还直接影响服务性能 ,如搜索结果的平均时延过大、搜索开销过大都将直接影响用户的满意度[2]。一些提供了索引信息组织化的搜索策略在结构化网络中比较适合，如 Chord 和 CAN[3]。这些搜索策略要求对系统的拓扑结构、对象的放置策略等属性严加控制。在另外一些松散组织的 P2P系统中，以Flooding为基础的搜索技术较为常用，如随机漫步者策略，纯粹 Flooding技术可以获得较高的搜索成功率,但是成功搜索的时间花费与消息处理开销会非常大.而随机漫步者策略,即每次只选择一个邻居节点来转发、 传播搜索请求的技术,会因为信息搜索的渠道过少导致慢收敛的问题.文献[4]提出了k2度随机漫步者策略,它测试了一个合适的k值来界定每次用于转发搜索请求时的邻居个数. 但是这种策略是以随机的方式来从邻居节点集合中选择下一组转发接点集的，没有考虑到 P2P服务的聚集性、局部性。鉴于此本课题拟采用随机行走策略来提高P2P网络的搜索效率。 1.2? 随机行走模型简介 随机行走(RandomWaIk，简称RW)是一种用以描述连续的随机步骤所形成的轨迹的数学形式，物理学中众所周知的布朗运动就可以用一个简单的对称随机行走模型来描述。在计算机科学、物理学、生态学、经济学等许多领域，随机行走模型己经成为了一个用于分析和解决相关问题的基本研究模型。 通过在一维空间上的数学描述可以让我们更加直观地认识随机行走模型。一个特殊的随机行走模型是从S0=0开始，每一步以均等的概率移动士1的一个整数集Z。定义行走规则如下:假设一组独立的随机变量Z1，Z2，…，对于每个随机变量，分别以50%的概率取值为1或者-l，在此基础上，令Sn：= ，这样得到的一个序列{Sn}就称为整数集Z上的简单随机行走。我们可以任意取8组这样的随机变量，得到的随机行走示意图如图1.1所示。 文章主要内容 第一章是引言，主要内容是课题的研究背景和意义，随机行走模型简介以及各章的内容简介。 第二章是随机行走模型概述，主要内容是随机行走的理论进展，及其应用研究进展。 第三章是随机行走模型在实际中的应用，主要内容是地球物理学中的随机行走模型，经济学中的随机行走模型，图论中的随机行走模型。 第四章是基于蚁群算法的资源搜索机制。 第五章是是毕业设计心得与收获。 最后是结论，致谢以及参考资料。