A Framework for Imperfectly Observed Networks
summary
Model assumes a finite edge-weighted graph where each potential edge generates a Poisson interaction process with rate equal to its weight, and the data is the multigraph seen when one observe[s] for time T. Questions: estimate connectivity, community density, max-weight matching, or first-passage-percolation (FPP) times from those counts. Results: regimes T <<1, T ~1, T ~log n matter; concentration bounds for hitting-times of substructures; naive edge-rate estimator fails in dense regime but a twice-seen-edge rule works for sparse graphs; universal fast estimation of FPP is impossible without extra assumptions. Tools: coupon-collector, concentration inequalities, coupling and combinatorial certification ideas (Menger-type arguments).
AI-written summary · about
chapters (8)
- 0:00Start
- 2:34Collaboration Networks
- 6:01Imperfectly Observed Network Problem
- 15:21Connectivity Problem
- 27:04The Unseen Species Problem
- 29:10Community Structure
- 36:46Levels of Randomness
- 40:52Why People Become Bayesian
related talks
01h 21mAn Overview on Data Streams Algorithms
59mNetwork Unreliability in Sub-quadratic Time
39mModel Counting Meets Distinct Estimation
01h 04mSampling Big Ideas in Sublinear Algorithms
01h 26mStreaming, Sketching and Sufficient Statistics II
17mReasoning about Network Traffic Load Property at Production Scale
32mActive Fault Finding in Networks
15mFormal Methods for Network Performance Analysis