5
$\begingroup$

I'm wanting to generate random connected directed acyclic graphs, and am wondering if there is a way of populating an adjacency matrix in R which would represent the aforementioned.

Something similar to this would be nice (that is done with Mathematica): https://mathematica.stackexchange.com/q/608

Thanks.

$\endgroup$
  • $\begingroup$ Is the definition of random taken on the other page the one you want? That is, both the number of vertices and number if edges are fixed at the outset and a DAG with these properties is generated? Or do you want a random number of edges more akin to an Erdos-Renyi model? Also, you mention connected DAGs here but not there. Can you clarify? $\endgroup$ – cardinal May 8 '12 at 18:17
  • 1
    $\begingroup$ The more control the better. That is, if I can control the number of vertices and edges, it would be nice. The graph needs to be connected. $\endgroup$ – Erich Peterson May 8 '12 at 18:32
  • $\begingroup$ Cross-posted as math.stackexchange.com/questions/142021 (the real question of interest here, I think.) $\endgroup$ – Emre May 8 '12 at 19:37
5
$\begingroup$

The question asks for a random lower triangular binary matrix which represents the edges. Here is one way, with the number of vertices (as v) and number of edges stipulated and edges chosen independently and uniformly among the available ones:

DAG.random <- function(v, nedges=1) {
    edges.max <- v*(v-1)/2
    # Assert length(v)==1 && 1 <= v
    # Assert 0 <= nedges <= edges.max
    index.edges <- lapply(list(1:(v-1)), function(k) rep(k*(k+1)/2, v-k)) 
    index.edges <- index.edges[[1]] + 1:edges.max
    graph.adjacency <- matrix(0, ncol=v, nrow=v)
    graph.adjacency[sample(index.edges, nedges)] <- 1
    graph.adjacency
}

This solution uses R's simultaneous use of matrix and array indexing. index.edges computes a list of the array indexes corresponding to the lower triangular elements of graph.adjacency. (This is done by finding the gaps in these indexes left by the diagonal and upper triangular entries and shifting the sequence c(1,2,3,...) by those gaps.) Sampling the indexes (without replacement) does the trick.

Edit

One ad-hoc way to create connected DAGs is by adjoining a connected "skeleton" to the random DAG in a way that keeps it acyclic. For instance, we can create a linear skeleton post hoc:

set.seed(17)
n <- 6; e <- 4
a <- DAG.random(n, e)
a[seq(from=2, by=n+1, length.out=n-1)] <- 1

Here's the adjacency matrix:

> a
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    0    0    0    0    0
[2,]    1    0    0    0    0    0
[3,]    0    1    0    0    0    0
[4,]    1    1    1    0    0    0
[5,]    0    0    0    1    0    0
[6,]    0    0    0    1    1    0
$\endgroup$
  • 2
    $\begingroup$ While I was writing this reply, the question was changed to require connected graphs. This raises the issue of what the distribution ought to be: should every connected DAG be generated equiprobably? Or should each isomorphism class have the same probability? Or something else? Some ad hoc solutions are evident: e.g., force 1's into the subdiagonal of the adjacency matrix to create a linear chain and then generate a few more random edges; or generate random marked trees and orient them appropriately, then add a few more random edges; etc. $\endgroup$ – whuber May 8 '12 at 18:48
  • $\begingroup$ I am looking for an ad-hoc solution for sure. I am simply wanting to experiment with an algorithm I have created, and need input data. I don't have any experience with graph theory or much experience with R. Do you have code which could make the connected constraint be forced? $\endgroup$ – Erich Peterson May 8 '12 at 18:56
  • 2
    $\begingroup$ One-liner: DAG.random <- function(v, e) { A <- matrix(0,v,v); A[lower.tri(A)] <- sample( c(rep(1,e),rep(0,v*(v-1)/2-e) ) ); A } $\endgroup$ – cardinal May 8 '12 at 19:02
  • $\begingroup$ p.s. isn't that sort of cheating w.r.t a "one-liner" when you use all of those semi-colons ;) $\endgroup$ – Macro May 8 '12 at 19:05
  • $\begingroup$ @Macro: Yes. Sort of. And, it spilled over into two lines in the display. So ugly. :) $\endgroup$ – cardinal May 8 '12 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.