Graph Partitionning

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 Di 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) – Di × Dj.

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 :

ModClust.c

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.

BootClust.c

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

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

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

OCG.c

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

The initial overlapping class system can be :

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(p3).
The criterion optimized at each step is the average modularity gain.