Re: Unbiased sampling of graphs

[Jason Alexander]

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

This is an attractive strategy if the space studied is small enough to make
constructing all of the connected graphs feasible.  Unfortunately, I'll be
looking at connected graphs with between 10 and 100+ nodes, where K can vary
(and the labels on the nodes are meaningful and can vary as well), so the
random sampling approach is the only feasible one.

Joshua Madden wrote:
> 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).

So the idea here is to identify a set of operations that preserve
connectivity (adding an edge, removing an edge from a cycle, etc.), and
then, beginning with some initial connected seed (a chain, a star, a tree,
etc.), apply the operations to randomly selected nodes (or cycles,...) a
randomly chosen number of times to produce a final connected graph?  I think
this approach won't be unbiased, though.  I would think that some graphs
would be much easier to derive from a given starting seed than others, in
that there would be multiple construction paths leading to the same outcome.

What about this approach?

while (not connected) {
  N = nil; M = nil;
  while (N==nil or M == nil) {
    if (N == nil)

      let N = randomly chosen node.
      if N has >K edges, then N=nil.
    }
    if (M == nil) {
      let M = randomly chosen node.
      if M has >K edges, then M=nil.
    }
  }
  Connect N and M.
}

Let E = number of edges in graph
Let Z = maximum number of edges in a graph on N nodes w/ degree <K
Let R = random number between 0 and Z-E.

Add R more edges to the graph, preserving degree <K.


We're growing a random graph subject to the constraint that each node has
degree <K and
we stop the while loop when the graph is connected.  Once we start the
construction, we clearly shut off certain graphs as outcomes, but since each
path through the construction process is equally likely, we uniformly
randomly sample from all of the connected graphs on N nodes with <K edges
per node obtainable by that approach.  Clearly some connected graphs we want
to consider can't be produced by this approach, which is what the last bit
is for.

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