Two operations of merging and splitting components in a chain graph

Milan Studený; Alberto Roverato; Šárka Štěpánová

Kybernetika (2009)

  • Volume: 45, Issue: 2, page 208-248
  • ISSN: 0023-5954

Abstract

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

How to cite

top

Studený, Milan, Roverato, Alberto, and Štěpánová, Šárka. "Two operations of merging and splitting components in a chain graph." Kybernetika 45.2 (2009): 208-248. <http://eudml.org/doc/37732>.

@article{Studený2009,
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.},
author = {Studený, Milan, Roverato, Alberto, Štěpánová, Šárka},
journal = {Kybernetika},
keywords = {chain graph; essential graph; factorisation equivalence; feasible merging components; legal merging components; strong equivalence; essential graph; factorisation equivalence; feasible merging components; legal merging components; strong equivalence},
language = {eng},
number = {2},
pages = {208-248},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Two operations of merging and splitting components in a chain graph},
url = {http://eudml.org/doc/37732},
volume = {45},
year = {2009},
}

TY - JOUR
AU - Studený, Milan
AU - Roverato, Alberto
AU - Štěpánová, Šárka
TI - Two operations of merging and splitting components in a chain graph
JO - Kybernetika
PY - 2009
PB - Institute of Information Theory and Automation AS CR
VL - 45
IS - 2
SP - 208
EP - 248
AB - 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.
LA - eng
KW - chain graph; essential graph; factorisation equivalence; feasible merging components; legal merging components; strong equivalence; essential graph; factorisation equivalence; feasible merging components; legal merging components; strong equivalence
UR - http://eudml.org/doc/37732
ER -

References

top
  1. An alternative Markov property for chain graphs, In: Uncertainty in Artificial Intelligence, Proc. Twelfth Conference (F. Jensen and E. Horvitz, eds.), Morgan Kaufmann, San Francisco 1996, pp. 40–48. MR1617123
  2. A characterization of Markov equivalence classes for acyclic digraphs, Ann. Statist. 25 (1997), 505–541. MR1439312
  3. On the Markov equivalence of chain graphs, undirected graphs and acyclic digraphs, Scand. J. Statist. 24 (1997), 81–102. MR1436624
  4. Alternative Markov properties for chain graphs, Scand. J. Statist. 28 (2001), 33–85. MR1844349
  5. A transformational characterization of equivalent Bayesian network structures, In: Uncertainty in Artificial Intelligence, Proc. Eleventh Conference (P. Besnard and S. Hanks, eds.), Morgan Kaufmann, San Francisco 1995, pp. 87–98. MR1615012
  6. The chain graph Markov property, Scand. J. Statist. 17 (1990), 333–353. Zbl0713.60013MR1096723
  7. Mixed Interaction Models, Research Report No. R-84-8, Inst. Elec. Sys., University of Aalborg 1984. 
  8. Graphical models for association between variables, some of which are qualitative and some quantitative, Ann. Statist. 17 (1989), 31–57. MR0981437
  9. Graphical Models, Clarendon Press, Oxford 1996. Zbl1055.62126MR1419991
  10. Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann, San Mateo 1988. Zbl0746.68089MR0965765
  11. A unified approach to the characterisation of equivalence classes of DAGs, chain graphs with no flags and chain graphs, Scand. J. Statist. 32 (2005), 295–312. MR2188675
  12. A graphical representation of equivalence classes of AMP chain graphs, J. Machine Learning Research 7 (2006), 1045–1078. MR2274397
  13. Equivalence of Chain Graphs (in Czech), Diploma Thesis, Charles University, Prague 2003. 
  14. A recovery algorithm for chain graphs, Internat. J. Approx. Reasoning 17 (1997), 265–293. MR1462716
  15. Characterization of essential graphs by means of the operation of legal merging of components, Internat. J. Uncertainty, Fuzziness and Knowledge-Based Systems 12 (2004), 43–62. MR2058946
  16. Transition between graphical and algebraic representatives of Bayesian network models, In: Proc. 2nd European Workshop on Probabilistic Graphical Models (P. Lucas ed.), Leiden 2004, pp. 193–200. 
  17. Probabilistic Conditional Independence Structures, Springer-Verlag, London 2005. 
  18. Equivalence and synthesis of causal models, In: Uncertainty in Artificial Intelligence, Proc. Sixth Conference (P. Bonissone, M. Henrion, L. N. Kanal, and J. F. Lemmer, eds.), North-Holland, Amsterdam 1991, pp. 255–270. 
  19. A graphical characterization of the largest chain graphs, Internat. J. Approx. Reasoning 20 (1999), 209–236. MR1685080

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.