Moral graph

In graph theory, a moral graph is used to find the equivalent undirected form of a directed acyclic graph. It is a key step of the junction tree algorithm, used in belief propagation on graphical models.

A directed acyclic graph
The corresponding moral graph, with newly added arcs shown in red

The moralized counterpart of a directed acyclic graph is formed by adding edges between all pairs of non-adjacent nodes that have a common child, and then making all edges in the graph undirected. Equivalently, a moral graph of a directed acyclic graph G is an undirected graph in which each node of the original G is now connected to its Markov blanket. The name stems from the fact that, in a moral graph, two nodes that have a common child are required to be married by sharing an edge.[1]

Moralization may also be applied to mixed graphs, called in this context "chain graphs". In a chain graph, a connected component of the undirected subgraph is called a chain. Moralization adds an undirected edge between any two vertices that both have outgoing edges to the same chain, and then forgets the orientation of the directed edges of the graph.

Weakly recursively simplicial

A graph is weakly recursively simplicial if it has a simplicial vertex and the subgraph after removing a simplicial vertex and some edges (possibly none) between its neighbours is weakly recursively simplicial. A graph is moral if and only if it is weakly recursively simplicial.

A chordal graph (a.k.a., recursive simplicial) is a special case of weakly recursively simplicial when no edge is removed during the elimination process. Therefore, a chordal graph is also moral. But a moral graph is not necessarily chordal.[2]

Recognising moral graphs

Unlike chordal graphs that can be recognised in polynomial time, Verma & Pearl (1993) proved that deciding whether or not a graph is moral is NP-complete.

gollark: The implications are obvious.
gollark: 2 = 0 (mod 2).
gollark: Maybe you can't.
gollark: But I wear those.
gollark: That's what they said.

See also

References
  1. Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J. (1999). "3.2.1 Moralization". Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. Springer-Verlag New York. pp. 31–33. doi:10.1007/0-387-22630-3_3. ISBN 0-387-98767-3.CS1 maint: ref=harv (link)
  2. Cowell et al. (1999), p. 50.
  • Verma, T. S.; Pearl, J. (1993), "Deciding morality of graphs is NP-complete", Uncertainty in Artificial Intelligence: 391–399, arXiv:1303.1501.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.