OCG - Overlapping Class Generator
Résumé
This program builds an overlapping class system from an unweighted simple graph G=(V,E). Let |V|=n and |E|=m. It is essentially a hierarchical ascending algorithm joining two classes at each step. The optimized criterion is the modularity. It can be either the average gain or the total gain.
The initial overlapping class 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 class systems can be calculated, the one maximazing the modularity, or the final one. In that case, the expected minimum number of clusters and the maximum caldinality of the final clusters are required. Fusion of classes are realized until one of these conditions is fullfiled. When no more class fusion can be realized the algorithm stops. Let p be the number of initial classes. The complexity is this algorithm is O(p^3).
