In short, a parameterized high performance library for computing maximum cliques in large sparse graphs.
Finding maximum cliques, k-cliques, and temporal strong components are in general NP-hard. 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.
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/socfb-Texas84.mtx -a 0
PMC has been tested on Ubuntu linux (10.10 tested) and Mac OSX (Lion tested) with gcc-mp-4.7 and gcc-mp-4.5.4
If you run into problems compiling, ensure openMP is installed. In OSX, this can be done in the terminal using:
sudo port selfupdate
sudo port install gcc47
port select --list gcc to list all gcc versions, you should see mp-gcc47.
To select mp-gcc4.7, use the command:
sudo port select --set gcc mp-gcc47
And you're all set. Note that other gcc versions also work (e.g., mp-gcc45, mp-gcc46,…).
Please let me know if you run into any issues.
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.
The parallel maximum clique algorithms use tight bounds that are fast to compute. A few of those are listed below.
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 k-core pruning steps ./pmc -f ../pmc/data/output/socfb-Stanford3.mtx -a 2 # k-core pruning and greedy coloring ./pmc -f ../pmc/data/output/socfb-Stanford3.mtx -a 1 # neighborhood core pruning (and ordering for greedy coloring) ./pmc -f ../pmc/data/output/socfb-Stanford3.mtx -a 0
The reduction wait parameter
-r below is set to be 1 second (default = 4 seconds).
./pmc -f data/sanr200-0-9.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/socfb-Stanford3.mtx -a 0 -t 2 -r 999
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:
dual_degorders vertices by the sum of degrees from neighbors
dual_kcoreorders vertices by the sum of core numbers from neighbors
kcore_degvertices are ordered by the weight k(v)d(v)
randrandomized ordering of vertices
Vertices are searched by default in increasing order, to search vertices in decreasing order, use the
./pmc -f data/p-hat700-2.mtx -a 0 -d
The fast heuristic may also be customized to use various greedy selection strategies. This is done by using
-h with one of the following:
kcore_degselect vertex that maximizes k(v)d(v)
randrandomly select vertices
Approximate the maximum clique using ONLY the heuristic by not setting the exact algorithm via the
-a [num] option. For example:
./pmc -f data/sanr200-0-9.mtx -h deg
# heuristic is turned off by setting `-h 0`. ./pmc -f data/tscc_enron-only.mtx -h 0 -a 0
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/socfb-Stanford3.mtx -a 0 -k 50
-o rand to find potentially different cliques of a certain size
# Computes a clique of size 36 from sanr200-0-9 ./pmc -f data/sanr200-0-9.mtx -a 0 -k 36 -o rand