Comparison of Multiple Random Walks Strategies for Searching Networks

Zhongtuan Zheng, Hanxing Wang, Shengguo Gao and Guoqiang Wang

Mathematical Problems in Engineering, 2013, vol. 2013, 1-12

Abstract:

We investigate diverse random-walk strategies for searching networks, especially multiple random walks (MRW). We use random walks on weighted networks to establish various models of single random walks and take the order statistics approach to study corresponding MRW, which can be a general framework for understanding random walks on networks. Multiple preferential random walks (MPRW) and multiple simple random walks (MSRW) are two special types of MRW. As search strategies, MPRW prefers high-degree nodes while MSRW searches for low-degree nodes more efficiently. We analyze the first passage time (FPT) of wandering walkers of MRW and give the corresponding formulas of probability distributions and moments, and the mean first passage time (MFPT) is included. We show the convergence of the MFPT of the first arriving walker and find the MFPT of the last arriving walker closely related with the mean cover time. Simulations confirm analytical predictions and deepen discussions. We use a small random network to test the FPT properties from different aspects. We also explore some practical search-related issues by MRW, such as detecting unknown shortest paths and avoiding poor routings on networks. Our results are of practical significance for realizing optimal routing and performing efficient search on complex networks.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2013/734630.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2013/734630.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:734630

DOI: 10.1155/2013/734630

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().