jayitha/clique-summary

computing redundancy-aware maximal cliques (acm sigkdd'13)

Purpose

This software implements ideas in paper Redundancy-Aware Maximal Cliques (see reference below).

Recent research efforts have made notable progress in improving the performance of (exhaustive) maximal clique enumeration (MCE). However, existing algorithms still suffer from exploring the huge search space of MCE. Furthermore, their results are often undesirable as many of the returned maximal cliques have large overlapping parts. This redundancy leads to problems in both computational efficiency and usefulness of MCE.

We aim at providing a concise and complete summary of the set of maximal cliques, which is useful to many applications. We propose the notion of �_t-visible MCE_ to achieve this goal and design algorithms to realize the notion. The algorithm samples the set of original maxmal cliques, using a recursive search with part of the search branches pruned. The algorithn is accompanied with an optional global filtering stage.

Two versions of the algorithm are available -- randomized and deterministic. The former probabilistically guarantees the summary quality under the notion of visibility , while the latter does definitely. Check the reference paper for details.

One may use the refined output space in efficient computations of, for example, top-k results with diversity and interactive clique exploration.

Program arguments

1. [input file]
2. [t] (as $\tau$ in the paper)
3. [R|D] ( R for randomized algorithm, D for deterministic)
4. [G|L] ( G to switch on global filter, L to switch off)
5. [output file] (summary, one clique per line)

Program output

• the summary

• of cliques in summary

• top-10 cliques scored by coverage

Input file format

• ascii file, adjacency lists
• 1st line: n, m for # of vertices/edges
• ith line: vertex i described by id, deg, list of neighbors

Reference

Jia Wang, James Cheng, Ada Wai-Chee Fu.
Redundancy-Aware Maximal Cliques.
19th ACM SIGKDD Conference On Knowledge Discovery and Data Mining (KDD'13), Chicago, USA