Abstract

In this paper we study two operations of merging components in a chain graph, which appear to be elementary operations yielding an equivalent graph in the respective sense. At first, we recall basic results on the operation of feasible merging components, which is related to classic LWF (Lauritzen, Wermuth and Frydenberg) Markov equivalence of chain graphs. These results are used to get a graphical characterisation of factorisation equivalence of classic chain graphs. As another example of the use of this operation, we derive some important invariants of LWF Markov equivalence of chain graphs. Last, we recall analogous basic results on the operation of legal merging components. This operation is related to the so-called strong equivalence of chain graphs, which includes both classic LWF equivalence and alternative AMP (Andersson, Madigan and Perlman) Markov equivalence.

AMS classification 62H05, 68T30, 05C90

Keywords

chain graph

factorisation equivalence

essential graph

feasible merging components

legal merging components

strong equivalence

A pdf version of the published paper (451kB) is available.

The paper develops the ideas from these papers:

• 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), pp. 43-62. A postscript version of a preprint (590kB) is available.
• A. Roverato: A unified approach to the characterisation of equivalence classes of DAGs, chain graphs with no flags and chain graphs. Scandinavian Journal of Statistics 32 (2005), pp. 295-312.
• A.Roverato, M. Studeny: A graphical representation of equivalence classes of AMP chain graphs. Journal of Machine Learning Research 7 (2006), pp. 1045-1078.
  A pdf version of a preprint (373kB) is available.