sampling regular graphs and a peer-to-peer network
We consider a simple Markov chain for d -regular graphs on n vertices, and show that the mixing time of this Markov chain is bounded above by a polynomial in n and d. A related Markov chain for d -regular graphs on a varying number of vertices is introduced, for even degree d. We use this to model a certain peer-to-peer network structure. We prove that the related chain has mixing time which is bounded by a polynomial in N , the expected number of vertices, under reasonable assumptions about the arrival and departure process.
sampling graph peer-to-peer networks timing polynomial use model structure process