Information Technology Reference
In-Depth Information
Theorem 1.
Let clique S
⊆
V
(
G
)
, S is a maximal clique of G,iff
∀
v
i
∈
S and
v
j
∈
N
(
v
i
)
−
S we have S
⊆
N
(
v
j
)
.
Proof:
One direction of the ”if and only if” condition states that clique
S
is a
maximal clique. If
∀
v
i
∈
S,
∃
v
j
∈
N
(
v
i
)
−
S
such that
S
⊂
N
(
v
j
), then in the
subgraph
S
is also a clique. However, we had
S
a maximal clique earlier, meaning that there is no superset of
S
being a clique,
so a contradiction occurs. The other direction of ”if and only if” condition states
that
{
v
j
}∪
S
,
C
(
v
j
) = 1, and set
{
v
j
}∪
∀
v
i
∈
S
and
v
j
∈
N
(
v
i
)
−
S
,wehave
S
⊆
N
(
v
j
), which means there exists
at least one vertex
v
k
∈
S
such that (
v
j
,v
k
)
∈
E
(
G
), so for subgraph
{
v
j
}∪
S
,
v
j
∈
N
(
v
i
)
−
S
,
C
(
v
j
)
=1.Consequently,
S
is a maximal clique.
Fig. 12.1.
4-clique and 3-clique
To make things more concrete, an illustrated example is given as follows on
the network shown in Fig.12.1, and the whole procedure is given in algorithm
1. In Fig.12.1,
C
(
v
0
)=
C
(
v
1
)=
3
3
×
(3
−
1)
2
×
4
4
×
(4
−
1)
2
×
2
=1,
C
(
v
2
)=
C
(
v
3
)=
=
3
,
2
×
1
and
C
(
v
4
)=
1)
= 1. We use set
CLIQUE
to store the candidate maximal
clique. Starting from
v
0
,wechoose
v
1
from
M
(
v
0
)=
2
×
(2
−
{
v
1
,v
2
,v
3
}
. Based on
v
0
and
v
1
,
T
(
v
0
)=
M
(
v
0
)
∩
M
(
v
1
)=
{
v
2
,v
3
}
. Because
T
(
v
0
)
=
∅
,wethuschoose
v
2
from
T
(
v
0
)and
CLIQUE
=
{
v
0
,v
1
}
.From
v
1
and
v
2
,
T
(
v
1
)=
T
(
v
0
)
∩
M
(
v
2
)=
{
v
3
}
.
T
(
v
1
)
=
∅
,
v
3
is chosen, and
CLIQUE
=
CLIQUE
∪{
v
2
}
=
{
v
0
,v
1
,v
2
}
.
From
v
2
and
v
3
,
T
(
v
2
)=
T
(
v
1
)
∩
M
(
v
3
)
∅
,and
CLIQUE
=
CLIQUE
∪
=
{
v
3
}
{
v
0
,v
1
,v
2
,v
3
}
{
v
0
,v
1
,v
2
,v
3
}
−
clique
.Sincethat
=
.Atthismoment,
is a 4
{
is a maximal
clique. Similarly, starting from
v
1
, we can obtain the candidate clique
v
0
,v
1
,v
2
,v
3
}
N
(
v
4
), according to theorem 1,
{
v
0
,v
1
,v
2
,v
3
}
{
v
1
,v
2
,v
3
}
.
However, since that
{
v
1
,v
2
,v
3
}⊂
N
(
v
0
),
{
v
1
,v
2
,v
3
}
is not a maximal clique.
12.4.3
Pruning by Prediction
To address the concern on eciency, at each step of the depth-first search,
Peamc
employs a pruning technique by predicting every possible maximal clique in ad-
vance. Fig.12.2 shows each of the search trees rooted with
{
v
0
,v
1
,v
2
}
in Fig. 12.1.
After we have obtained the maximal 4-clique
{
v
0
,v
1
,v
2
,v
3
}
,wehavetoback-
track to the node
{
v
0
,v
1
}
. However, when we reach the leaf node
{
v
0
,v
1
,v
3
}
,
