Sampling a large network with a given distribution has been identified as a useful operation to build network overlays. For example, constructing small world network topologies can be done by sampling with a probability that depends on the distance to a given node. In this talk we describe algorithms that can be used by a source node to randomly select a node in a network with probability distributions that depend on their distance. The first algorithm proposed is fully local and uses a uniform sampling service (that could be implemented with, for instance, a gossip-based protocol). This algorithm is of iterative nature and has a parameter r that gives its number of iterations. We prove that the obtained sampling distribution converges to the desired distribution as r grows. The second algorithm presented is fully distributed and uses a new class of random walks, that we call Drifting Random Walks. A key feature of this algorithm is that it finishes in a bounded number of hops with the exact probability distribution. We complement the analyses of the algorithms with simulations.

Joint work with Andrés Sevilla, Alberto Mozo, M. Araceli Lorenzo, Jose Luis López-Presa, and Pilar Manzano

The conference will be conducted in English