Revision b1e762cae4768d2b8b3ba3d946048e056ccb5e16 authored by Software Heritage on 22 November 2018, 09:11:57 UTC, committed by Software Heritage on 22 November 2018, 09:11:57 UTC
0 parent
README
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 <http://www.gnu.org/licenses/>.
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...