大规模网络上的随机行走过程研究+文献综述
本文探讨了用随机行走进行网络搜索研究的各种情况，分析网络拓扑结构对随机行走搜索算法的性能影响。具体研究了单粒子随机行走搜索过程、多粒子随机行走搜索过程、单多粒子混合随机行走搜索过程和有偏随机行走搜索过程。由仿真实验得出：单粒子随机行走搜索策略效率较低，从小度节点行走到大度节点的搜索效率高于从大度节点到小度节点的搜索效率；多粒子随机行走搜索策略效率很高，增加随机行走的粒子数可以提高搜索效率；单多粒子混合随机行走搜索策略的效率远高于单粒子搜索策略，略低于多粒子随机行走搜索策略，增加多粒子节点的复制能力可以提高搜索效率；采用有偏随机行走可以提高搜索效率。19376
关键词: 复杂网络 随机行走 首次到达时间 网络搜索
毕业论文设计说明书（论文）外文摘要
Title Research of random walks on large scale network
Abstract
Twenty-first century is the information age. There is a wide variety of information dissemination on the Internet, such as the rumor spread, virus dissemination process is very common. Random walk as a transmission mode has very important value of understanding and application.
This paper discusses the research of search on the network by random walk and analyze the impact of network topology on the random walk search algorithm performance. We specific discuss a single particle search process by random walk,multi-particle search process by random walk,a single multi-particle mixing search process by random walk，search process by Biased random walk. From the simulation experimental results: Single-particle random walk’s search efficiency is low, walk from low-degree node to high-degree node is more efficient than walk from high-degree node to low-degree node ; Multi-particle random walk has high search efficiency, increase the number of particles can improve search efficiency in multi-particle random walk; single multi-particle mixing random walk’s search efficiency is much higher than the single-particle random walk’s search efficiency and slightly lower than the multi-particle random walk’s search efficiency, increasing the ability to multi-particle node replication can improve search efficiency; using a biased random walk can improve search efficiency.
Keywords: Complex Network, Random Walk, First passage time, Network
Research
目 次
1 绪论 2
1.1 网络模型综述 2
1.2 网络搜索研究综述 4
1.3 本文研究思路介绍 5
1.4 本章小结 5
2 生成小世界网络和无尺度网络 6
2.1 小世界网络模型 6
2.2 无尺度网络模型 7
2.3 本章小结 7
3 模拟随机行走过程 9
3.1 单粒子随机行走 9
3.2 多粒子随机行走 13
3.3 单多粒子混合随机行走 19
3.4 有偏随机行走 23
3.5 本章小结 25
结 论 27
致 谢 28
参 考 文 献 29
1 绪论
1.1 网络模型综述
1.1.1 小世界网络模型