Skip to content

Latest commit

 

History

History
104 lines (86 loc) · 13.1 KB

how.rst

File metadata and controls

104 lines (86 loc) · 13.1 KB
Raw

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 fmc and PMC pmc, but also uses the concept of bitset-compression from BBMC bbmc 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| ω tcm tfmc tpmc tcm_heur ωcm_heur tfmc_heur ω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 with BENCHMARKING=1.

The benchmark graphs were taken from the UFSparse ufsparse, SNAP snap, and DIMACS dimacs collections. |V| and |E| denote the number of nodes and edges in the graph. ω denotes the size of the maximum clique found. All the branch-and-bound methods agreed on the maximum clique size in every benchmark. tcm, tfmc, and tpmc denote the time taken by cliquematch, FMC, and PMC respectively in the branch-and-bound search: the least time is in bold text. wcm − heur, tcm − heur denote the size of clique and time taken by the heuristic method in cliquematch; and similarly for wfmc − heur and tfmc − 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 ~cliquematch.IsoGraph or ~cliquematch.AlignGraph are good places to start if you're trying to implement a custom correspondence graph class.

References

refs.bib