Partie 1 : MCl

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 :