Re: Unbiased sampling of graphs

[Chris Langton]

Darn those hidden default assumptions!

   I had digraphs in mind when I wrote:

>    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? 


  I was clearly thinking directed graphs here, with K being the outdegree 
of each node...in which case I think what I said is right: the minimum 
connected graph (fewest number of edges) is the ring, no? I don't know
why I assumed digraphs....

   "Howeva"....might not a similar approach work for undirected graphs?

  I think you have to have N-1 edges for the minimum connected graph 
of N nodes: could be a chain, or a star as Chris Landauer points out,
and the variations between chain and star. But the point is, I'd bet 
that you could still start with the minimal connected graphs of N nodes, 
those with the smallest overall K's per node, and then work up from 
there, minimizing time spent considering or generating unconnected graphs.

  For instance, I think that the linear chain admits of the smallest 
overall distribution of K/node of the various minimal connected-graphs 
with N-1 edges. In that case, there are N-2 nodes with K=2 and 2 nodes 
with K=1. The star has N-1 nodes with K=1 but one node has K=N-1, 
while the ring - which has N edges, and is therefore not minimal - 
has N nodes with K=2. 

  So - I'd think that you could start out with the linear chain of 
N nodes and N-1 edges, and then cannonically tweak the K's per 
node, building the possible connected graphs up from there for each 
new combination of K's. 

  I think something like this will minimize the time wasted on 
unconnected graphs: you search outwards from connected graphs, 
preserving the property of connectedness, and you stop any one 
search direction the first time you generate an unconnected graph, 
so you don't waste time on variants of that. If a variant of that
unconnected graph would be another connected graph, you should reach
it by following a different search path from the same, or another, 
minimal connected graph.

  Is that last statement true, I wonder?  I'd like to see the structure 
of the "graph" of connected graphs. Is it itself connected? I.e., are 
all the connected graphs reachable from one another under a well-defined
graph-tweaking operation defining the edges between them?


   Chris
  


  
 


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