How cliquematch
works¶
cliquematch
implements an exact algorithm to find maximum cliques, with a lot
of pruning optimizations for large sparse graphs. The algorithm used is
similar to FMC [1] and PMC [2], but also uses the concept of
bitset-compression from BBMC [3] to save memory. It is implemented in
C++11
, does not use any additional libraries apart from the C++
STL,
and is single-threaded.
Benchmarking the cliquematch
algorithm¶
The below table shows how cliquematch compares to FMC and PMC.
name |
|V| |
|E| |
\(\omega\) |
\(t _{cm}\) |
\(t _{fmc}\) |
\(t _{pmc}\) |
\(t _{cm\_heur}\) |
\(\omega _{cm\_heur}\) |
\(t _{fmc\_heur}\) |
\(\omega _{fmc\_heur}\) |
---|---|---|---|---|---|---|---|---|---|---|
Erdos02 |
6927 |
8472 |
7 |
0.0002 |
0.0014 |
0.0021 |
0.0001 |
6 |
0.0009 |
7 |
Erdos972 |
5488 |
7085 |
7 |
0.0002 |
0.0005 |
0.0016 |
0.0001 |
7 |
0.0002 |
6 |
Erdos982 |
5822 |
7375 |
7 |
0.0002 |
0.0004 |
0.0017 |
0.0001 |
7 |
0.0002 |
7 |
Erdos992 |
6100 |
7515 |
7 |
0.0002 |
0.0004 |
0.0016 |
0.0001 |
8 |
0.0002 |
8 |
Fault_639 |
638802 |
14626683 |
18 |
0.6856 |
13.8808 |
|
0.6045 |
18 |
2.4705 |
18 |
brock200_2 |
200 |
9876 |
11 |
0.1213 |
0.6329 |
0.0017 |
0.0019 |
10 |
0.0023 |
9 |
c-fat200-5 |
200 |
8473 |
58 |
0.0002 |
0.4155 |
0.0004 |
0.0001 |
58 |
0.0103 |
58 |
ca-AstroPh |
18772 |
198110 |
57 |
0.0019 |
0.0789 |
0.0133 |
0.0017 |
56 |
0.0287 |
57 |
ca-CondMat |
23133 |
93497 |
26 |
0.0007 |
0.0055 |
0.0083 |
0.0008 |
26 |
0.0043 |
26 |
ca-GrQc |
5242 |
14496 |
44 |
0.0002 |
0.0005 |
0.0017 |
0.0001 |
43 |
0.0011 |
44 |
ca-HepPh |
12008 |
118521 |
239 |
0.0035 |
0.013 |
0.015 |
0.0032 |
239 |
0.2525 |
239 |
ca-HepTh |
9877 |
25998 |
32 |
0.0002 |
0.0007 |
0.0035 |
0.0001 |
32 |
0.0001 |
32 |
caidaRouterLevel |
192244 |
609066 |
17 |
0.0175 |
0.2134 |
0.0762 |
0.0157 |
17 |
0.0695 |
15 |
coPapersCiteseer |
434102 |
16036720 |
845 |
0.0295 |
0.8348 |
1.4065 |
0.0276 |
845 |
14.7004 |
845 |
com-Youtube |
1134890 |
2987624 |
16 |
0.2239 |
9.6494 |
|
0.1694 |
16 |
0.3484 |
13 |
cond-mat-2003 |
31163 |
120029 |
25 |
0.0014 |
0.013 |
0.0099 |
0.0013 |
25 |
0.0038 |
25 |
cti |
16840 |
48232 |
3 |
0.0021 |
0.0036 |
0.0046 |
0.001 |
3 |
0.0013 |
3 |
hamming6-4 |
64 |
704 |
4 |
0.0002 |
0.0003 |
0.0001 |
0.0001 |
4 |
7.8917 |
4 |
johnson8-4-4 |
70 |
1855 |
14 |
0.0264 |
0.1456 |
0.0003 |
0.0001 |
11 |
0.0005 |
14 |
keller4 |
171 |
9435 |
11 |
2.0404 |
15.3436 |
|
0.0016 |
9 |
0.0027 |
9 |
loc-Brightkite |
58228 |
214078 |
37 |
2.4475 |
2.7237 |
0.0277 |
0.0051 |
36 |
0.0153 |
31 |
fmc -t 0 -p
was used to run the FMC branch-and-bound algorithm.pmc -t 1 -r 1 -a 0 -h 0 -d
(single CPU thread, reduce wait time of 1 second, full algorithm, skip heuristic, search in descending order) was used to run the PMC branch-and-bound algorithm.fmc -t 1
was used to run the FMC heuristic algorithm.A small script was used to run the
cliquematch
algorithm.cliquematch
was compiled withBENCHMARKING=1
.
The benchmark graphs were taken from the UFSparse [4], SNAP
[5], and DIMACS [6] collections. \(|V|\) and
\(|E|\) denote the number of nodes and edges in the graph. \(\omega\)
denotes the size of the maximum clique found. All the branch-and-bound methods
agreed on the maximum clique size in every benchmark. \(t_{cm}\),
\(t_{fmc}\), and \(t_{pmc}\) denote the time taken by cliquematch
,
FMC, and PMC respectively in the branch-and-bound search: the least time is in
bold text. \(w_{cm-heur}\), \(t_{cm-heur}\) denote the size of clique
and time taken by the heuristic method in cliquematch
; and similarly for
\(w_{fmc-heur}\) and \(t_{fmc-heur}\). A minus sign (-
) indicates
that the program returned an error without completing the calculation.
Correspondence Graphs in C++
¶
The correspondence graph classes are generated using simple C++ template
programming (simple because it’s basically a typed macro substitution).
cliquematch
can be extended with custom correspondence graphs: they can be
prototyped using the existing classes, and/or implemented in C++ for
performance. The source code of IsoGraph
or
AlignGraph
are good places to start if you’re trying to implement
a custom correspondence graph class.
References¶
- 1
Bharath Pattabiraman, Md Mostofa Ali Patwary, Assefaw H Gebremedhin, Wei-keng Liao, and Alok Choudhary. Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection. Internet Mathematics, 11(4-5):421–448, 2015.
- 2
Ryan A Rossi, David F Gleich, and Assefaw H Gebremedhin. Parallel maximum clique algorithms with applications to network analysis. SIAM Journal on Scientific Computing, 37(5):C589–C616, 2015.
- 3
Pablo San Segundo, Diego Rodríguez-Losada, and Agustín Jiménez. An exact bit-parallel algorithm for the maximum clique problem. Computers & Operations Research, 38(2):571–581, 2011.
- 4
Timothy A Davis and Yifan Hu. The university of florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011.
- 5
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. https://snap.stanford.edu/data, June 2014.
- 6
David S Johnson and Michael A Trick. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993. Volume 26. American Mathematical Soc., 1996.