Title ----- OCG - Overlapping Class Generator Authors ------- Alain Guenoche (I2M, guenoche@iml.univ-mrs.fr) with contributions from Benoit Robisson and Charles E. Chapple Maintener --------- Lionel Spinelli (TAGC, lionel.spinelli@univ-amu.fr) Details ------- 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). Licence ------- Copyright (C) 2011 Alain Guenoche (guenoche@iml.univ-mrs.fr) with contributions from Benoit Robisson and Charles E. Chapple This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see .