Comparative study of random walks with one-step memory on complex networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913577729785856 |
|---|---|
| author | Mirchev, Miroslav Basnarkov, Lasko Mishkovski, Igor |
| author_facet | Mirchev, Miroslav Basnarkov, Lasko Mishkovski, Igor |
| contents | We investigate searching efficiency of different kinds of random walk on complex networks which rely on local information and one-step memory. For the studied navigation strategies we obtained theoretical and numerical values for the graph mean first passage times as an indicator for the searching efficiency. The experiments with generated and real networks show that biasing based on inverse degree, persistence and local two-hop paths can lead to smaller searching times. Moreover, these biasing approaches can be combined to achieve a more robust random search strategy. Our findings can be applied in the modeling and solution of various real-world problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08608 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Comparative study of random walks with one-step memory on complex networks Mirchev, Miroslav Basnarkov, Lasko Mishkovski, Igor Computers and Society Social and Information Networks Physics and Society 05C81, 05C82, 68R10 G.2.2; H.3.3; I.6.3 We investigate searching efficiency of different kinds of random walk on complex networks which rely on local information and one-step memory. For the studied navigation strategies we obtained theoretical and numerical values for the graph mean first passage times as an indicator for the searching efficiency. The experiments with generated and real networks show that biasing based on inverse degree, persistence and local two-hop paths can lead to smaller searching times. Moreover, these biasing approaches can be combined to achieve a more robust random search strategy. Our findings can be applied in the modeling and solution of various real-world problems. |
| title | Comparative study of random walks with one-step memory on complex networks |
| topic | Computers and Society Social and Information Networks Physics and Society 05C81, 05C82, 68R10 G.2.2; H.3.3; I.6.3 |
| url | https://arxiv.org/abs/2411.08608 |