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