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
.
 
Search WWH ::




Custom Search