Information Technology Reference
In-Depth Information
size of a maximal clique and
y
denote the number of the maximal cliques with size
x
, such that
y
=
x
−α
. For the traversing of the search tree rooted with vertex
v
i
,
the calculation of the
triangle neighbor
set
T
(
v
i
)costs
a
0
×
3
−α
)
(
k
×
×
Δ
,where
0
≤
a
0
<
1,
Δ
denotes the maximum degree of
G
.If
T
(
v
i
)
=
∅
, the next round
calculation of
T
(
v
j
) will cost
a
1
×
(
k
×
4
−α
)
×
Δ
.If
T
(
v
j
)
∅
=
, the calculation
of
T
(
v
k
) will cost
a
2
×
Δ
. This process continues recursively until we
reach the leaves of the search tree. Since that
M
C
denotes the length of the deep-
est path from the root to the leaf, the time to enumerate all the maximal cliques
by traversing a single search tree is represented as :
(
k
×
5
−α
)
×
(
a
(
T
0
)
0
3
−α
)
2
+
...
+(
a
(
T
0
)
M
C
−
,a
(
T
0
)
i
M
−
C
)
2
T
0
=
Δ
×{
×
k
×
×
k
×
}
∈
[0
,
1) (12.2)
3
Because
Peamc
requires the traversing of the search tree rooted with every vertex
of
G
, the total runtime is thus represented as
n−
1
3
−α
)
2
[(
a
(
T
0
)
0
)
2
+
...
+(
a
(
T
n−
1
)
0
)
2
]+
...
T
=
T
i
=
Δ
×{
(
k
×
i
=0
n
−
1
)
2
[(
a
(
T
0
)
M
C
−
3
)
2
+
...
+(
a
(
T
n−
1
)
,a
(
T
j
)
i
a
(
T
j
)
i
M
−α
C
M
C
−
3
)
2
]
+(
k
×
}
∈
[0
,
1)
,
= 1 (12.3)
j
=0
Since that [(
a
(
T
0
)
0
)
2
+
...
+(
a
(
T
n−
1
)
0
)
2
]
<
((
a
(
T
0
)
0
)+
..
+(
a
(
T
n−
1
)
0
))
2
=1,wehave
(3
−α
)
2
. Moreover, because all
vertices of
G
are traversed by the ascending order of their index, which eliminates
many duplicate results, and the pruning strategy with prediction also reduces
the search space greatly when the maximal cliques grow large, the actual runtime
is much less than
T
. Thus, to enumerate all the maximal cliques in
G
, it will cost
O
(
Δ
3
−α
)
2
+
...
+(
k
M
−
C
)
2
]
<Δ
T<Δ
×
[(
k
×
×
×
M
C
×
Tri
2
) in the worst case, where
Tri
=
k
3
−α
,andrequire
O
(
Δ
n
)
time as a preprocessing to calculate set
N
(
v
i
) of every vertex. To load the whole
graph
G
with
n
vertices and
m
edges into memory will consume
O
(
m
+
n
) space. If
we have
n
processing elements, according to theorem 2, every processing element
will traverse one search tree rooted with each vertex. Therefore, the parallel
runtime is the time that elapses from the moment a parallel computation starts
to the moment the last processing element ends, which will cost
O
(
Δ×M
C
×Tri
2
×
M
C
×
×
×
n
)
theoretically. In practice, the number of the processing elements
P
is far less
than
n
, so the practical time delay is
O
(
Δ×M
C
×Tri
2
P
) on average.
12.5
Experimental Evaluation
To evaluate the performance of Peamc, we have also implemented
Bron
's
BK
algorithm and
Kazuhisa
's algorithm. Our experiments are done on a
DAWN
Cluster
(84 3.2GHz processors with 2Gbytes of main memory on each node,
Linux AS3
). The implementations of
Kazuhisa
's algorithm and Improved
BK
are strictly based on
Kazuhisa
's and
Bron
's papers. The code is also optimized
