Information Technology Reference
In-Depth Information
by our best efforts with
C++ STL
. These algorithms have been first examined
with graphs generated randomly. Then they are challenged with the complex
networks and
Peamc
is also evaluated on large sparse call graphs built by real
data taken from one telecom carrier for months in a city. The runtime in tables is
expressed in seconds and we give the following notations for short:
M.D.
stands
for
Max Degree
,
M.C.
for the number of
Maximal Cliques
,
M
C
is the size of
the maximum clique,
Ka
for
Kazuhisa
's Algorithm,
BK
for Improved BK,
P
n
and
P
n
represent
Peamc
on
n
processing elements with and without pruning
respectively and
s
stands for speedup in the end.
12.5.1
Random Networks
Our random graphs are generated as follows. For given
r
and
n
, we build a
graph with
n
vertices such that
v
i
and
v
j
are adjacent with probability 0.5 if
i
+
n
r
.Weexaminethecaseof
r
=10
and
r
=30with
n
= 1000
,
2000
,
4000
,
8000
,
16000
,
32000 respectively.
By comparing the results of
r
=10and
r
= 30 in Table 12.1 and 12.2, we see
that Improved
BK
's performance keeps stable regardless of
−
j
(
mod n
)
≤
r
or
j
+
n
−
i
(
mod n
)
≤
|
E
(
G
)
|
. However, in
the case of
r
= 30, when
grows large, the clustering coecient of every
vertex is also increasing, thus
Peamc
outperforms Improved
BK
gradually. Since
our implementation of
Kazuhisa
's algorithm is optimized for the sparse graph
according to the paper with
O
(
Δ
4
)timedelay,
Kazuhisa
's algorithm performs
better in Table 12.3 than in Table 12.1 and 12.2.
|
V
(
G
)
|
Table 12.1.
Results on random networks with
r
=10
|V
(
G
)
||E
(
G
)
|
M.D. M.C.
M
C
Ka
BK
P
1
P
30
s
1000
4534
16
2239
6
7
0.5
0.2 0.01 19.8
2000
8938
16
4396
6
27
4
0.4 0.02 19.7
4000
17987
24
8894
6
116
29
0.9 0.04 20
8000
36223
28
18112
6
519
243
1.8 0.09 18.5
16000 71904
35
35897
6
n/a 1934 3.6 0.19 18.8
32000 144350
44
68794
6
n/a 15389 7.3 0.38 19
Table 12.2.
Results on random networks with
r
=30
|V
(
G
)
||E
(
G
)
|
M.D. M.C.
M
C
Ka
BK
P
1
P
30
s
1000
14432
64
19269
8
275
0.7
29 1.69 17.6
2000
28709
82
38060
8
1006
4
56 3.27 17.4
4000
58063
92
78054
8
12464
31
124 6.49 19
8000 116276 112 157278
8
50371
244
248 13.4 18.5
16000 231622 128 311572
9
n/a
1937 486 26 18.8
32000 464069 154 626207
9
n/a 15331 984 47.8 20.6
