OASIcs.SOSA.2018.7.pdf
- Filesize: 468 kB
- 9 pages
Document
On Sampling Edges Almost Uniformly
Authors
-
Part of:
Volume:
1st Symposium on Simplicity in Algorithms (SOSA 2018)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-01-05
Cite As Get BibTex
Talya Eden and Will Rosenbaum. On Sampling Edges Almost Uniformly. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 7:1-7:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.7
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.
Subject Classification
Keywords
- Sublinear Algorithms
- Graph Algorithms
- Sampling Edges
- Query Complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear time. SIAM J. Comput., 46(5):1603-1646, 2017. URL: http://dx.doi.org/10.1137/15M1054389.
- Talya Eden, Dana Ron, and C. Seshadhri. Sublinear time estimation of degree distribution moments: The degeneracy connection. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 7:1-7:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.7.
- Talya Eden and Will Rosenbaum. On sampling edges almost uniformly. CoRR, abs/1706.09748, 2017. URL: http://arxiv.org/abs/1706.09748.
- Uriel Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput., 35(4):964-984, 2006. URL: http://dx.doi.org/10.1137/S0097539704447304.
- Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 406-415. ACM, 1997. URL: http://dx.doi.org/10.1145/258533.258627.
- Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Struct. Algorithms, 32(4):473-493, 2008. URL: http://dx.doi.org/10.1002/rsa.20203.
- Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput., 33(6):1441-1483, 2004. URL: http://dx.doi.org/10.1137/S0097539703436424.
- Michal Parnas and Dana Ron. Testing the diameter of graphs. Random Struct. Algorithms, 20(2):165-183, 2002. URL: http://dx.doi.org/10.1002/rsa.10013.