randDAG: Random DAG Generation

Description

Generating random directed acyclic graphs (DAGs) with fixed expected number of neighbours. Several different methods are provided, each intentionally biased towards certain properties. The methods are based on the analogue functions in the igraph package.

Usage

randDAG(n, d, method="er", par1=NULL, par2=NULL, 
        DAG=TRUE, weighted=TRUE, wFUN=list(runif, min=0.1, max=1))

Arguments

An integer larger than 2, indicating the number of nodes in the DAG.

A positive number, corresponding to the expected number of neighbours per node, more precisely the expected sum of the in- and out-degree.

method

A string, specifying the method used for generating the random graph. See details below.

par1

Possible additional argument, dependent on the method. See details below.

par2

Possible additional argument, dependent on the method. See details below.

DAG

If TRUE, labelled graph is directed to a labelled acyclic graph.

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

Value

A graph object of class graphNEL.

Details

A (weighted) random graph with n nodes and expected number of neighbours d is constructed. For DAG=TRUE, the graph is oriented to a DAG. There are eight different random graph models provided, each selectable through the parameters method, par1 and par2. The argument method, of format string, can take one of the following values:

regular:Graph where every node has exactlydincident edges.

watts: Watts-Strogatz graph that interpolates between the regular (par1->0) and Erdoes-Renyi graph (par1->1). The parameter par1 is per default 0.5 and has to be in (0,1). er: Erdoes-Renyi graph where every edge is present independently. power: A graph with power-law degree distribution with expectation d. bipartite: Bipartite graph with at least par1*n nodes in group 1 and at most (1-par1)*n nodes in group 2. The argument par1 has to be in [0,1] and is per default 0.5. barabasi: A graph with power-law degree distribution and preferential attachement according to parameter par1. It must hold that par1 >= 1 and the default is par1=1. geometric: A geometric random graph in dimension par1, where par1 can take values from {2,3,4,5} and is per default 2. If par2="geo" and weighted=TRUE, then the weights are computed according to the Euclidean distance. interEr: A graph with par1 islands of Erdoes-Renyi graphs, every pair of those connected by a certain number of edges proportional to par2. It has to hold that n/s is an integer and par2 is in (0,1) with defaults par1=2 and par2=0.25, respectively.

References

These methods are mainly based on the analogue functions in the igraph package.

Examples

Run this code

# require("Rgraphviz")
set.seed(37)
dag1 <- randDAG(10,4,"regular")
dag2 <- randDAG(10,4,"watts")
dag3 <- randDAG(10,4,"er")
dag4 <- randDAG(10,4,"power")
dag5 <- randDAG(10,4,"bipartite")
dag6 <- randDAG(10,4,"barabasi")
dag7 <- randDAG(10,4,"geometric")
dag8 <- randDAG(10,4,"interEr",par2=0.5)

par(mfrow=c(4,2))
plot(dag1,main="Regular graph")
plot(dag2,main="Watts-Strogatz graph")
plot(dag3,main="Erdoes-Renyi graph")
plot(dag4,main="Power-law graph")
plot(dag5,main="Bipartite graph")
plot(dag6,main="Barabasi graph")
plot(dag7,main="Geometric random graph")
plot(dag8,main="Interconnected island graph")

set.seed(45)
dag0 <- randDAG(6,3)
dag1 <- randDAG(6,3,weighted=FALSE)
dag2 <- randDAG(6,3,DAG=FALSE)
par(mfrow=c(1,2))
plot(dag1)
plot(dag2) ## undirected graph
dag0@edgeData   ## note the uniform weights between 0.1 and 1
dag1@edgeData   ## note the constant weights

wFUN <- function(m,lB,uB) { runif(m,lB,uB) }
dag <- randDAG(6,3,wFUN=list(wFUN,1,4))
dag@edgeData   ## note the uniform weights between 1 and 4

Run the code above in your browser using DataLab