Distance-based Node Sampling using Drifting Random Walks

Details Distance-based Node Sampling using Drifting Random Walks Distance-based Node Sampling using Drifting Random Walks

2011-07-06

arxiv.org/abs/1107.1089v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

Sampling a large network with a given distribution has been identified as a useful operation to build network overlays. For example, sampling nodes with uniform probability is the cornerstone of epidemic information spreading, and constructing small world network topologies can be done by sampling with a probability that depends on the distance to a given node. In this paper we describe distributed algorithms for sampling networks, so that a node is selected with a probability that is a function of the distance of the node to a special node, called the \emph{source}. The basic technique used for sampling is a new class of random walks that start at the source and always move away from it, that we call Drifting Random Walks. A key feature of these algorithms is that they finish in a bounded number of hops with the exact probability distribution, and unlike previous gossip and random walk based approaches, our algorithms do not need warm-up to converge to the desired distribution. We have analyzed these algorithms using a grid and a more realistic concentric rings topologies. Additionally, we have evaluated by simulation the performance of the algorithm, using a concentric rings topology, and different probability distributions. At the end of the simulations, we have obtained that the average error of our sampling algorithm matches that of a centralized pseudorandom simulator.

Affiliated with

Also associated with

No associations

Rating

Distance-based Node Sampling using Drifting 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 Distance-based Node Sampling using Drifting Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distance-based Node Sampling using Drifting Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-677938