Database Reference
In-Depth Information
Fo r 1
<
i
<
m, the conditional subgraph probability of G i given
¬
v i is
v i p
Pr
(
G i ,
x
v i )=
Pr
( ¬
v i 1
v i ) ·
Pr
(
G i 1 ,
x
v i 1 ) ·
Pr
( ¬
v i 1 ¬
v i )
v i p .
v i p
+
Pr
( ¬
v i 1
v i ) ·
Pr
(
G i 1
,
x
F
v i 1
) ·
Pr
(
v i 1
¬
v i )
+
Pr
(
v i 1
v i ) ·
Pr
(
G i 1 ,
x
|
v i 1 )
The conditional subgraph probability of G i given v i is
Pr
(
G i ,
x
|
v i )=
Pr
(
G i 1 ,
x
v i .
F
v i 1 )
To compute subgrph probabilities, we scan cliques C 1 ,···,
C m and calculate
Pr
(
G i ,
x
|
v i )
and Pr
(
G i ,
x
v i )
for 0
x
i . Then, we compute Pr
(
G m ,
x
)
for
G m = 1 j m C j using
Pr
(
G m ,
x
)=
Pr
(
v m 1 )
Pr
(
G m 1 ,
x
|
v m 1 )
v p
+
Pr
( ¬
v m 1 )
Pr
(
G m 1 ,
x
v m 1 )
Pr
( ¬
v m 1 )
(7.7)
v p .
v p
+
Pr
( ¬
v m 1 )
Pr
(
G m 1 ,
x
F
v m 1 )
Pr
(
v m 1 )
m 2
The overall complexity is O
(
)
.
7.4.2 A Tree of Cliques
(
)
Now let us consider the general case where the clique graph of G i
v
is a tree.
Example 7.5 (Connecting multiple cliques). Figure 7.6(b) shows three cliques C 1 ,
C 2 and C 3 connected by clique C. C 1 ,C 2 and C 3 are the end vertices of three clique
chains. Let v 1 ,v 2 and v 3 be the three common vertices between C and C 1 ,C 2 and C 3 ,
respectively. Then, there are five possible value assignments of C: v p =
1 ,v 1 =
1 ,
v 2 =
1 ). In any of the five
cases, the joint probability distribution of C 1 ,C 2 and C 3 are conditionally indepen-
dent. The subgraph probability of the three cliques is simply the product of their
conditional subgraph probabilities.
1 ,v 2 =
1 or no vertices taking value 1 (if
v V C Pr
(
v
) <
We scan the cliques in a clique tree in the depth first order. When we reach a leaf
clique C l , its subgraph probability is calculated and sent to its parent clique C p .If C p
only contains one child, then the subgraph probability of the subtree containing C l
and C p is computed at C p , using Theorem 7.4. If C p contains more than one child,
then the subgraph probability of all cliques in the subtree with root C p is computed at
C p as described in Example 7.5. The complete procedure is shown in Algorithm 7.1.
Generally, if there are d chains of cliques connecting to a clique C , calculating the
subgraph probability for each chain takes O
n i )
where n i is the number of cliques
contained in the i -th chain. Calculating the subgraph probability for all cliques takes
O
(
dn 2
(
)
, where n
= 1 i d n i is the number of cliques in all d chains.
 
Search WWH ::




Custom Search