Information Technology Reference
In-Depth Information
Definition 3.
For a vertex v
i
∈
V
(
G
)
, if the neighbors of v
i
are part of a clique,
then there will be
|N
(
v
i
|
)(
|N
(
v
i
)
|−
1
2
total edges among them. The ratio of the
number E of the edges that actually exist between the vertices of N
(
v
i
to the
total number of edges is the
clustering coecient
of v
i
denoted as C
(
v
i
)=
2
E
1)
.
|
N
(
v
i
)
|×
(
|
N
(
v
i
)
|−
12.4.2
Basic Idea and Method
To eciently enumerate all maximal cliques, we must address the following two
issues. The first one is how to provide a systematic way to enumerate all the
maximal cliques without duplicates. The second one is how to design smart
strategies to prune futile search subspaces to speed up the searching process.
In terms of the first issue, it is actually concerned with the correctness and
completeness of the algorithm. From the priori discussion, we see that the av-
erage clustering coecient value of random networks is rather different from
that of complex networks. In a random graph, since the edges are distributed
randomly, the
clustering coe
cient
is the connection probability
p
. However, in
most real networks the clustering coecient is typically much larger than it is in
a comparable random network which has the same number of nodes and edges as
the real network. From definition 3, we see that the
clustering coe
cient
is a di-
rect indication to the existence of triangle structures. Because triangle structure
or 3-clique is the basic unit of any clique whose size is larger than 3, we could
take advantage of this fact to develop our traversal strategy to search for the
vertices that could build triangles by depth-first order recursively. For each step
of this traversal process, the large
clustering coe
cient
property of the complex
networks will be an important clue to find the maximal cliques quickly.
All vertices of
G
will be accessed by the ascending order of their index. For
v
i
G
, a search tree rooted with
v
i
where each node corresponds to a candi-
date clique will be built and traversed. In the beginning, the vertices of
M
(
v
i
)
will be chosen by the ascending order of their index. Suppose the current ver-
tex with the smallest index chosen from
M
(
v
i
)is
v
j
.From
v
i
and
v
j
we build
the
triangle neighbor
set
T
(
v
i
).
∈
in the
search tree. Again, a vertex
v
k
with the smallest index from set
T
(
v
i
) will be
chosen. Next, based on
v
j
and
v
k
, we build the
triangle neighbor
set
T
(
v
j
). If
T
(
v
j
)
{
v
i
,v
j
}
becomes the direct child of
{
v
i
}
. This process will repeat
recursively until we reach the leaf node of the search tree where we could not
build any triangle neighbor set. Apparently the traversal process of the search
tree is actually the process of building triangles. Because every candidate vertex
is accessed by the ascending order of its index, there will be no duplicate tri-
angles and candidate cliques being generated. Since the search tree rooted with
every vertex in
G
will be traversed, which means all the candidate cliques will
be identified, the completeness of
Peamc
is thus ensured. To identify whether
the candidate clique is a maximal clique, we present the following theorem.
=
∅
,
{
v
i
,v
j
,v
k
}
forms the child node of
{
v
i
,v
j
}
