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

Remarque : Le lien de C vers lui-même s’appelle une boucle (loop).

Principes et algorithme de MCl

Une bonne méthode de clustering maximise

En ce qui concerne le partitionnement de graphes, une bonne méthode vise à ce que les clusters obtenus

Pour identifier les clusters, MCL se base sur la remarque suivante : si on place un marcheur aléatoire sur un sommet d’un cluster, il a plus de chances (en se promenant aléatoirement d’un sommet à un autre) de rester dans le cluster (plus grande densité de liens) que d’en sortir.

Le procédé s’appuie donc sur le calcul des probabilités de marches aléatoires (probabilité de passer par un sommet et probabilité d’emprunter un arc) dans un graphe donné. Le calcul s’effectue sur des matrices de Markov qui représentent les probabilités de transition d’un sommet à un autre ; il s’agit donc d’une matrice d’adjacence dont la somme des lignes vaut 1 (la somme des probabilités de sortie d’un sommet vaut 1). Exemple avec le graphe précédent :

Matrice d'adjacence                Matrice de Markov
    A  B  C  D                        A  B    C   D
A   0  1  0  4                    A   0  0.2  0   0.8
B   0  0  0  2                    B   0  0    0   1
C   0  1  1  0                    C   0  0.5  0.5 0
D   0  0  0  0                    D   0  0    0   0

Remarque : Ces matrices sont également appelées matrices stochastiques ou encore matrices de transition.

L’algorithme MCL simule des marches aléatoires dans un graphe en alternant deux oprations appelées expansion et inflation. L’expansion correspond au calcul de marches aléatoires de grandes longueurs et coincide à élever une matrice stochastique à une certaine puissance. Concrètement, l’expansion consiste à multiplier la matrice avec elle-même avec le produit matriciel. L’inflation consiste à exagérer les probabilités de marches au sein d’un même cluster et à atténuer les probabilités de marches inter-clusters. En pratique, l’inflation consiste à élever chaque cellule de la matrice à une certaine puissance (inflate factor) puis à normaliser les valeurs obtenues afin que la matrice soit stochastique.

Au final, à force de répéter les opérations d’expansion et d’inflation sur la matrice de transition (et donc sur le graphe), celui-ci est décomposé en différentes composantes (composantes connexes) déconnectées les unes des autres et qui correspondent aux clusters. En d’autres termes, l’algorithme converge et la matrice n’évolue plus.

L’algorithme est donc le suivant :

M : matrice d’adjacence

ajouter les boucles à M
M_1 la matrice stochastique obtenue à partir de M
tant que on observe un changement dans la matrice
faire :
   M_2 \(\leftarrow\) expansion(M_1)
   M_2 \(\leftarrow\) inflation(M_2, inflate_factor)
   déterminer s’il y a eu un changement
   M_1 \(\leftarrow\) M_2

Le résultat est la matrice d’adjacence M_1 ou bien les composantes connexes du graphe correspondant à cette matrice.

Mise en oeuvre en R

Prise en main de la librairie igraph

Pour le chargement, le dessin et l’analyse des graphes, vous pourrez utiliser la librairie igraph.

Pour installer la librairie (si nécessaire) :

install.packages('igraph')

Puis pour l’utiliser :

library(igraph)

Pour créer un graphe à partir d’une matrice d’adjacence :

Exemple pour un graphe non orienté :

Matrice d'adjacence:
    A  B  C  D
A   0  1  0  4
B   1  0  1  1
C   0  1  0  0
D   1  4  0  0

Création de la matrice :

M = matrix(c(0,1,0,1, 1,0,1,4, 0,1,0,0, 4,1,0,0), ncol=4)

Création du graphe à partir de la matrice

g=graph.adjacency(M, mode='undirected', weighted=TRUE)

La fonction V(g) permet d’accéder aux sommets (Vertices) et la fonction E(g) aux arêtes (Edges). On peut ainsi attribuer une étiquette aux sommets :

V(g)$label=c('A','B','C','D')
V(g)
## + 4/4 vertices, from f9c4078:
## [1] 1 2 3 4
V(g)$label
## [1] "A" "B" "C" "D"

On peut accéder au poids des arêtes :

E(g)
## + 4/4 edges from f9c4078:
## [1] 1--2 1--4 2--3 2--4
E(g)$weight
## [1] 1 4 1 4

Et tracer le graphe :

plot(g, vertex.color='white', edge.width=E(g)$weight)

Pour un graphe orienté :

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

Création de la matrice :

M = matrix(c(0,0,0,0, 1,0,1,0, 0,0,1,0, 4,2,0,0), ncol=4)

Création du graphe et ajout des étiquettes :

g=graph.adjacency(M, mode='directed', weighted=TRUE)
V(g)$label=c('A','B','C','D')

Dessin du graphe :

plot(g, vertex.color='white', edge.width=E(g)$weight)