Re: Unbiased sampling of graphs

[Joshua Madden]

quoth Jason Alexander:

> 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).
>     }
> }

Hmm.  Here is something that you might try if it is important that your
sampling be unbiased.

(1) Create a bijective (1-1 and onto) mapping of the natural numbers to
the set (which I will call C_k) of n-node graphs of maximum degree k.

(2) Generate a random number using your favorite random number generator,
in the range [1, |C_k|].  Then use the corresponding graph.

The downside of this method is that I don't immediately know of a clever 
way to create such a mapping, although there might be one.  :(

Here's an easier version of the above, although less elegant:

(1) Create a bijective mapping of numbers to n-node graphs by associating
each possible edge with a bit in a binary number (with n(n-1) bits,
naturally), so the bit is 1 if the edge exists and 0 otherwise;
unfortunately this means that you're not guaranteed that a given number
corresponds to a connected graph (or, for that matter, that it has maximum
degree k).

(2) Generate a random number in the range [2^(n-2) - 1, 2^(n(n-1))].  
Test to see whether the corresponding graph is connected and has max
degree k; if so, you're good, otherwise, chuck it out.  The efficiency of
this method will depend on what proportion of graphs are connected
and have max degree k.  The number of graphs with max degree k is
something like 2^(kn), but I don't have a good idea of how many of those
will be connected.  (My guess is "most of them", but that's pretty vague,
I know.)

The reason why you make the lower edge of the range 2^(n-2) - 1 rather
than something more obvious, like 0, is that any connected graph must have
at least n-1 edges (--> number must have >= n-1 '1' bits), and thus the
smallest number which can correspond to a connected graph is the one in
which the first n-1 digits (that is, digits 0 through n-2) are all
1.  This is basically an easy way to quickly eliminate a small chunk of
the space which is useless.

There are probably a number of clever things which one could do to make
this second version more spiffy (i.e., to eliminate other useless pieces
of the space of n-node graphs) but that should do for a start.

Probably more than you really wanted, but what the heck.  :)  Have fun.

Joshua

address@hidden Per Obscurius...cs.uoregon.edu/~jmadden
    Joshua Madden: Information Scientist, Musician, Philosopher-At-Tall
It's that moment of dawning comprehension that I live for--Bill Watterson
My opinions are too rational and insightful to be those of any organization.



                  ==================================
   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.
                  ==================================