pcalg (version 2.2-3)

Uniform DAG Sampling: Sample DAG uniformly

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

An 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

If TRUE, weights of the edges are computed according to wFUN.

wFUN

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

n.exact

An integer at least as large as 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

Value

• A graph object of class 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

http://arxiv.org/pdf/1202.6590.pdf{Uniform random generation of large acyclic digraphs}, Jack Kuipers and Guisi Moffa, Statistics and Computing, 2013, Springer.

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(20)
dag2 <- unifDAG.approx(20,15)

dag <- unifDAG(5)
plot(dag)
dag@edgeData   ## note the constant weights
 
dag <- unifDAG(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(5,weighted=TRUE,wFUN=list(wFUN,1,4))
dag@edgeData   ## note the uniform weights between 1 and 4