University of Cambridge > Talks.cam > Probability > Mixing time for the non-babktracking random walk on random graphs with communities

Mixing time for the non-babktracking random walk on random graphs with communities

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Perla Sousi.

The mixing time of random walks on finite connected graphs is tightly related to the existence of bottlenecks in the graph: intuitively, the harder it is for the walk to escape some sets, the larger its mixing time. Moreover, strong bottlenecks usually prevent cutoff, which describes an abrupt convergence to equilibrium. In this talk, we will be interested in the mixing behavior of the non-backtracking random walk (NBRW) on random graphs with given degrees and with a two-community structure. Such graphs have a bottleneck, whose strength can be measured by the fraction of edges that go from one community to the other. Under some degree assumptions, we will show that, as long as this fraction decays more slowly than 1/log(N), where N is the size of the graph, the NBRW has cutoff, and the distance profile can be very precisely described. On the other hand, if the fraction decays faster than 1/log(N), then there is no cutoff.

This talk is part of the Probability series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity