M. Studeny: Characterization of essential graphs by means of the operation of legal merging of components. International Journal of Uncertainty, Fuzziness, and Knowledge-Based Systems 12 (2004), supplement 1, pp. 43-62.

One of the most common ways of representing equivalent Bayesian networks is the use of essential graphs. Their classic graphical characterization was proposed by Andersson, Madigan and Perlman in 1997. In the contribution an alternative characterization of essential graphs is presented. The main observation is that every essential graph is the largest chain graph within a special class of chain graphs. More precisely, it is the largest chain graph contained in an equivalence class of chain graphs without flags (= certain induced subgraphs). A special operation of legal merging of connectivity components for chain graphs is introduced. This operation leads to an algorithm for finding the essential graph on basis of any graph in that equivalence class of chain graphs without flags which contain the equivalence class of Bayesian networks. In particular, the algorithm may start with any Bayesian network.

AMS classification 68T30

chain graph
acyclic directed graph
legal merging

A pdf copy of the paper (1190kB) only for academic/personal use is available.

The paper is an extended version of the conference paper:

The paper also partially builds on the paper: