pcalg (version 2.4-3)

unifDAG: Uniform Sampling of Directed Acyclic Graphs (DAG)

Description

Uniform sampling of a labelled directed acyclic graph (DAG) with combinatorial enumeration.

Usage

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

Arguments

n

integer larger than 1, indicating the number of nodes in the DAG. unifDAG can only be used for n up to 100. For larger n, use unifDAG.approx.

weighted

logical indicating if weights of the edges are computed according to wFUN.

wFUN

a function for computing the weights of the edges in the DAG. It takes as first argument a number of edges m for which it returns a vector of length m containing the weights. Alternatively, it could be a list consisting of the function in the first entry and of further arguments of the function in the additional entries. The default (only if weighted is true)) is a uniform weight between 0.1 and 1. See the examples.

n.exact

an integer, at least n and between 2 and 100, denoting the number of nodes up to which the exact method is used, followed by an approximation for larger numbers up to n. See details on the quality of the approximation.

Value

graphNEL.

Details

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.

References

Jack Kuipers and Guisi Moffa (2015) Uniform random generation of large acyclic digraphs. Statistics and Computing 25(2), 227--242, Springer; http://dx.doi.org/10.1007/s11222-013-9428-y

See Also

randDAG for generating different random DAGs, each intentionally shifted towards certain properties; randomDAG a limited and soon deprecated version of randDAG where the output is topologically sorted; rmvDAG for generating multivariate data according to a DAG.

Examples

# require("Rgraphviz")
set.seed(123)
dag1 <- unifDAG(n=10)
dag2 <- unifDAG.approx(n=10, n.exact=5)

dag <- unifDAG(n=5)
plot(dag)
dag@edgeData   ## note the constant weights

dag <- unifDAG(n=5,weighted=TRUE)
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