Database Reference
In-Depth Information
v
1
v
1
v
v
5
v
v
5
v
8
v
8
2
2
v
4
v
4
v
3
v
3
v
6
vv
v
v
6
v
v
v
7
7
9
10
9
10
G
1
G
2
G
3
G
1
G
2
G
3
(a) Compute
Pr
(
G
(
v
5
)
,
x
)
.
(b) Compute
Pr
(
G
(
v
6
)
,
x
)
.
Fig. 7.7
Reuse the intermediate results.
Last, in component G
3
, suppose we have computed the conditional subgraph
probability Pr
(
G
3
(
v
5
)
,
x
|
v
5
)=
Pr
(
{
v
4
},
x
|
v
5
)
. Then, we can compute the subgraph
probability Pr
(
G
3
(
v
6
)
,
x
)=
Pr
(
{
v
4
,
v
5
},
x
)
based on Pr
(
G
3
(
v
5
)
,
x
|
v
5
)
using Equa-
tion 7.7.
Generally, let
S
=
{
v
1
,···,
v
n
}
be the set of vertices satisfying
P
and sorted in the
ranking order. Let
G
(
v
i
)
be the dominant graph of
v
i
. After obtaining the subgraph
probability of
G
(
v
i
)
, we scan
v
i
+
1
and compute the subgraph probability for
G
(
v
i
+
1
)
.
For each component
G
j
, one of the following four cases happens.
Case 1: neither
v
i
nor
v
i
+
1
is in
G
j
.
(
)=
(
)
Then,
G
j
v
i
+
1
G
j
v
i
.
G
1
in Figure 7.7 illustrates this case.
Case 2: only
v
i
is in
G
j
.
G
3
in Figure 7.7 is an example of this case. After the conditional subgraph proba-
bility
Pr
has been computed, when scanning
v
i
+
1
, we want to compute
the subgraph probability
Pr
(
G
j
(
v
i
)
,
x
|
v
i
)
(
G
j
(
v
i
+
1
)
,
x
)
. The following corollary shows that
G
j
(
v
i
)
is a subgraph of
G
j
(
v
i
+
1
)
.
Corollary 7.3 (Property of dominant subgraphs).
Given a PME-graph G
=(
V
,
E
)
and two vertices v
i
and v
j
, let G
(
v
i
)
and G
(
v
j
)
be the dominant subgraphs of v
i
and v
j
, respectively. If v
i
f
v
j
, then G
(
v
i
)
is a
subgraph of G
.
Proof.
There are two categories of vertices in
G
(
v
j
)
(
v
i
)
. Let
v
be a vertex in
G
(
v
i
)
.We
only need to show that
v
is also in
G
(
v
j
)
.
If
v
.
If
v
is not ranked higher than
v
i
, then
v
must be a joint vertex lying in a path
f
v
i
, then
v
f
v
j
(since
v
i
v
j
). Thus,
v
is also in
G
(
v
j
)
v
1
,···,
v
,···,
v
2
where
v
1
f
v
i
and
v
2
f
v
i
. Since
v
i
f
v
j
,wehave
v
1
f
v
j
and
v
2
f
v
j
. Thus,
v
is also in
G
(
v
j
)
.
Therefore, we can compute the subgraph probability
Pr
(
G
j
(
v
i
+
1
)
,
x
)
based on
(
(
)
,
|
)
Pr
G
j
v
i
x
v
i
using Equation 7.7.
