These programs are dedicated to graph partitionning.

G = (X,E) is an undirected, unweighted graph with |X| = n and |E| = m.

Let A(i,j) = 1, iff (i,j) is an edge (0 otherwise) and let D_{i} be the degree of vertex i.

Its aim is to optimize an integer modularity function equivalent to the Newman modularity.

The problem becomes a clique partitioning one with a complete graph weighted by B(i,j) = 2m × A(i,j) – D_{i} × D_{j}.

The graph is given in a file containing the number of edges (a first record m) and m edges.

This file name if followed by the extension .gr which has not to be specified when the name of the graph is required.

This file must be in a folder denoted Data which is placed in the same folder as the program.

Each edge is given by the two label vertices, separated by at least one "space". Labels are limited to 20 characters.

Finally a partition of X is saved into a file nameofgraph.clas. Classes can be selected according to their cardinality.

Small classes having less element than the minimum defined by the user are not recorded. This class file contains :

- the number of classes,
- for each class,
- the number of vertices
- the list of the label vertices

This program calculates a strict partition (separated classes).

An upper bound of the cardinality of the classes can be fixed. If this bound is set to 0, no bound is used.

- The first step is to evaluate the modularity values between any pair.

Generally, edges have positive weigth and non-edges receive a negative value. - The second step is a hierarchical ascending method applied to B, until the largest link between two classes becomes negative.

This permits to determine the number of clusters, which has not to be given.

The average linkage algorithm has been selected after many tests, simulating graphs containing communities (denses zones). - The thirsd step is a stochastic transfer method.

The transfer procedure consists in assigning each element to the class maximizing its contribution to the modularity value.

And the stochastic part is to test partitions around the current best one, applying the transfer procedure.

The "Bootstrap Clustering" method.

The BC method is to build a partition of the vertices of an unweighted given graph. It first calculates an initial partition using an original algorithm for graph partitioning. This algorithm, denoted TFit for Transfer-Fusion iterated, is close to the Louvain method. Between two consecutive levels of the Louvain algorithm, a transfer procedure of single vertices has been inserted.

The bootstrap procedure builds NbPart graphs, similar to the given graph that are generated using two types of noising (default value : NbPart = 30).

- typ = 1 : the edges length are multiplied by a elongating factor taue (default value .02)
- typ = 2 : the Czekanovski-Dice distance D if first established, and random edges are added.

They correspond to pairs such that D(x,y) < 1. The number of added pairs is fixed by factor \tau_a (default value .5). All the initial and added edges are weighted by 1 - D(x,y).

Each graph is partitionned using the same TFit algorithm, making a profile of NbPart partitions. This profile permits :

- to compute a consensus partition of the NbPart partitions, using the TFit method again
- to evaluate the robusness of any class and any partition.

The robustness coefficient is equal to the average percentage of bootstraped graphs joining pairs. The robustness of both initial partition and consensus partition are edited, with the cluster robustnesses. Both are saved in a file "Bootstrap.nameofgraph.txt" stored in the Data folder.

All the parameter values can be fixed in the beginning of the program. A methological article is submitted ; details can be requested to guenoche@iml.univ-mrs.fr

This program built an overlapping class system from an unweighted simple graph G = (V,E).

The initial overlapping class system can be :

- the set of all maximal cliques (it can be long to establish it first)
- 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.

It is essentially a hierarchical ascending algorithm, as for the ModClust program.

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

The criterion optimized at each step is the average modularity gain.