Abstract

The class of chain graphs involving both undirected graphs and directed acyclic graphs was introduced in middle eighties for description of probabilistic conditional independence structures. Every class of Markov equivalent chain graphs (that is, the graphs describing the same conditional independence structure) has a natural representative, which is called the largest chain graph. The paper presents a recovery algorithm, which on the basis of the conditional independence structure induced by a chain graph finds the largest chain graph, representing the corresponding class of Markov equivalent chain graphs. As a byproduct an undirect (implicit) graphical characterization of the graphs, which are the largest chain graphs (for a class of Markov equivalent chain graphs) is obtained, and an algorithm changing every chain graph into the largest chain graph of the corresponding equivalence class is described.

AMS classification 68T30, 62H05

Keywords

chain graph

Markov equivalence

largest chain graph

pattern

pool-component principle

A scanned pdf copy (1482kB) is available.

The paper builds on the following works:

• M. Frydenberg: The chain graph Markov property. Scandinavian Journal of Statistics 17 (1990), n. 3, pp. 333-353.
• Ch. Meek: Causal inference and causal explanation with background knowledge. In Uncertainty in Artificial Intelligence 11 (B. Besnard, S. Hanks eds.) Morgan Kaufmann 1995, pp. 403-410.