Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering

Ole J. Mengshoel, David C. Wilkins, Dan Roth

Research output: Contribution to journalArticlepeer-review


This article presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating, since they allow controlled experimentation to determine the impact of improvements to inference algorithms. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. Our generation algorithms, called BPART and MPART, support controlled but random construction of bipartite and multipartite Bayesian networks. The Bayesian network parameters that we vary are the total number of nodes, degree of connectivity, the ratio of the number of non-root nodes to the number of root nodes, regularity of the underlying graph, and characteristics of the conditional probability tables. The main dependent parameter is the size of the maximal clique as generated by tree clustering. This article presents extensive empirical analysis using the Hugin tree clustering approach as well as theoretical analysis related to the random generation of Bayesian networks using BPART and MPART.

Original languageEnglish (US)
Pages (from-to)1137-1174
Number of pages38
JournalArtificial Intelligence
Issue number16-17
StatePublished - Nov 2006
Externally publishedYes


  • Bayesian networks
  • C / V-ratio
  • Controlled experiments
  • Maximal clique size
  • Probabilistic reasoning
  • Random generation
  • Tree clustering inference

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering'. Together they form a unique fingerprint.

Cite this