Parallel Maximum Clique (PMC) Library
In short, a parameterized high performance library for computing maximum cliques in large sparse graphs.
Finding maximum cliques, kcliques, and temporal strong components are in general NPhard. Yet, these can be computed fast in most social and information networks. The PMC library is designed to be fast for solving these problems. Algorithms in the PMC library are easily adaptable for use with a variety of orderings, heuristic strategies, and bounds.
 Maximum clique: Given a simple undirected graph G and a number k, output the clique of largest size.
 Kclique: In kclique, the problem is to find a clique of size k if one exists.
 Largest temporalscc: Given a temporal graph G, a temporal strong component is a set of vertices where all temporal paths exist between the vertices in that set. The Largest TSCC problem is to find the largest among all the temporal strong components.
Features
 General framework for parallel maximum clique algorithms
 Optimized to be fast for large sparse graphs + Algorithms tested on networks of 1.8 billion edges
 Set of fast heuristics shown to give accurate approximations
 Algorithms for computing Temporal Strongly Connected Components (TSCC) of large dynamic networks
 Parameterized for computing kcliques as fast as possible
 Includes a variety of tight linear time bounds for the maximum clique problem
 Ordering of vertices for each algorithm can be selected at runtime
 Dynamically reduces the graph representation periodically as vertices are pruned or searched + Lowers memoryrequirements for massive graphs, increases speed, and has caching benefits
Synopsis
Setup
First, you’ll need to compile the parallel maximum clique library.
$ cd path/to/pmc/
$ make
Afterwards, the following should work:
# compute maximum clique using the full algorithm `a 0`
./pmc f data/socfbTexas84.mtx a 0
PMC has been tested on Ubuntu linux (10.10 tested) and Mac OSX (Lion tested) with gccmp4.7 and gccmp4.5.4
If you run into problems compiling, ensure openMP is installed. In OSX, this can be done as follows:
sudo port selfupdate
Now, install GCC via the terminal command:
sudo port install gcc47
Now type "port select list gcc", you should see mpgcc47, among others. To select MPGCC 4.7, run the command:
sudo port select set gcc mpgcc47
And you're all set. Note that other gcc versions also work (e.g., mpgcc45, mpgcc46,…).
Please let me know if you run into any issues.
Input file format

Matrix Market Coordinate Format (symmetric)
For details see: http://math.nist.gov/MatrixMarket/formats.html#MMformat%%MatrixMarket matrix coordinate pattern symmetric 4 4 6 2 1 3 1 3 2 4 1 4 2 4 3

Edge list (symmetric and unweighted): Codes for transforming the graph into the correct format are provided in the experiments directory.
Overview
The parallel maximum clique algorithms use tight bounds that are fast to compute. A few of those are listed below.
 Kcores
 Degree
 Neighborhood cores
 Greedy coloring
All bounds are dynamically updated.
Examples of the three main maximum clique algorithms are given below. Each essentially builds on the other.
# uses the four basic kcore pruning steps
./pmc f ../pmc/data/output/socfbStanford3.mtx a 2
# kcore pruning and greedy coloring
./pmc f ../pmc/data/output/socfbStanford3.mtx a 1
# neighborhood core pruning (and ordering for greedy coloring)
./pmc f ../pmc/data/output/socfbStanford3.mtx a 0
Dynamic graph reduction
The reduction wait parameter r
below is set to be 1 second (default = 4 seconds).
./pmc f data/sanr20009.mtx a 0 t 2 r 1
In some cases, it may make sense to turn off the explicit graph reduction. This is done by setting the reduction wait time ‘r’ to be very large.
# Set the reduction wait parameter
./pmc f data/socfbStanford3.mtx a 0 t 2 r 999
Orderings
The PMC algorithms are easily adapted to use various ordering strategies. To prescribe a vertex ordering, use the o option with one of the following:
deg
kcore
dual_deg
orders vertices by the sum of degrees from neighborsdual_kcore
orders vertices by the sum of core numbers from neighborskcore_deg
vertices are ordered by the weight k(v)d(v)rand
randomized ordering of vertices
Direction of ordering
Vertices are searched by default in increasing order, to search vertices in decreasing order, use the d
option:
./pmc f data/phat7002.mtx a 0 d
Heuristic
The fast heuristic may also be customized to use various greedy selection strategies. This is done by using h
with one of the following:
deg
kcore
kcore_deg
select vertex that maximizes k(v)d(v)rand
randomly select vertices
Terminate after applying the heuristic
Approximate the maximum clique using ONLY the heuristic by not setting the exact algorithm via the a [num]
option. For example:
./pmc f data/sanr20009.mtx h deg
Turning the heuristic off
# heuristic is turned off by setting `h 0`.
./pmc f data/tscc_enrononly.mtx h 0 a 0
Kclique
The parallel maximum clique algorithms have also been parameterized to find cliques of size k. This routine is useful for many tasks in network analysis such as mining graphs and community detection.
# Computes a clique of size 50 from the Stanford facebook network
./pmc f data/socfbStanford3.mtx a 0 k 50
using o rand
to find potentially different cliques of a certain size
# Computes a clique of size 36 from sanr20009
./pmc f data/sanr20009.mtx a 0 k 36 o rand
Terms and conditions
Please feel free to use these codes. We only ask that you cite:
Ryan A. Rossi, David F. Gleich, Assefaw H. Gebremedhin, Md. Mostofa Patwary,
A Fast Parallel Maximum Clique Algorithm for Large Sparse Graphs and Temporal
Strong Components, arXiv preprint 1302.6256, 2013.
These codes are research prototypes and may not work for you. No promises. But do email if you run into problems.
Copyright 20112013, Ryan A. Rossi. All rights reserved.