Locally Convergent Graphs
Talkat Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp · 2022-08-29..09-02·
summary
Sequence convergence uses the rooted-ball metric: pick a vertex uniformly, record the radius-R ball, and set distance = 1/(R+1) where balls are isomorphic; limits are probability measures on rooted, locally finite graphs. For deterministic sequences this equals Benjamini–Schramm convergence; for random graphs require convergence in probability or almost surely to get concentration (expectation alone is too weak). Limits obey unimodularity (neighbor reweighting / mass transport), which controls random-walk and percolation behavior; counterexamples show identical local limits can have different cuts or giant-component sizes, and existence of sequences for every unimodular law remains open.
AI-written summary · about
chapters (9)
- 0:00Introduction to sparse graphs
- 1:15Defining local convergence
- 4:36Challenges in sparse limits
- 10:44Formalizing graph metrics
- 26:34Convergence of random graphs
- 36:46Applications and motivation
- 51:02Random graph sequences
- 1:09:24Probability and convergence
- 1:18:30Unimodularity and conclusion
related talks
47mMultiscale Analysis on and of Graphs
48mDistributed Learning Dynamics Convergence in Routing Games
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
01h 05mRandom Walks on Simplicial Complexes for Exploring Networks
49mAn Algorithmic Theory of Brain Networks
26mOn the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...
01h 23mProperty Testing for Graphs
29mAmplifying Contextual Distance in Higher-Order Languages, using the Law of Large Numbers