unifDAG: Uniform Sampling of Directed Acyclic Graphs (DAG)
In unifDAG: Uniform Sampling of Directed Acyclic Graphs

Description Usage Arguments Details Value Note Author(s) References Examples

View source: R/unifDAG.R

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

1 2	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 `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.

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 (kalisch@stat.math.ethz.ch) and Manuel Schuerch.

Jack Kuipers and Giusi 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

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

Loading required package: Rgraphviz
Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: 'BiocGenerics'

The following objects are masked from 'package:parallel':

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from 'package:stats':

    IQR, mad, sd, var, xtabs

The following objects are masked from 'package:base':

    Filter, Find, Map, Position, Reduce, anyDuplicated, append,
    as.data.frame, cbind, colMeans, colSums, colnames, do.call,
    duplicated, eval, evalq, get, grep, grepl, intersect, is.unsorted,
    lapply, lengths, mapply, match, mget, order, paste, pmax, pmax.int,
    pmin, pmin.int, rank, rbind, rowMeans, rowSums, rownames, sapply,
    setdiff, sort, table, tapply, union, unique, unsplit, which,
    which.max, which.min

Loading required package: grid
An object of class "attrData"
Slot "data":
$`1|2`
$`1|2`$weight
[1] 1


$`1|3`
$`1|3`$weight
[1] 1


$`4|3`
$`4|3`$weight
[1] 1


$`4|5`
$`4|5`$weight
[1] 1



Slot "defaults":
$weight
[1] 1


An object of class "attrData"
Slot "data":
$`1|3`
$`1|3`$weight
[1] 0.8865549


$`1|4`
$`1|4`$weight
[1] 0.2362044


$`2|1`
$`2|1`$weight
[1] 0.9796452


$`2|4`
$`2|4`$weight
[1] 0.3536305


$`4|3`
$`4|3`$weight
[1] 0.4311064


$`5|1`
$`5|1`$weight
[1] 0.7000346



Slot "defaults":
$weight
[1] 1


An object of class "attrData"
Slot "data":
$`1|4`
$`1|4`$weight
[1] 1.132441


$`2|1`
$`2|1`$weight
[1] 3.326223


$`3|1`
$`3|1`$weight
[1] 2.130449


$`3|2`
$`3|2`$weight
[1] 2.093233


$`3|4`
$`3|4`$weight
[1] 3.710203


$`3|5`
$`3|5`$weight
[1] 1.126324


$`5|1`
$`5|1`$weight
[1] 3.596502



Slot "defaults":
$weight
[1] 1