Algorithms & Randomness Center (ARC)
Andreas Galanis (Oxford)
Thursday, September 21, 2017
Klaus 1116 West - 11:00 am
Title: Random Walks on Small World Networks
Abstract:
We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d>1 is added as a "long-range" edge with probability proportional to d^(-r), where r>=0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the decentralised routing time is O((logn)^2) when r=2 and n^Ω(1) when r\neq 2. Here, we prove that the random walk also undergoes a phase transition at r=2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(logn) for r<2, O((logn)^4) for r=2 and n^{Ω(1)} for r>2.
Joint work with Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda.
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu