Unbiased sampling of graphs

[Jason Alexander]

Hello,

I need to generate a unbiased random sample from the set of connected graphs
having N nodes and no more than K edges per node.  One no-brainer way of
sampling would be:

while (true) {
  generate a graph w/ N nodes and <= K edges per node.
  if it's connected, break; otherwise, scrap graph and try again.
}

I would think there should be a better way.  I'm not convinced that any of
the methods I've thought of, though, sample the space without bias.  For
example, one might try:

while (true) {
  generate a graph w/ N nodes and <= K edges per node.
  if connected, break
  else {
    while (unconnected nodes remain) {
       let X be a randomly chosen unconnected node.
       choose another node at random; if that node has < K edges, link it to
node X; otherwise,
       choose another node at random (keep doing this until you get one with
<K edges, then link to X).
    }
}

This seems plausible, but I'm skeptical.

Any thoughts or references would be appreciated.

Cheers,

Jason

--
Jason Alexander
Department of Philosophy
University of California, San Diego
La Jolla, CA 92093-0119
858-822-4910 (office)
858-534-8566 (fax)



                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================