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

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 |