What if CLIQUE were fast? Maximum Cliques in Information Networks and Strong Components in Temporal Networks
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.
Download
Prereqs
- A working Matlab mex compiler
- A working C/C++ compiler
Setup
First, you'll need to compile the fastMaxClique directory.
In bash:
$ cd fastMaxClique/src/
$ make
Then for the parallelized version:
$ cd fastMaxClique/src_parallel/
$ make
Next, start matlab in the directory where you unzipped the cliques.tar.gz file
$ matlab
>> cd shared_codes/compile
For maxcliques, cd mc/code/, and type: >> setup_paths
Note the same directions apply for computing the largest temporal strong component.
This should work on Mac OSX (Lion tested) and Ubuntu linux (10.10 tested) with Matlab R2011a.
See 'mc/code/examples.m' or 'tscc/code/examples.m' for further details.
Please let me know if you run into any issues.
Overview
The package is organized by directory
/fastMaxClique
- C++ codes for max clique
/shared_codes
- Codes used for both maxclique and temporal scc
/mc/codes/
- Codes for preprocessing graphs for maxclique, exporting graphs, computing bounds & network stats
/tscc/codes/
- Codes used for computing the reachability graph and temporal scc
Figures
|Experiment|Description|Figure|
|:------------------|:------------------------------------|:------------------|
|shared_codes/merge_info.py
| Performance of the max clique algorithm | Tab. 1 |
|mc/codes/bounds_plot.m
| Relationships between the max clique and graph properties | Fig. 1 |
|mc/codes/bounds_plot.m
| Analysis of the max clique upperbounds | Fig. 2 |
|tscc/codes/print_reach_table.m
| Dynamic network, temporal SCC, and reachability stats | Tab. 2 |
|shared_cores/merge_info.py
| Performance of max clique alg. for Temporal SCC's | Tab. 3 |
|mc/codes/vary_upperbound.m
| Varying the upperbound of the max clique algorithm | Fig. 5 |
|mc/codes/print_mc_table.m
| Static network stats and lower/upper bounds | Tab. 4 |
|mc/codes/print_mc_table.m
| Dynamic retweet network stats and lower/upper bounds | Tab. 5 |