Smart random walkers: the cost of knowing the path
arXiv:1202.5568 · doi:10.1103/PhysRevE.86.011120
Abstract
In this work we study the problem of targeting signals in networks using entropy information measurements to quantify the cost of targeting. We introduce a penalization rule that imposes a restriction to the long paths and therefore focus the signal to the target. By this scheme we go continuously from fully random walkers to walkers biased to the target. We found that the optimal degree of penalization is mainly determined by the topology of the network. By analyzing several examples, we have found that a small amount of penalization reduces considerably the typical walk length, and from this we conclude that a network can be efficiently navigated with restricted information.
arXiv comment9 pages, 11 figures
References in corpus (22)
- Emergence of scaling in random networks
- Specificity and stability in topology of protein networks
- Search in Power-Law Networks
- Communicability in complex networks
- The Physics of Communicability in Complex Networks
- The entropy of network ensembles
- Networks and Cities: An Information Perspective
- Localization of maximal entropy random walk
- Biased random walks on complex networks: the role of local navigation rules
- Exploring complex networks by walking on them
- Maximal-entropy random walks in complex networks with limited information
- Exploring Complex Networks through Random Walks
- Searchability of Networks
- Traffic optimization in transport networks based on local routing
- Hide and seek on complex networks
- Disease Spreading in Structured Scale-Free Networks
- Efficient search by optimized intermittent random walks
- Information Horizons in Networks
- Localization Transition of Biased Random Walks on Random Networks
- Navigating Networks with Limited Information
- Networks and Our Limited Information Horizon
- Random Walks on Complex Networks