An optimal path finding strategy in networks based on random walk

详细信息    查看全文

• 作者：Bin Hu ; Huan-yan Qian ; Yi Shen ; Jia-xing Yan
• 关键词：Shortest path ; Random walk ; Multiple particles ; Multiple sources
• 刊名：Cluster Computing
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：19
• 期：4
• 页码：2179-2188
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Processor Architectures; Operating Systems; Computer Communication Networks;
• 出版者：Springer US
• ISSN：1573-7543
• 卷排序：19

文摘

In this paper, we study a path finding strategy based on random walk in which we allow multiple particles to set out from different but neighboring sources to their common destination. Three path finding models, the single-particle-form-one-source, the multiple-particles-from-one-source, and the last multiple-particles-form-multiple-sources (MSMP) are described. Then we apply the three models to different simulation networks. The experiment results show that the MSMP schema can decrease the path finding cost. Furthermore, we propose an absorption strategy to deal with the additional Brownian particles in networks. The experiment results on BA networks show that the absorption strategy can increase the probability of a successful path finding. In the end, we find he path found out by above methods may be the shortest theoretically, but may not be optimal in the practical application. To overcome this, we put forward a method to calculate the optimal path based on arrival reliability and verify its correctness by enumeration.