Re: Unbiased sampling of graphs

[Chris Langton]

--- Joshua Madden <address@hidden> wrote:

> > Chris Langton wrote:
> >
> >  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...
> 

That's not what I mean by tweak...not that the chain has to be a subgraph,
but that you tweak the chain's "K-spectrum" (N-2 nodes with K=2 and 2 nodes
with K=1) through the different ways to have Sum(K) = 2(N-1). So you turn 
the chain into the star by picking 1 node to add 1 to each time you take
1 away from one of the K=2 nodes, until you have N-1 nodes with K=1 and
1 node with K=N. Similar tweaking will lead to other minimal graphs.
Then you'd move up to Sum(K) = 2N, etc....

   However.....

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


  This is, of course, the more serious problem with this scheme - you don't 
want to have to generate the whole set in advance and then draw randomly from 
it - too big a task. And, as you point out, the canonical order of generation
would be far from representative of a random draw on the full distribution.


  So...back to the graphing board....

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

   I agree - isn't there always this (dumb) path?: Start from any connected
graph, and add edges until you hit the fully connected graph (all nodes
connected to all other nodes) and then selectively remove edges until
you hit the target connected graph.

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

 yo tambien!

  Chris

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



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