Sampling regular graphs and a peer-to-peer network
January 31, 2005 11:50 AM to 12:35 PM
Speakers:
Greenhill, Catherine
|
 |
Abstract: |
The problem of generating random regular graphs has been well studied.
Here the number of vertices $n$ is fixed and the aim is to efficiently
sample (uniformly or approximately uniformly) from the set of all
$d$-regular graphs on $n$ vertices, for some given $d=d(n)$. Some of
the methods used for this include the configurations model, Markov
chains and random graph processes.
A very natural Markov chain for regular graphs is one which moves by
``switching'' two edges of the graph. This chain is known to be
rapidly mixing for bipartite graphs, and my coauthors and I recently
proved that it is rapidly mixing for all graphs. We also defined a
related Markov chain for $d$-regular graphs on a varying number of
vertices, when $d$ is even. The Markov chain is a model for a certain
peer-to-peer network, and is designed so that its stationary
distribution is uniform when restricted to graphs with a fixed number
of vertices. We found that, under certain natural assumptions, our
Markov chain converges rapidly to its stationary distribution. This
supports a claim made by the designers of the peer-to-peer network:
namely, that the network quickly starts to behave like a random
regular graph, and hence has good properties (such as high
connectivity and low diameter) with high probability.
This talk is on joint work with Colin Cooper and Martin Dyer. |
|
|
