一种基于布朗粒子的混合搜索模型  

A mixed search model of Brownian particles

作　　者：濮存来[1] 裴文江[1] 王少平[1] 

机构地区：[1]东南大学信息科学与工程学院,南京210096

出　　处：《物理学报》2010年第1期103-110,共8页Acta Physica Sinica

基　　金：国家自然科学基金(批准号:60672095;60972165);国家高技术研究发展计划(863计划)(批准号:2007AA11Z210);教育部博士点基金(批准号:20070286004);江苏省高技术研究项目;江苏省自然科学基金(批准号:BK2008281);国家十一五密码发展基金;国家火炬计划项目资助的课题~~

摘　　要：基于网络上的布朗粒子运动基本原理,提出了一种单粒子和多粒子相结合的混合搜索模型.该模型将一次搜索过程分成单粒子搜索与多粒子搜索两个阶段,既克服了单粒子搜索效率低下的缺点,又降低了多粒子搜索的硬件代价.在各种复杂网络拓扑上实施该模型,并与混合导航模型进行比较.结果表明,混合搜索模型的平均搜索时间收敛更快,硬件代价更小.将度大优先的目标选择策略与混合搜索模型相结合,能进一步提高搜索效率.此外通过仿真发现,在无标度网络上混合搜索模型的效率远高于单粒子随机行走,与多粒子随机行走的效率相当,但硬件代价远小于多粒子行走.最后针对该模型给出了一种能有效降低负载的"吸收"策略.According to the basic theories of Brownian motion, a mixed search model is proposed. By dividing every search process into two phases： single random walk search and multiple random walk searches, it improves the efficiency of a single random walk while reduces the hardware cost of multiple random walks. Compared with the mixing navigation model proposed by Tao Zhou, our model converges much faster on complex networks with lower hardware cost. We also compared two selection strategies： random selection and target selection, and found that our model improves the search efficiency further on complex networks when employed with target selection, which is prefered to the nodes of the highest degrees. Besides, by simulations on scale-free networks, we found the efficiency of our model is far higher than the single random walk and comparable to multiple random walks while the hardware cost of our model is far less. Finally, we give an absorption strategy to reduce the traffic load produced by the MS model.

关 键 词：复杂网络 随机行走 首达时间 搜索 

分 类 号：O157.5[理学—数学]