On Sampling Edges Almost Uniformly

Abstract

We consider the problem of sampling an edge almost uniformly from an unknown graph, $G=(V,E)$. Access to the graph is provided via queries of the following types: (1) uniform vertex queries, (2) degree queries, and (3) neighbor queries. We describe an algorithm that returns a random edge $e\in E$ using $\tilde{O}(n/\sqrt{\epsilon m})$ queries in expectation, where $n=|V|$ is the number of vertices, and $m=|E|$ is the number of edges, such that each edge $e$ is sampled with probability $(1\pm \epsilon )/m$. We prove that our algorithm is optimal in the sense that any algorithm that samples an edge from an almost-uniform distribution must perform $\Omega (n/\sqrt{m})$ queries.