Network Discovery by Generalized Random Walks
arXiv:1008.4980 · doi:10.1209/0295-5075/92/50008
Abstract
We investigate network exploration by random walks defined via stationary and adaptive transition probabilities on large graphs. We derive an exact formula valid for arbitrary graphs and arbitrary walks with stationary transition probabilities (STP), for the average number of discovered edges as function of time. We show that for STP walks site and edge exploration obey the same scaling as function of time . Therefore, edge exploration on graphs with many loops is always lagging compared to site exploration, the revealed graph being sparse until almost all nodes have been discovered. We then introduce the Edge Explorer Model, which presents a novel class of adaptive walks, that perform faithful network discovery even on dense networks.
arXiv comment23 pages, 7 figures
References in corpus (12)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Epidemic spreading in scale-free networks
- Hierarchical organization of modularity in metabolic networks
- The spread of epidemic disease on networks
- Search in Power-Law Networks
- Random Geometric Graphs
- Scaling theory of transport in complex networks
- Scaling Properties of Random Walks on Small-World Networks
- Scaling of random spreading in small world networks
- Network Discovery by Generalized Random Walks
- Random Walks on Complex Networks
Cited by in corpus (7)
- Random walks and diffusion on networks
- Memory in network flows and its effects on spreading dynamics and community detection
- Unveiling the relationship between complex networks metrics and word senses
- Distributed flow optimization and cascading effects in weighted complex networks
- Network Discovery by Generalized Random Walks
- Understanding Complex Systems: From Networks to Optimal Higher-Order Models
- Sampling a Network to Find Nodes of Interest