Surf Wiki
Save to docs
general/bayesian-networks

From Surf Wiki (app.surf) — the open knowledge base

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.

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.

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.

Recognising moral graphs

Unlike chordal graphs that can be recognised in polynomial time, proved that deciding whether or not a graph is moral is NP-complete.{{cite journal

References

References

  1. (1999). "Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks". Springer-Verlag New York.
  2. {{harvtxt. Cowell. Dawid. Lauritzen. Spiegelhalter. 1999, p. 50.
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

bayesian-networks graphical-models graph-operations
Want to explore this topic further?

Ask Mako anything about Moral graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report