A Fast Parallel Maximum Clique Algorithm for Large Sparse Graphs and Temporal Strong Components
Ryan A. Rossi
David F. Gleich
Assefaw H. Gebremedhin
Md. Mostofa Ali Patwary
These codes are research prototypes and may not work for you. No promises. But do email if you run into problems.
Online appendix
We could not fit all the data we wished to into the space constraints of the paper. The omitted data is on this website.
Download our fast max-clique solver
pmc is our fast max-clique solver. It's described in the paper, but please read about it here too.
-
<a href="https://www.cs.purdue.edu/homes/dgleich/codes/maxcliques/pmc.zip"> pmc.zip </a>
(Download)
Prereqs
- A working C/C++ compiler
Setup
First, you'll need to compile the parallel maximum clique library.
In bash, change to the directory where you unzipped the pmc.zip file, and type make
:
$ cd path/to/pmc/
$ make
Afterwards, the following should work:
%% compute maximum clique using the full algorithm `-a 0`
./pmc -f data/flickr-sym-both-cc.mtx -a 0
Please let me know if you run into any issues.
Overview
The parallel maximum clique library is organized by directory
/
- C++ codes for max clique algorithms
/data/
- A few sample graphs
/experiments/
- Codes for preprocessing graphs for maximum clique, exporting graphs, computing bounds & network stats
/experiments/tscc/codes/
- Codes used for computing the reachability graph
Figures
|Experiment|Description|Figure|
|:------------------|:------------------------------------|:------------------|
|exp/pmc_runner.py
| Performance of the max clique algorithm | Tab. 1 |
|exp/plots/pmc_linear_perf.m
| Runtime of PMC scales linearly with the network dimension | Fig. 1 |
|exp/plots/speedup_social.m
| Speedup of PMC for social networks | Fig. 4 |
|exp/plots/speedup_dimacs.m
| Speedup of PMC for DIMACs benchmark graphs | Fig. 5 |
|exp/plots/pp_social_serial.m
| Performance profile of benchmark solvers for social networks | Fig. 6a |
|exp/plots/pp_dimacs.m
| Performance profile of benchmark solvers for DIMACS | Fig. 6b-c |
|exp/pmc_runner.py
| Performance of PMC for computing Temporal SCC's | Tab. 2 |