Introduction

BNGenerator is a program that generates random Bayesian networks, guaranteeing that the distribution of generated networks is (asymptotically) uniform. The program is coded in Java and is freely distributed under the GNU license.

The program accepts constraints on the maximum degree for nodes and on the maximum number of arcs in the network; these constraints limit how "connected" the networks are. Also, it is possible to control the induced width of the network, leading to more "realistic" networks. Other constraints (for example, maximum number of parents for each node) could be coded with relatively simple modifications in the program; the theoretical analysis of the algorithm and the source code are available, and these modifications should not be too hard.

BNGenerator was coded by Jaime Shinsuke Ide , as a result of research conducted by Jaime S. Ide and Fabio G. Cozman . Ideas and results were based on the work of G. Melançon and M. Bousquet-Melou, and some parts of BNGenerator were directly inspired by the DagAlea software. The research was funded by FAPESP .

Generation method

• A directed acyclic graph with N nodes.
• For each node, a random variable with V values.
• For each variable, a conditional probability distribution p(X|P) , where P indicates the variables that are parents of X in the graph (that is, the nodes associated with P are parents of the node associated with X ).

There is a huge number of directed acyclic graphs for any reasonably large number of nodes. Even though there are expressions that would allow one to compute the number of directed acyclic graphs, there does not seem to exist a simple method that would allow us to sample uniformly from this huge space. Basically, there does not seem to be a method to map the integers (from 1 to some large number M) to the directed acyclic graphs with N nodes. But even if we knew how to sample from the space of all possible directed acyclic graphs, that knowledge would not give us a practical solution to the problem of generating random Bayesian networks. It has been observed that in practice Bayesian networks are rather sparse graphs, in the sense that nodes have a few parents and children (that is, the degree of the nodes is not too large). Now, our problem then is to generate uniformly distributed samples from the class of directed acyclic graphs with restrictions on node degree (or possibly, restrictions on the number of parents, number of children, number of arcs, etc). This is a hard problem.

Our approach, and the proofs that our algorithms for generating random directed acyclic graphs are correct, are in the paper

Jaime Shinsuke Ide , Fabio Gagliardi Cozman . Generating random Bayesian networks , Brazilian Symposium on Artificial Intelligence , Recife, Pernambuco, Brazil, 2002.

To generate random directed acyclic graphs, BNGenerator uses MCMC methods (Markov chain Monte Carlo). We define a set of possible transitions for a graph (that is, a set of possible modifications for the graph) and we select one transition at random. Given the characteristics of the possible transitions and the selection process, a random directed acyclic graph with uniform distribution is produced after several transitions. In fact, the result is asymptotic: in the limit of infinitely many transitions, a uniformly distributed sample will be produced. In the paper indicated previously, we present the transitions and selection process used by BNGenerator, and prove that they have the right properties: after many transitions, we obtain a uniform random Bayesian network. In theory we would have to wait for infinitely many iterations, but in practice we stop at a large number. Empirical studies suggest that for a graph with N nodes, we should perform at least 4 * N * N transitions. That is the number of transitions that BNGenerator adopts by default, but the user can specify a different number.

When we have a random directed acyclic graph, it is easy to generate a number V for each node. We just sample the uniform distribution between 2 and some maximum allowed number Vm. Once we have the number of values for all variables in the graph, we can generate probability distributions by sampling from Dirichlet distributions. See the paper indicated previously for a more detailed discussion.

BNGenerator starts from a very simple Bayesian network (a chain of nodes where each node has at most a parent and a child) and keeps performing transitions. The user can specify how many transitions are performed before a network is saved in file. After a network is saved, BNGenerator can keep performing transitions and saving more networks.

An important point is that we differentiate between generic graphs and graphs that do have a single path (directed or undirected) between any two nodes. The latter graphs are said singly connected, and also called polytrees. The distinction is important in Bayesian networks because singly connected networks have interesting properties that do not generalize to other classes of networks. It should be noted that no guaranteed algorithm for generating random polytrees seems to exist at the moment (that is, an algorithm that can guarantee the distribution of the generated samples). BNGenerator can produce random singly connected Bayesian networks if the user wishes to do so.

