Consensus and mixing on Small World Networks

2016. 12. 08. 16:15
Balázs Gerencsér (Rényi Institute)

We review and put into context the mixing properties of standard Markov chains and variants for Small World Networks based on the model of Newman and Watts.

Consensus problems provide a natural guideline to optimize Markov chains with uniform stationary distribution. We learn what is achievable for reversible Markov chains
when the underlying graph is a Small World Network.

Without the reversibility condition comes additional flexibility but also complexity. We show an example where mixing turns out to be substantially faster, confirming
that it is an area worth addition investigation.

Furthermore, the cutoff phenomenon of mixing for this setup is demonstrated.