Title: | Uniform Sampling of Directed Acyclic Graphs |
---|---|
Description: | Uniform sampling of Directed Acyclic Graphs (DAG) using exact enumeration by relating each DAG to a sequence of outpoints (nodes with no incoming edges) and then to a composition of integers as suggested by Kuipers, J. and Moffa, G. (2015) <doi:10.1007/s11222-013-9428-y>. |
Authors: | Markus Kalisch [aut, cre], Manuel Schuerch [ctb] |
Maintainer: | Markus Kalisch <[email protected]> |
License: | GPL (>= 2) |
Version: | 1.0.4 |
Built: | 2024-11-03 06:25:28 UTC |
Source: | CRAN |
Uniform sampling of a labelled directed acyclic graph (DAG) with combinatorial enumeration.
unifDAG (n, weighted=FALSE, wFUN=list(runif, min=0.1, max=1)) unifDAG.approx(n, n.exact=20, weighted=FALSE, wFUN=list(runif,min=0.1,max=1))
unifDAG (n, weighted=FALSE, wFUN=list(runif, min=0.1, max=1)) unifDAG.approx(n, n.exact=20, weighted=FALSE, wFUN=list(runif,min=0.1,max=1))
n |
integer larger than |
weighted |
logical indicating if weights of the edges are
computed according to |
wFUN |
a |
n.exact |
an integer, at least |
A (weighted) random graph with n
nodes is uniformly drawn over
the space of all labelled DAGs with n
nodes.
The main idea of these two methods is to first sample a random
sequence of outpoints, that is, nodes without incoming edges. This
sequence is then used to construct an adjacency matrix, which is
converted to the final DAG. The presented methods differ only in the
approach to find this sequence of outpoints.
The method unifDAG
builds the random sequence of outpoints
based on precomputed enumeration tables.
The method unifDAG.approx
executes unifDAG
up to the
number n.exact
, for larger number of nodes an approximation is
used instead. The default of n.exact = 20
(40
) should
get the approximation within the uniformity limits of a 32 (64) bit
integer sampler. See reference for more details.
A graph object of class graphNEL
.
The main advantage of these algorithms is that they operate on the space of DAGs instead of the space of undirected graphs with an additional phase of orienting the edges. With this approach the unintentional bias towards sparse graphs, for instance occurring when sampling adjacency matrices, can be eliminated.
Markus Kalisch ([email protected]) and Manuel Schuerch.
Jack Kuipers and Giusi Moffa (2015) Uniform random generation of large acyclic digraphs. Statistics and Computing 25(2), 227–242, Springer; doi:10.1007/s11222-013-9428-y
set.seed(123) dag1 <- unifDAG(n=10) dag2 <- unifDAG.approx(n=10, n.exact=5) dag <- unifDAG(n=5) if (require("Rgraphviz")) plot(dag) dag@edgeData ## note the constant weights dag <- unifDAG(n=5,weighted=TRUE) if (require("Rgraphviz")) plot(dag) dag@edgeData ## note the uniform weights between 0.1 and 1 wFUN <- function(m,lB,uB) { runif(m,lB,uB) } dag <- unifDAG(n=5,weighted=TRUE,wFUN=list(wFUN,1,4)) dag@edgeData ## note the uniform weights between 1 and 4
set.seed(123) dag1 <- unifDAG(n=10) dag2 <- unifDAG.approx(n=10, n.exact=5) dag <- unifDAG(n=5) if (require("Rgraphviz")) plot(dag) dag@edgeData ## note the constant weights dag <- unifDAG(n=5,weighted=TRUE) if (require("Rgraphviz")) plot(dag) dag@edgeData ## note the uniform weights between 0.1 and 1 wFUN <- function(m,lB,uB) { runif(m,lB,uB) } dag <- unifDAG(n=5,weighted=TRUE,wFUN=list(wFUN,1,4)) dag@edgeData ## note the uniform weights between 1 and 4