An optimal path finding strategy in networks based on random walk

作者：Hu, Bin^*; Qian, Huan-yan; Shen, Yi; Yan, Jia-xing

来源：Cluster Computing, 2016, 19(4): 2179-2188.

DOI：10.1007/s10586-016-0674-6

• Shortest path
• Random walk
• Multiple particles
• Multiple sources

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.

• 出版日期2016-12
• 单位南京农业大学; 东南大学; 南京理工大学