Home Software OCG

 

Overlapping Cluster Generator (OCG)

Description

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.

 

Installation

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>

 

Usage

./OCG [options] <graph_file>

Available options are as follows:

Initial Class System type. Choices are:

 

-m:
(M)aximal Cliques
-e:
(E)dges
-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:

node1    node2
node2    node3
node1    node3


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

Download

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

OCG_1.0_Becker_et_al