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
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:
- 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.