Rapid Mixing of Local Graph Dynamics

arXiv1705.03427MaRDI QIDQ6286471FDOQ6286471

Authors: Laurent Massoulié, Rémi Varloot 

Publication date: 9 May 2017

Abstract: Graph dynamics arise naturally in many contexts. For instance in peer-to-peer networks, a participating peer may replace an existing connection with one neighbour by a new connection with a neighbour's neighbour. Several such local rewiring rules have been proposed to ensure that peer-to-peer networks achieve good connectivity properties (e.g. high expansion) in equilibrium. However it has remained an open question whether there existed such rules that also led to fast convergence to equilibrium. In this work we provide an affirmative answer: We exhibit a local rewiring rule that converges to equilibrium after each participating node has undergone only a number of rewirings that is poly-logarithmic in the system size. The proof involves consideration of the whole isoperimetric profile of the graph, and may be of independent interest.

This page was built for publication: Rapid Mixing of Local Graph Dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286471)