[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Unbiased sampling of graphs
From: |
Joshua Madden |
Subject: |
Re: Unbiased sampling of graphs |
Date: |
Tue, 10 Apr 2001 22:01:44 -0700 (Pacific Daylight Time) |
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.
==================================