OCG, an Overlapping Cluster Generator of large network

OCG builds an overlapping cluster system from an unweighted simple graph G=(V,E). OCG is essentially based on 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 : (i) the set of all maximal cliques (it can take a long time to establish) (ii) the set of edges (many initial classes (m) implying many steps (O(m)) or (iii) 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.

Related publication : Becker, E., Robisson, B., Chapple, C. E., Guénoche, A. & Brun, C. Multifunctional proteins revealed by overlapping clustering in protein interaction network. Bioinformatics 28, 84–90 (2012)

Documentation : Online Documentation

Download : See HAL-AMU article