Biased random search in complex networks
Journal
arXiv preprint arXiv:1907.08222
Date Issued
2019-07
Author(s)
Kocarev, Ljupcho
Abstract
We study two types of biased random walk over complex networks, which are based on local
information. In the first approach, the transitions towards neighboring nodes with smaller degrees
are favored. We show analytically that for well connected networks, biasing the random walk
based on inverse of nodes’ degrees leads to a uniform distribution of the visiting frequency, which
arguably helps in speeding up the search. The second approach explores a random walk with a onestep memory with two-hop paths arrival balancing. We introduce a framework based on absorbing Markov chains for theoretical calculation of the mean first passage time in random walk with memory and apply it in the second approach. Numerical simulations indicate that both approaches can reduce the mean searching time of the target. The one-step memory based method proved to be better for undirected networks, while the inverse-degree biasing leads to faster search in directed networks.
information. In the first approach, the transitions towards neighboring nodes with smaller degrees
are favored. We show analytically that for well connected networks, biasing the random walk
based on inverse of nodes’ degrees leads to a uniform distribution of the visiting frequency, which
arguably helps in speeding up the search. The second approach explores a random walk with a onestep memory with two-hop paths arrival balancing. We introduce a framework based on absorbing Markov chains for theoretical calculation of the mean first passage time in random walk with memory and apply it in the second approach. Numerical simulations indicate that both approaches can reduce the mean searching time of the target. The one-step memory based method proved to be better for undirected networks, while the inverse-degree biasing leads to faster search in directed networks.
File(s)![Thumbnail Image]()
Loading...
Name
Biased_Random_Search_in_Complex_Networks.pdf
Size
520.89 KB
Format
Adobe PDF
Checksum
(MD5):42da60b5f6a70d5062c576b887a4f2fd