Re: Unbiased sampling of graphs

[Chris Langton]

   Hmmm - well, the minimal connected graph for N nodes is a ring with K=1
for each node. This minimal graph will be a sub-graph of any other connected
graph you generate....so - why not start from this minimal ring, and grow 
edges from each node (up to edges=K per node) cannonically from there? It 
doesn't seem as though you need to randomly sample the space of all N-node, 
e <= K graphs....plus, I think you only have to explore the non-repeats 
with respect to rotations of node labeling around such a ring....are node
labels important? or are you only looking for topologically distinct 
graphs regardless of node labels?

   Chris Langton



--- Jason Alexander <address@hidden> wrote:
> 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.
>                   ==================================
> 
> 


__________________________________________________
Do You Yahoo!?
Get email at your own domain with Yahoo! Mail. 
http://personal.mail.yahoo.com/


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