The k-Cap Process on Geometric Random Graphs

ACO Student Seminar
Friday, February 11, 2022 - 1:00pm for 1 hour (actually 50 minutes)
Skiles 254
Mirabel Reid – Georgia Tech CS –
Abhishek Dhawan

The k-cap (or k-winners-take-all) process on a graph works as follows: in each
iteration, exactly k vertices of the graph are in the cap (i.e., winners); the next round
winners are the vertices that have the highest total degree to the current winners,
with ties broken randomly. This natural process is a simple model of firing activity
in the brain. We study its convergence on geometric random graphs revealing rather
surprising behavior