Studeny.a21

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.

Abstract
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

Keywords: chain graph; acyclic directed graph; flag; 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:

M. Studeny: Characterization of essential graphs by means of an operation of legal component merging. In Proceedings of the 1st European Workshop on Probabilistic Graphical Models (PGM'02) (J. A. Gamez, A. Salmeron eds.), University Castilla la Mancha 2002, pages 161-168.

The paper also partially builds on the paper:

S. A. Andersson, D. Madigan, M. D. Perlman: A characterization of Markov equivalence classes for acyclic digraphs. Annals of Statistics 25 (1997), pp. 505-541.