Fetching the paper…
Reading the bibliography…
We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise $\epsilon$-close to the uniform distribution, in an \emph{amortized-efficient} fashion.
New fast method for generating discrete random numbers with arbitrary frequency distributions
Alastair J. Walker · 1974
Earlier work this paper cites.
An efficient method for generating discrete random variables with general distributions
Alastair J. Walker · 1977
Earlier work this paper cites.
Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs
Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon · 2004
Earlier work this paper cites.
Tight bounds for testing bipartiteness in general graphs
Tali Kaufman, Michael Krivelevich, and Dana Ron · 2004
Earlier work this paper cites.
Fast generation of discrete random variables
George Marsaglia, Wai Wan Tsang, Jingbo Wang, et al · 2004
Earlier work this paper cites.
On sums of independent random variables with unbounded variance and estimating the average degree in a graph
Uriel Feige · 2006
Earlier work this paper cites.
Sampling from large graphs
Jure Leskovec and Christos Faloutsos · 2006
Earlier work this paper cites.
Approximating average parameters of graphs
Oded Goldreich and Dana Ron · 2008
Earlier work this paper cites.
Walking in facebook: A case study of unbiased sampling of osns
Minas Gjoka, Maciej Kurant, Carter T. Butts, and Athina Markopoulou · 2010
Earlier work this paper cites.
Measuring the mixing time of social graphs
Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim · 2010
Earlier work this paper cites.
Estimating and sampling graphs with multidimensional random walks
Bruno Ribeiro and Don Towsley · 2010
Earlier work this paper cites.
Counting stars and other small subgraphs in sublinear-time
Mira Gonen, Dana Ron, and Yuval Shavitt · 2011
Cited alongside, same era.
Tight bounds for lp samplers, finding duplicates in streams, and related problems
Hossein Jowhari, Mert Sağlam, and Gábor Tardos · 2011
Cited alongside, same era.
Understanding graph sampling algorithms for social network analysis
Tianyi Wang, Yang Chen, Zengbin Zhang, Tianyin Xu, Long Jin, Pan Hui, Beixing Deng, and Xing Li · 2011
Cited alongside, same era.
Talya Eden, Dana Ron, and Will Rosenbaum · 2012
Cited alongside, same era.
Network sampling: From static to streaming graphs
Nesreen K Ahmed, Jennifer Neville, and Ramana Kompella · 2013
Cited alongside, same era.
On sampling edges almost uniformly
Talya Eden and Will Rosenbaum · 2018
Later among the works it cites.
A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling
Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna · 2019
Later among the works it cites.
The arboricity captures the complexity of sampling edges
Talya Eden, Dana Ron, and Will Rosenbaum · 2019
Later among the works it cites.
Sublinear time estimation of degree distribution moments: The arboricity connection
Talya Eden, Dana Ron, and C Seshadhri · 2019
Later among the works it cites.
Faster sublinear approximation of the number of k-cliques in low-arboricity graphs
Talya Eden, Dana Ron, and C Seshadhri · 2020
Closest in time.
On approximating the number of k-cliques in sublinear time
Talya Eden, Dana Ron, and C Seshadhri · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Colin Cooper, Tomasz Radzik, and Yiannis Siantos · 2014
Cited alongside, same era.
On sampling from massive graph streams
Nesreen K Ahmed, Nick Duffield, Theodore L Willke, and Ryan A Rossi · 2017
Cited alongside, same era.
Edge-based wedge sampling to estimate triangle counts in very large graphs
Duru Türkoglu and Ata Turk · 2017
Cited alongside, same era.
Sublinear-time algorithms for counting star subgraphs via edge sampling
Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee · 2018
Cited alongside, same era.
Lower bounds for approximating graph parameters via communication complexity
Talya Eden and Will Rosenbaum · 2018
Cited alongside, same era.
Closest in time.
Sampling arbitrary subgraphs exactly uniformly in sublinear time
Hendrik Fichtenberger, Mingze Gao, and Pan Peng · 2020
Closest in time.
Towards a decomposition-optimal algorithm for counting and sampling arbitrary motifs in sublinear time
Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld · 2021
Closest in time.
Sampling and counting edges via vertex accesses
Jakub Tětek and Mikkel Thorup · 2021
Closest in time.
Approximate triangle counting via sampling and fast matrix multiplication
Jakub Tětek · 2021
Closest in time.