Distributed Uniform Sampling in Real- World Networks
Asad Awan, Ronaldo Alves Ferreira, Suresh Jagannathan, Ananth Y. Grama · Purdue e-Pubs (Purdue University System) · 2004
Uniform sampling in networks is at the core of a wide variety of randomized algorithms.Random sampling can be peJjonned by modeling the system as a graph with associated transition probabilities and defining a corresponding Markov chain (Me).A random walk ofprescribed minimum length, pelfonned on this graph, yields a stationary dim'ibution, and the corresponding random sample.This sample, however, is not uniform when network nodes have a nonuniform degree distribution.This poses a significant practical challenge since typical large scale, real-world, unstructured networks tend to have non-uniform degree distributions, e.g.. power-law degree distribution iJl unstructured peer-to-peer networks.In this paper we present a distributed algorithm that enables efficient un(form sampling in large real-world networks.Specifically, we prescribe necessary conditions for uniform sampling in such networks and present distributed algorithms that satisfy these requiremems.We empirically evaluate the peJjormance of our algorithm in comparison to known algorithms.We also quamijy. in context of the presented algorithms, the peJjormance parameters in uniform sampling that are 1110St relevant in a distributed setting -computational complexit..-, number of network messages, and the uniformity of the sampling.Detailed experimental results are used to support our claims relating to pelformance improvements of our algorithm.