Re: Uniform random sampling of graphs

[Jason Alexander]

Thanks to everyone who has helped me out with this problem.  The last
algorithm I posted produced a biased sample.  Here's one that (cross
fingers) should work.

The problem: How to draw a uniform random sample from the set of connected
graphs w/ degree <=K.

Solution (?): We'll reduce the problem to drawing a uniform random sample
from the set of connected graphs w/ degree <=K having exactly E edges.  That
problem can be solved by generating a random graph w/ E edges and degree <=K
and randomly rewiring the unconnected nodes (if there are any) to obtain a
connected graph.

Since each edge we add to the graph increases the degree of 2 nodes by 1, we
can place an upper limit on the total number of possible edges in the graph:
|_ NK/2_|.  Call this number M.  We can similarly place a lower limit on how
many edges we need to have a connected graph (it's a straight line).  Call
this number M'=N-1.

We then need to calculate how many possible connected graphs there are on N
nodes with degree <=K having E edges, for each E between M' and M.  This
should be a fairly straightforward combinatorial calculation.  I would think
that it should be solvable using recurrence relations, in which case it
would be doable by a computer (so you could shove all of this overhead into
a single function at the start of the modeling run).

Once we've obtained the above information, use it to construct a probability
distribution over the number of edges for connected graphs w/ degree <= K.
Choose, using that distribution, a particular number of edges, then generate
a compatible graph as described previously.

Does this work?

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