Shotgun Assembly of Graphs
summary
Defines and studies the problem of reconstructing a large graph from the multiset of its radius-r neighbourhoods (the “shotgun assembly” model). Presents conditions and thresholds for when reconstruction is possible for specific random-graph models (e.g., Erdős–Rényi and random regular graphs) and analyses how neighborhood radius r and graph sparsity affect identifiability and algorithmic reconstruction.
AI-written summary · about
chapters (23)
- 0:00Intro
- 1:00Graph Shotgun Problem
- 3:33DNA Shotgun Sequencing
- 4:50Q1: Deterministic
- 7:10Setup Q2: Randomized Random sequence, entries independent and uniform on a letters.
- 10:06Graph Shotgun Sequencing
- 10:54Random Puzzle Problem
- 13:14A general setup
- 16:23Random jigsaw Puzzle
- 18:55The unique Assembly Question
- 23:32Bounds on puzzle assembly
- 25:04Assembly algorithm
- 28:01Analysis 1
- 29:32Analysis 2
- 31:12Cheat and Punishment
- 32:39Some Random Graph Examples
- 35:00Example: Sparse Erdős-Rényi random graph
- 36:29Example 1b: Less sparse Erdős-Rényi random graph
- 37:18Example 2: Random Regular Graphs
- 38:24Happy and Sad neighborhoods
- 39:01The Upper Bound
- 43:20The lower bound
- 43:37Conclusion
related talks
52mNew Algorithms For The Graph Alignment Problem
29mApplying Randomized Methods for Zonotope Enumeration and...
21mHierarchical Clustering: Finding the awkward reunions
01h 26mStreaming, Sketching and Sufficient Statistics II
35mDistributed Models for Private Analysis of Graph Data
01h 02mGraph Powering
45mCorrelated Stochastic Block Models: Graph Matching And Community Recovery
47mMultiscale Analysis on and of Graphs