When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.7
URN: urn:nbn:de:0030-drops-83001
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8300/
 Go to the corresponding OASIcs Volume Portal

### On Sampling Edges Almost Uniformly

 pdf-format:

### 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 a new simple algorithm that returns a random edge e in E using \tilde{O}(n/sqrt{eps m}) queries in expectation, such that each edge e is sampled with probability (1 +/- eps)/m. Here, n = |V| is the number of vertices, and m = |E| is the number of edges. 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.

### BibTeX - Entry

@InProceedings{eden_et_al:OASIcs:2018:8300,
author =	{Talya Eden and Will Rosenbaum},
title =	{{On Sampling Edges Almost Uniformly}},
booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
pages =	{7:1--7:9},
series =	{OpenAccess Series in Informatics (OASIcs)},
ISBN =	{978-3-95977-064-4},
ISSN =	{2190-6807},
year =	{2018},
volume =	{61},
editor =	{Raimund Seidel},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},