Matriz de adyacencia generada aleatoriamente en R

Question

Quiero generar grafos acíclicos dirigidos conectados al azar, y me pregunto si hay una forma de rellenar una matriz de adyacencia en R que represente lo anterior.

Algo similar a esto estaría bien (que se haga con Mathematica): https://mathematica.stackexchange.com/q/608

Gracias.

Answer 1

La pregunta pide una matriz binaria triangular inferior aleatoria que represente las aristas. Aquí hay una forma, con el número de vértices (como v ) y número de aristas estipuladas y aristas elegidas de forma independiente y uniforme entre las disponibles:

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
}

Esta solución utiliza el uso simultáneo de R de la indexación de matrices y arrays. index.edges calcula una lista de los matriz índices correspondientes a los elementos triangulares inferiores de graph.adjacency . (Esto se hace encontrando los huecos en estos índices dejados por las entradas diagonales y triangulares superiores y desplazando la secuencia c(1,2,3,...) por esas lagunas). El muestreo de los índices (sin reemplazo) es suficiente.

Editar

Una ad-hoc La forma de crear DAGs conectados es unir un "esqueleto" conectado al DAG aleatorio de forma que lo mantenga acíclico. Por ejemplo, podemos crear un esqueleto lineal 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

Aquí está la matriz de adyacencia:

> 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