Chapitre 7 : Mining de graphes
Les graphes (réseaux sociaux, web, interactions) sont au cœur du big data. On s’intéresse ici à deux tâches : détecter les communautés (Girvan-Newman) et mesurer la similarité de nœuds (SimRank).
Objectifs
À la fin de ce chapitre, vous devez pouvoir :
Dérouler Girvan-Newman (détection de communautés par betweenness)
Dérouler SimRank (similarité de nœuds par marche aléatoire)
1. Girvan-Newman (détection de communautés)
Idée : les arêtes entre communautés sont traversées par beaucoup de plus courts chemins. On retire itérativement les arêtes de plus forte intermédiarité (edge betweenness) pour faire apparaître les communautés.
La betweenness d’une arête = nombre de paires de nœuds dont un plus court chemin emprunte cette arête (créditée fractionnellement quand il y a plusieurs plus courts chemins).
Algorithme :
Calculer la betweenness de toutes les arêtes (BFS depuis chaque nœud : comptage des plus courts chemins descendant, puis crédit remontant).
Retirer l’arête de betweenness maximale.
Recalculer les betweenness des arêtes restantes.
Répéter : le graphe se scinde progressivement en composantes = communautés.
On obtient une hiérarchie de communautés (comme un dendrogramme) ; on choisit le niveau de coupe (souvent via la modularité).
2. SimRank (similarité de nœuds)
Idée : « deux nœuds sont similaires s’ils sont référencés par des nœuds similaires ». C’est une définition récursive, évaluée par marche aléatoire.
où \(I(x)\) = voisins entrants de x, et \(C \in (0,1)\) un facteur d’atténuation ; avec \(s(a,a) = 1\).
Algorithme (itératif) : initialiser \(s(a,b)=1\) si \(a=b\), sinon 0 ; puis itérer la formule jusqu’à convergence. (Interprétation : expected meeting distance de deux marcheurs aléatoires remontant les arêtes.) Utilisé pour la recommandation, la désambiguïsation, la recherche de pages liées.
3. Autres (brève description)
Méthode |
Idée |
|---|---|
Modularité (Louvain) |
Optimiser la modularité par fusions locales — très scalable (≫ Girvan-Newman). |
Clustering spectral |
Utiliser les valeurs/vecteurs propres du laplacien du graphe pour partitionner. |
Comptage de triangles / clustering coefficient |
Mesurer la cohésion locale (souvent en MapReduce). |
Plus courts chemins en MapReduce |
BFS distribué (cf. friend recommendation, TP4). |
Exercices
Exercice 1 — Betweenness
Dans un graphe « haltère » (deux triangles A-B-C et D-E-F reliés par l’unique arête C–D), quelle arête a la plus forte betweenness, et pourquoi Girvan-Newman la retire-t-il en premier ?
▶ Voir la correction
L’arête C–D : c’est le seul pont entre les deux groupes, donc tous les plus courts chemins reliant un nœud de {A,B,C} à un nœud de {D,E,F} passent par elle → betweenness maximale. La retirer sépare le graphe en ses deux communautés naturelles.
Exercice 2 — SimRank
Pourquoi SimRank est-il défini de façon récursive, et que représente le facteur \(C\) ?
▶ Voir la correction
Parce que la similarité de deux nœuds dépend de celle de leurs voisins, qui dépend à son tour de la leur, etc. — d’où une définition récursive résolue par itérations jusqu’au point fixe. Le facteur \(C \in (0,1)\) atténue la contribution des voisins éloignés (sinon la similarité « se propagerait » sans décroître) ; il garantit la convergence et reflète que la similarité décroît avec la distance.