Information Technology Reference
In-Depth Information
with
T
(
v
0
)=
{
v
3
}
,sincethat
v
0
,
v
2
,and
v
3
share the same clique number 0, the
branch from
can now be pruned. In our experiments, this
pruning strategy often improves the eciency by a factor of 25% on average.
{
v
0
}→{
v
0
,v
2
,v
3
}
Parallel Model of
Peamc
12.4.4
From the above discussion of the basic algorithm, we can find that the enu-
meration of all maximal cliques requires that the search tree rooted with every
vertex of
G
must be traversed. Because every vertex is accessed by the ascending
order of its index, there will be no duplicate triangles and candidate cliques be-
ing generated. In Fig.12.2, we see that from vertex
v
0
we have candidate clique
{
v
0
,v
1
,v
2
,v
3
}
. When we start from vertex
v
1
,only
{
v
1
,v
2
,v
3
}
is built since ver-
tex
v
0
has lower index than vertex
v
1
.Thus
{
v
0
,v
1
,v
2
}
is a duplicate triangle
and will not be considered. This fact indicates that if
v
i
=
v
j
, the traversing of
the search tree rooted with
v
i
, is independent of that rooted with
v
j
shown in
Fig.12.2. Therefore, we have the following theorem.
Theorem 2.
The enumeration of all maximal cliques in graph G with n vertices
can be partitioned into n independent enumerations of the maximal cliques from
the search tree rooted with the each vertex.
Practically, the number of processing elements on the existing parallel platform
P
is often smaller than
n
, so some mapping techniques are required. A naive
mapping scheme is to assign
n
tasks to
P
processing elements sequentially. Let
I
p
∈{
0
,
1
, .., P
−
}
denote the index of the processing element. Each partition
of the
n
tasks assigned to each processing element is presented by [
I
p
×
(
1
n
P
+
n
1])
,
(
I
p
+1)
×
(
P
+ 1)]. However, this scheme sometimes suffers from load
unbalancing, simply because for a search tree rooted with vertex
v
i
,
|M
(
v
i
)
|
may be significantly large. When
n
P
, it is highly possible that many tasks
with vertices having large
may be assigned to the same partition, which
will lead to a high load on a single processing element. To address such problem,
we first sort the vertices of
G
by the descending order of
|
M
(
v
i
)
|
|
M
(
v
i
)
|
and then define
the partition
β
on a single processing element
I
p
as follows
+1
,v
i
=
u
j
,u
j
=
i
i
2
n
P
×
P
+
I
p
=0
β
=
{
v
i
|
i
=0
, ...,
=0
}
(12.1)
i
2
(
i
+1)
×
P
−
I
p
−
1
P
+1
i
=0
|M
(
v
i
)
|
Let
α
=
P
+1
. This mapping scheme enables
α
of most partitions
approximate with each other, which brings a better load balancingwhich will
improve the eciency by a factor of 30% on average.
n
12.4.5
Analysis of Peamc
Based on the experimental results of our research, we have found that the distribu-
tion of the maximal cliques whose size varies from 3 to
M
C
also holds a power-law
feature, where
M
C
represents the size of the maximum clique. Let
x
denote the
