Network Discovery by Generalized Random Walks

Details Network Discovery by Generalized Random Walks Network Discovery by Generalized Random Walks

2010-08-30

arxiv.org/abs/1008.4980v1

Physics

Condensed Matter

Statistical Mechanics

23 pages, 7 figures

Scientific paper

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 $\sim n^{\lambda}$ as 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, which presents a novel class of adaptive walks, that perform faithful network discovery even on dense networks.

Affiliated with

Also associated with

No associations

Rating

Network Discovery by Generalized Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Network Discovery by Generalized Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Discovery by Generalized Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-399796