Database Reference
In-Depth Information
C
C
3
Scan order
v
p
v
3
v
2
v
p
v
1
C
1
v
i−1
v
i
C
2
C
i+1
C
i−1
C
i
(a) A chain of cliques.
(b) A tree of cliques.
Fig. 7.6
Difference cases in subgraph recurrence.
C
m
be a chain of cliques. The two consecutive cliques
C
i
−
1
and
C
i
share a common vertex
v
i
−
1
(2
Generally, let
C
1
,···,
≤
i
≤
m
). Each clique
C
i
contains at most
three vertices, as illustrated in Figure 7.6(a).
A private vertex
v
i
p
only belongs to
C
i
.
•
•
A head vertex
v
i
−
1
belongs to
C
i
and
C
i
−
1
.
•
A tail vertex
v
i
belongs to
C
i
and
C
i
+
1
.
Trivially,
C
1
has no head vertex and
C
m
has no tail vertex.
Let
G
i
−
1
=
1
≤
j
≤
i
−
1
C
j
and
G
i
=
S
i
−
1
∪
C
i
. To compute
Pr
(
G
i
,
x
|¬
v
i
)
, two cases
−{
}
−{
}
may arise, since
C
i
v
i
−
1
and
G
i
−
1
v
i
−
1
are conditionally independent given
v
i
−
1
.
1.
v
i
−
1
appears. Then no other vertices in
C
i
can appear.
2.
v
i
−
1
does not appear. In order to have
x
selected vertices appear in
G
i
, we consider
two subcases.
a. no selected vertex in
C
i
appears. Then there must be
x
selected vertices in
G
i
−
1
appear.
b. 1 vertex in
C
i
appears. Then there must selected
x
−
1 vertices in
G
i
−
1
appear.
Summarizing the above cases, we have the following theorem.
Theorem 7.4 (Conditional subgraph probabilities).
Given a chain of cliques
C
1
,···,
C
m
, let G
i
=
1
≤
j
≤
i
C
j
,
C
i
, and v
i
p
be the private vertex
{
v
i
−
1
}
=
C
i
−
1
∩
of C
−
i. The conditional subgraph probability of G
1
given
¬
v
1
is
⎧
⎨
v
p
)
−
1
−
Pr
(
Pr
(
v
1
)
,
x
=
0
;
1
−
Pr
(
v
1
)
v
p
)
Pr
(
G
1
,
x
|¬
v
1
)=
Pr
(
v
1
)
,
x
=
1
;
⎩
1
−
Pr
(
0
,
x
>
1
.
The conditional subgraph probability of G
1
given v
1
is
1
,
x
=
1
;
Pr
(
G
1
,
x
|
v
1
)=
0
,
x
=
1
.
