A chordal graph is one where for each cycle of length greater than three, there is a chord connecting unconnected nodes of the cycle. It can be converted into a Bayesian network.
If the graph is chordal and represents a minimal I-map, the distribution it represents can be decomposed into product form. These graphs can be represented as DAG Bayesian Networks or as undirected Markov Networks.
Test for Chordality
Graph triangulation algorithm a.k.a. Fill-In algorithm. (Tarjan and Yannakakis 1984)
Construction
Fill-In Algorithm
Given a graph G
- Compute an ordering of the nodes from 1 to |V|
- From n = |V| to 1, connect all the parents of node n
If no edges were added, the graph was already chordal. However, the graph may have been chordal even if edges were added.
Last modified: 2017/03/15 00:24
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International