### 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.