Overlapping Cluster Generator (OCG)
This program builds an overlapping cluster system from an unweighted simple graph G=(V,E).
Let |V|=n and |E|=m.
It is essentially a hierarchical ascending algorithm. It starts by building an initial set of overlapping clusters. At each step, two clusters are joined if their union results in a gain (either average or total) in modularity.
The initial overlapping cluster system can be :
- the set of all maximal cliques (it can take a long time to establish)
- the set of edges (many initial classes (m) implying many steps (O(m))
- the set of "centered cliques" (at most n), giving a fast solution for large graphs.
Two 'partitions' (strictly speaking a partition cannot be overlapping) can be calculated. By default, the algorithm returns the system of clusters that maximized the modularity of the 'partition'. Alternatively, if either a minimum number of clusters, or the maximum allowed cluster cardinality is set by the user, OCG will return the 'partition' that maximizes the overall modularity within those constraints.
OCG is written in C, you will therefore need to get a C compiler if you do not already have one.
On a GNU/linux system, using gcc as a compiler, use the following commands:
tar xvzf OCG.tgz
gcc OCG.c -o OCG
You can then copy the program to a directory in your
$PATH (eg /usr/bin/) or just run it from the current directory:
./OCG [options] <graph_file>
Available options are as follows:
Initial Class System type. Choices are:
|-c:||(C)entered Cliques (default), with two possibilities:|
|0: requires a stop criterion (see -s and -n)|
|1: maximizing the partition modularity (default)|
|-s:||Maximum allowed class (s)ize. Can take any integer value from 0 (default, no constraint) upwards|
|-n:||Minimum (n)umber of expected classes (0 means no constraint)|
|-p:||Set an output file to import partition in the Clust&See cytoscape (P)lugin.|
|The name has to end by a '.cns' extension.|
|-v:||(V)erbose, print a progress report and some other information to standard error.|
Note: It is possible to use Centered Cliques with maximizing the modularity (-c 1, default) and add some constraints with -s and/or -n.
Using OCG is very simple. Once you have compiled, you can try it with the included graph file test.gr:
./OCG -v test.gr
Graph file format
The graph file should be a simple text file with one edge per line eg:
The included test.gr graph file is an example of this format.