Home Research Network Bioinformatics C. Brun OCG


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.


For a detailed explanation of the algorithm, please see Becker et al., 2012.



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
cd OCG
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 <graph_file>



./OCG [options] <graph_file>

Available options are as follows:

Initial Class System type. Choices are:


(M)aximal Cliques
(C)entered Cliques (default), with two possibilities:
0: requires a stop criterion (see -s and -n)
1: maximizing the partition modularity (default)
Maximum allowed class (s)ize. Can take any integer value from 0 (default, no constraint) upwards
Minimum (n)umber of expected classes (0 means no constraint)
Set an output file to import partition in the Clust&See cytoscape (P)lugin.
The name has to end by a '.cns' extension.
(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:

node1    node2
node2    node3
node1    node3

The included test.gr graph file is an example of this format.


Download the algorithm as described in Becker et al., 2012.