Random Walks on Small World Networks

Presented on September 21, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116W.Andreas Galanis is a postdoctoral research fellow in the Department of Computer Science at the University of Oxford, working with Leslie Ann Goldberg. His research interests are in counting and sampling, random graphs and phase transitions.Runtime: 53:56 minutesWe 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 r2. Joint work with Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda