Le projet consiste à implémenter en R l’algorithme MCL de partitionnement de graphe (clustering) : à partir d’un graphe et d’un paramètre nommé inflate factor (noté IF par la suite), l’algorithme découpe le graphe en clusters. Exemple sur le graphe ci-dessous avec un IF de 3 :

Introduction sur les graphes

Un graphe est un objet mathématique composé de sommets (vertex) reliés par des arètes (edge). Une des représentations informatiques consiste en une matrice carrée nommée matrice d’adjacence (adjacency matrix). Une cellule de cette matrice contient le poids de l’arète reliant deux sommets ou zéro en absence de lien.

Exemple :

    A  B  C  D
A   0  1  0  4
B   1  0  1  1
C   0  1  0  0
D   1  4  0  0

correspond au graphe :

Remarque : Dans ce dessin, l’épaisseur du trait de l’arète est proportionnel à son poids.

On distingue les graphes orientés (directed graph) des graphes non orientés (undirected graph). Dans un graphe orienté, les arètes sont appelées arcs et ont une direction (de A vers B). La matrice d’adjacence n’est donc plus obligatoirement symétrique et un choix arbitraire est fait concernant son interprétation : par exemple, les sommets sources correspondent aux lignes et les sommets destinations correspondent aux colonnes. Illustration :

    A  B  C  D                                   A  B  C  D
A   0  1  0  4                               A      1     4
B   0  0  0  2   ou de manière plus lisible  B            2
C   0  1  1  0                               C      1  1  
D   0  0  0  0                               D