Sublinear Time Local-Access Random Generators

on YouTube ↗41m

" summary

Generates huge random graphs on the fly and answers vertex-pair, next-neighbor, all-neighbor and random-neighbor queries while spending polylogarithmic time per query and only storing the decided ones (ones explicit, zeros implicit); supports G(n,p), sparse degree-bounded graphs via port-matching for sparse graphs, preferential-attachment next-neighbor queries with polylog work, stochastic block sampling via multivariate hypergeometric steps, and Kleinberg small-world edges. Key tools are interval-summable CDFs and skip-sampling hypergeometric runs plus bucketing and rejection sampling; resulting samples are ε-close in distribution and consistent across queries.

AI-written summary · about

" chapters (17)

1. 0:00Start
2. 0:18How to generate?
3. 6:09Implementations of Barabasi-Albert Preferential Attachment Graphs Even-Levi-Medina-Rosen 2017
4. 13:17Possible queries
5. 14:29Today's Goal: Graph models supporting typical graph queries
6. 14:56All-neighbor queries for sparse G(n,p): Implementation adapted from [NNO7]
7. 20:01The case of directed graphs
8. 22:06Undirected graphs
9. 22:56Implementation of next neighbor queries: (assume no adjacency queries)
10. 24:41Skip-sampling for next-neighbor queries
11. 29:12Random-Neighbor Query: output random neighbor of i
12. 29:58Implementation of Random-Neighbor queries via Bucketing
13. 31:25Random Neighbors with rejection sampling
14. 34:20How to fill a bucket?
15. 37:50Stochastic Block Model
16. 38:13Another use: Partially Sampling a Random Walk
17. 39:29Small-World Model [Kleinberg]