Database Reference
In-Depth Information
Algorithm 7.1
Computing subgraph probabilities.
Input:
A dominant subgraph
G
)
Output:
Subgraph probabilities
f
(
x
)=
Pr
(
G
(
v
)
,
x
)
Method:
1:
for all
connected component
G
i
in
G
(
v
)
(1
≤
i
≤
m
)
do
2:
f
i
(
x
)=
RecursiveSubgraph
(
G
i
,
G
i
.
root
)
;
3:
end for
4:
(
v
f
(
x
)=
f
i
(
x
)
∗···∗
f
m
(
x
)
{
*Symbol
∗
denotes the convolution operation
}
RecursiveSubgraph(
G
,
C
)
Input:
Component
G
and clique
C
Output:
Subgraph probabilities
f
G
C
(
x
)
of
G
C
(the subtree with root
C
)
Method:
1:
for all
children
C
i
of
C
(1
≤
i
≤
m
)
do
2:
f
G
C
i
(
x
)=
RecursiveSubgraph
(
G
i
,
C
i
)
;
3:
end for
4: compute
f
0
(
x
)=
Pr
(
G
C
,
x
|¬
v
1
···¬
v
m
)
;
5:
for
i
=
1to
m
do
6:
compute
f
i
(
x
)=
Pr
(
G
C
,
x
|
v
i
)
;
7:
end for
8: return
f
G
C
(
x
)
by integrating
f
0
(
x
)
,···,
f
m
(
x
)
;
Computing subgraph probabilities when
v
is in
G
(
v
)
Let
C
be the clique containing
v
. When
v
appears, the other vertices in
C
can-
not appear. By plugging in this constraint, the conditional subgraph probability
Pr
(
G
(
v
)
,
x
|
v
)
can be computed using the same method discussed in this section.
7.4.3 Integrating Multiple Components
Once the subgraph probability distribution of each connected component is ob-
tained, we can calculate the convolution of those subgraph probabilities as the sub-
graph probability distribution over all connected component.
Theorem 7.5 (Integrating multiple components).
Given a dominant subgraph
G
(
v
)
, let G
1
,···,
G
m
be a set of connected components of G
(
v
)
. Let n
i
be the number
of cliques in G
i
, then,
1. f
1
(
x
)=
Pr
(
G
1
,
x
)
;
(
i
j
=
1
G
j
,
n
i
x
i
=
2. Fo r
2
≤
i
≤
m, f
i
(
x
)=
Pr
x
)=∑
0
f
i
−
1
(
x
−
x
i
)
Pr
(
G
i
,
x
i
)
.
n
2
The complexity of computing the distribution
Pr
(
G
(
v
)
,
x
)
is
O
(
)
, where
n
is
(
)
the number of cliques in
G
v
.