Re: Unbiased sampling of graphs

[Joshua Madden]

Chris:

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

Yes, the minimum connected graph (otherwise known as a tree) of n nodes must 
have n-1 edges.  However, "working up from there" is problematical; see below.

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

A nice idea, but you can't generate all connected graphs by just adding edges 
to 
the chain.  That is, the chain is not a subgraph of all other connected graphs. 
 
The star is perhaps the most obvious counterexample; a complete binary tree is 
another.  If you are willing to break links as well as adding them 
(necessitating either a clever way of doing so such that the graph remains 
connected--see the last paragraph below for one idea--or repeated testing for 
connectedness) then you should be able to do it.  However...

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

...the other problem with this scheme is that, if I understand Jason's original 
question, he's trying to choose a *random* (I'm assuming a uniform 
distribution) 
graph from the set of all connected max-k-degree graphs.  You are trying to 
exhaustively search the space of all such graphs, which is not the same 
problem. 
 If you "choose" graphs in the order in which they are encountered in this 
search, the sequence of chosen graphs will be highly nonrandom.

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

An interesting question, to be sure...another related question being what the 
diameter of that "metagraph" would be (i.e., what is the longest distance 
between any two graphs in the metagraph).  I'd bet that the answer to your 
question ('is the metagraph connected?') is 'yes', assuming that the operation 
of moving from one graph to another is the addition or removal of an edge.  You 
can always safely add an edge.  To remove an edge, you just have to identify a 
cycle in the graph; any one of its edges may be removed without disconnecting 
the graph.  I'm pretty sure that playing with adding edges and then removing an 
edge from the resulting cycle should allow you to get from any tree (minimal 
connected graph) to any other, and if you can do that, you're done (any 
connected graph must have *some* tree as a subgraph).

Can you tell I haven't had the opportunity to play with graph theory recently?  
:)

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