Influencing Cascades: An Algorithmic View
Talkat Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp · 2022-08-29..09-02
summary
Models adoption as asynchronous logit (Glauber) dynamics with inverse-noise beta and a potential function; the main quantitative claim ties the worst-case hitting time to a graph-dependent barrier called the tilted cut width: hitting time grows like exp(beta · barrier). Consequences: bounded-degree expanders (and many power‑law/random‑regular models) force exponentially long switches to the superior action, while finite‑range grids give O(1) (fast) convergence; small‑world links cross a threshold at R ≈ D.
AI-written summary · about
chapters (21)
- 0:00Introduction to speaker
- 1:23Network diffusion overview
- 2:06Modeling diffusion of behavior
- 4:56Game theory on networks
- 7:49Equilibrium and potential games
- 9:42Impact of noise and nucleation
- 12:08Noisy best response dynamics
- 15:02Refining equilibrium selection
- 17:10Hitting time and network structure
- 20:08Contrasting networks and epidemics
- 22:51Graph theoretic properties
- 26:06Logit dynamics and cohesiveness
- 29:43Potential function and convergence
- 32:34Expander graph behavior
- 35:52Mixing time and bottlenecks
- 39:02Random regular graph analysis
- 42:08Low dimensional grid networks
- 46:12Small world network models
- 49:08Mixed community regimes
- 51:59Coordination vs contagion
- 53:47Strategic seeding and future work