科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 a function of time. We show that for STP walks site and edge exploration obey the same scaling similar to n(lambda). as a function of time n. 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 (EEM), which presents a novel class of adaptive walks, that perform faithful network discovery even on dense networks.
- 出版日期2010-12