Controlling induced width constraint

Recently, we added a new feature on BNGenerator as described with details on the paper

Jaime Shinsuke Ide , Fabio Gagliardi Cozman . Generation of Random Bayesian Networks with Constraints on Induced Width, with Applications to the Average Analysis od d-Connectivity, Quasi-random Sampling, and Loopy Propagation. University of São Paulo. Technical Report June 2003. (320KB )

We eventually found that the most appropriate quantity to control is the induced width of networks. The induced width of a network can be easily explained and understood; it conveys the algorithmic complexity of inferences and, indirectly, it captures how dense the network is. Our tests indicate (rather subjectively) that a network with low induced width ''looks like'' real networks in the literature. Besides, it makes sense to control induced width, as we are usually interested in comparing algorithms or parameterizing results with respect to the complexity of the underlying network, and induced width is the main indicator of such complexity. Unfortunately, the generation of random graphs with constraints on induced width is significantly more involved than the generation of graphs with constraints on node degree and number of edges. In the paper above, we report on new algorithms that accomplish generation of graphs with simultaneous constraints on all these quantities: induced width, node degree, and number of edges.

Finding the exact value of induced width is NP-hard problem with no easy solution. Then, in order to get more efficiency, we compute as ''induced width'' a value obtained with a particular efficient heuristic. We observed that the heuristic approximates very well the exact value of the induced width.

Downloading BNGenerator

Running BNGenerator

BNGenerator is run as follows (assuming all files and the colt.jar library are in the same directory):

nNodes

the number of nodes in the networks that are generated. Default is 4. Note: nNodes must be larger than 3 (you can easily generate all directed acyclic graphs with 3 nodes).

maxDegree

The maximum degree of any node in the networks that are generated (the degree of a node is the sum of incoming and outgoing arcs). Default is (nNodes - 1). Note: maxDegree must be larger than 2 (you can easily enumerate all graphs with nNodes and maxDegree equal to 2).

maxArcs

The maximum number of arcs that can be present in the generated networks. Note that, for a given number of nodes and a given maximum degree, the number of arcs must satisfy some constraints. If the specified number of arcs is impossible, a message is printed. The default behavior is to ignore any constraint on the number of arcs.

maxIW

The maximum value of induced width in the generated networks. Induced width conveys the algorithmic complexity of inferences and, indirectly, it captures how dense the network is. The default behavior is to ignore any constraint on induced width.

nBNs

The number of random Bayesian networks that are generated and actually saved in files. Default is 1.

nTransitions

The number of iterations (transitions in the Markov chain built by BNGenerator) between networks are generated and saved. Note that every iteration generates a new Bayesian network; after nTransitions , a network is saved in a file (and this process is repeated nBNs times). Default is (4 * nNodes * nNodes ).

format

The output format for the generated networks. it can be either xml (in which case the output is in the XMLBIF format) or java (in which case the output is a Java program that can be used to input data into the EBayes library or xmljava (in which case both outputs are generated). Default is xml.

nVal

The maximum number of values for each variable (node) in the generated networks. Each variable has a random number of values between 2 and nVal. Default is 2 (every variable is binary).

fName

The name of the file(s) that will receive output networks. An extension will be appended to fName , depending on the value of format . If nBNs is larger than one, a sequence of files is generated. The file names are of the form fName X.format , where X is a number. Default is Graph .

structure

The type of network generated: either singly (in which case singly-connected networks will be generated) or multi (in which case multi-connected networks will be generated with Algorithm 1 of paper , if there is no constraint on induced width; otherwise, networks will be generated with Algorithm PMMixed of paper ). Singly connected networks are usually called polytrees. Note that multi option leads to the generation of generic graphs, including graphs that are singly connected, trees, and chains. But the probability of hitting a singly connected graph using the multi option is really small for large values of nNodes. Default is multi.

Examples

java -classpath .;colt.jar BNGenerator -nNodes 20 - maxDegree 3 -nBNs 1 - fName example

Generates one Bayesian network with 20 binary nodes and stores the network in the file example1.xml . Every node has a maximum degree of 3. Before the final network is saved, 1600 transitions are performed (using the default 4*20*20).