graph generation utilities {bnlearn}

Generate empty, complete or random graphs

Description

Generate empty, complete or random directed acyclic graphs from a given set of nodes.

Usage

empty.graph(nodes, num = 1)
complete.graph(nodes, num = 1)
random.graph(nodes, num = 1, method = "ordered", ..., debug = FALSE)

Arguments

nodes

a vector of character strings, the labels of the nodes.

num

an integer, the number of graphs to be generated.

method

a character string, the label of a score. Possible values are ordered (full ordering based generation), ic-dag (Ide's and Cozman's Generating Multi-connected DAGs algorithm) and melancon (Melancon's and Philippe's Uniform Random Acyclic Digraphs algorithm).

...

additional tuning parameters (see below).

debug

a boolean value. If TRUE a lot of debugging output is printed; otherwise the function is completely silent. Ignored in some generation methods.

Details

Graph generation algorithms available in random.graph() are:

• full ordering based generation (ordered): generates graphs whose node ordering is given by the order of the labels in the nodes argument. The same algorithm is used in the randomDAG function in package pcalg.

• Ide's and Cozman's Generating Multi-connected DAGs algorithm (ic-dag): generates graphs with a uniform probability distribution over the set of multiconnected graphs.

• Melancon's and Philippe's Uniform Random Acyclic Digraphs algorithm (melancon): generates graphs with a uniform probability distribution over the set of all possible graphs.

Additional arguments for the random.graph() function are:

• prob: the probability of each arc to be present in a graph generated by the ordered algorithm. The default value is 2 / (length(nodes) - 1), which results in a sparse graph (the number of arcs should be of the same order as the number of nodes).

• burn.in: the number of iterations for the ic-dag and melancon algorithms to converge to a stationary (and uniform) probability distribution. The default value is 6 * length(nodes)^2.

• every: return only one graph every number of steps instead of all the graphs generated with ic-dag and melancon. Since both algorithms are based on Markov Chain Monte Carlo approaches, high values of every result in a more diverse set of networks. The default value is 1, i.e. to return all the networks that are generated.

• max.degree: the maximum degree for any node in a graph generated by the ic-dag and melancon algorithms. The default value is Inf.

• max.in.degree: the maximum in-degree for any node in a graph generated by the ic-dag and melancon algorithms. The default value is Inf.

• max.out.degree: the maximum out-degree for any node in a graph generated by the ic-dag and melancon algorithms. The default value is Inf.

empty.graph() generates num identical empty graphs, while complete.graph() generates num identical complete directed acyclic graphs.

Value

empty.graph(), complete.graph() and random[.graph() return an object of class bn (if num is equal to 1) or a list of objects of class bn (otherwise). If every is greated than 1, random.graph() always returns a list, regardless of the number of graphs it contains.

Author(s)

Marco Scutari

References

Ide JS, Cozman FG (2002). "Random Generation of Bayesian Networks". Proceedings of the 16th Brazilian Symposium on Artificial Intelligence, 366–375.

Melancon G, Dutour I, Bousquet-Melou M (2001). "Random Generation of Directed Acyclic Graphs". Electronic Notes in Discrete Mathematics, 10:202–207.

Melancon G, Philippe F (2004). "Generating Connected Acyclic Digraphs Uniformly at Random". Information Processing Letters, 90(4):209–213.

Examples

empty.graph(LETTERS[1:8])
random.graph(LETTERS[1:8])
plot(random.graph(LETTERS[1:8], method = "ic-dag", max.in.degree = 2))
plot(random.graph(LETTERS[1:8]))
plot(random.graph(LETTERS[1:8], prob = 0.2))