Marrying Graph Convergence and Cascade Models
Talkat Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp · 2022-08-29..09-02·
summary
Shows that for bounded‑degree or large‑set expander graph sequences the critical probability converges and any giant component is unique and has a relative size that converges; proves a constant‑query local estimator (a few BFS‑style simulations from uniform random nodes) gives a 1–ε approximation of that limit; uses sprinkling + Menger paths to merge many constant‑size clusters and Efron‑Stein/variance control (instead of bounded‑differences) for the directed percolation bow‑tie result and equality of directed/undirected thresholds.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:10Personal Story
- 5:06The Epidemic Process
- 6:17Directed Percolation
- 8:23The Critical Probability
- 11:01Converging Sequence
- 22:47The Household Model
- 24:37The Directed Percolation
- 38:49Concentration Bonds
- 40:51Menger's Theorem
- 53:01Coupling the Director to the Undirected
related talks
01h 23mProperty Testing for Graphs
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
47mMultiscale Analysis on and of Graphs
27mSampling Algorithms to Count Frequent Patterns in Graphs
39mBroadcasting on Directed Acyclic Graphs
23mTowards General and Tight Hardness Results for Graph Problems
46mDistributed Graph Techniques in the MPC Model
35mSuperlinear Lower Bounds for Multipass Graph Processing