2
$\begingroup$

Assume that I have a belief network with a set of nodes.

In order to create a valid junction tree I have to moralize the graph. Assume now that I have nodes with more than 2 parents (e.g 3 parents) then I have to link each of the parents. After doing that, the graphical models contain some unnecessary cliques. Can I use only a part of the cliques for the Junction Tree Creation? Or I must use every clique in the junction tree (e.g., a case with 8 nodes and 8 cliques)?

$\endgroup$
1
$\begingroup$

You only need to use maximal cliques. That is, if you have two cliques {a,b,c} and {a,b}, you only use {a,b,c}. Other than that, yes, you might generate unnecessary cliques, but how many depends also on the triangulation strategy (minimum fill-in is an NP-hard problem, so you won't really be able to do it perfectly in all cases).

$\endgroup$
0
$\begingroup$

I'm trying to implement the junction tree algorithm in Ruby.

I found that after moralizing, triangulating, and creating the final cliques by variable elimination, the final cliques contained all of the cliques from triangulated graph, but the maximally connected cliques in the triangulated graph were combined into one clique in the junction tree.

I'm new at this, but I don't think you can drop cliques along the way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.