Chapitre 3 Détection de communautés : approche modularité

Une problématique souvent liée aux graphes est la détection de communautés. Elle consiste à trouver des groupes de nœuds très liés entre eux. Cette thématique est proche du clustering. Nous présentons dans cette partie les approches liées à la modularité. Cette dernière est un critère qui permet de mesurer la performance d’une partition de nœuds dans un graphe, plus la modularité est grande, meilleure est la partition.

Exercice 3.1 (Calculs de modularité) On considère le graphe suivant

G <- make_graph(c(1,2,1,3,1,4,4,5,4,6),directed = FALSE)
plot(G)

et les deux partitions des nœuds suivantes.

cl1 <- c(1,1,1,2,2,2)
cl2 <- c(1,2,1,2,1,1)

  1. Calculer la modularité pour ces deux partitions en utilisant la définition (la formule).

  2. Retrouver ces deux valeurs avec la fonction modularity.

  3. Construire un graphe et proposer une partition avec une modularité élevée et une autre avec une modularité faible.

Exercice 3.2 (Edge betweeness et méthode de Louvain) On considère le graphe suivant :

G1 <- make_full_graph(3)
G2 <- make_full_graph(3)
G3 <- make_full_graph(2)
G4 <- make_full_graph(3)
G5 <- make_full_graph(3)
G <- G1+G2+G3+G4+G5
G <- add.edges(G, c(6,7))
G <- add.edges(G, c(3,7))
G <- add.edges(G, c(8,9))
G <- add.edges(G, c(8,12))
plot(G)

  1. Calculer l’edge betweeness de chaque arête et identifier l’arête qui possède la plus forte valeur.

  2. Effectuer le clustering par edge betweeness et visualiser le dendrogramme. Identifier la première arête retirée.

  3. Représenter les classes sur le graphe.

  4. Couper le dendrogramme pour obtenir 3 classes. On pourra utiliser cutat.

  5. Comparer le résultat avec la méthode de Louvain.

  6. Comparer les modularités obtenues.

  7. Comparer avec cluster_optimal.

Exercice 3.3 (Communautés pour karaté et friends) Utiliser les techniques basées sur la modularité pour faire de classes sur les données karate et friends.

library(igraphdata)
data(karate)