Comparison of multiple random walks strategies for searching networks
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 framewor...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2014
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/102075 http://hdl.handle.net/10220/18853 |
| _version_ | 1824456959924895744 |
|---|---|
| author | Zheng, Zhongtuan Wang, Hanxing Gao, Shengguo Wang, Guoqiang |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Zheng, Zhongtuan Wang, Hanxing Gao, Shengguo Wang, Guoqiang |
| author_sort | Zheng, Zhongtuan |
| collection | NTU |
| description | 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. |
| first_indexed | 2025-02-19T04:02:24Z |
| format | Journal Article |
| id | ntu-10356/102075 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T04:02:24Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | ntu-10356/1020752020-03-07T14:00:36Z Comparison of multiple random walks strategies for searching networks Zheng, Zhongtuan Wang, Hanxing Gao, Shengguo Wang, Guoqiang School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing 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. Published version 2014-02-24T12:15:02Z 2019-12-06T20:49:20Z 2014-02-24T12:15:02Z 2019-12-06T20:49:20Z 2013 2013 Journal Article Zheng, Z., Wang, H., Gao, S., & Wang, G. (2013). Comparison of Multiple Random Walks Strategies for Searching Networks. Mathematical Problems in Engineering, 2013, 734630-. https://hdl.handle.net/10356/102075 http://hdl.handle.net/10220/18853 10.1155/2013/734630 en Mathematical problems in engineering © 2013 Zhongtuan Zheng et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. application/pdf |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing Zheng, Zhongtuan Wang, Hanxing Gao, Shengguo Wang, Guoqiang Comparison of multiple random walks strategies for searching networks |
| title | Comparison of multiple random walks strategies for searching networks |
| title_full | Comparison of multiple random walks strategies for searching networks |
| title_fullStr | Comparison of multiple random walks strategies for searching networks |
| title_full_unstemmed | Comparison of multiple random walks strategies for searching networks |
| title_short | Comparison of multiple random walks strategies for searching networks |
| title_sort | comparison of multiple random walks strategies for searching networks |
| topic | DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing |
| url | https://hdl.handle.net/10356/102075 http://hdl.handle.net/10220/18853 |
| work_keys_str_mv | AT zhengzhongtuan comparisonofmultiplerandomwalksstrategiesforsearchingnetworks AT wanghanxing comparisonofmultiplerandomwalksstrategiesforsearchingnetworks AT gaoshengguo comparisonofmultiplerandomwalksstrategiesforsearchingnetworks AT wangguoqiang comparisonofmultiplerandomwalksstrategiesforsearchingnetworks |