Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes

Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Mesures Graphe Mesure PageRank

la connectivité ou influence transitive des nœuds peut être calculé soit en

distribuant de manière itérative le rang (initialement le degré) des nœuds sur
Degré de centralité : nombre d’arêtes qui lui sont associées leurs voisins
Community Analytics (nombre de voisins adjacents) parcourant le graphe et en compant la frequance avec laquel on visite
chaque voisin.
Centralité moyenne : moyenne des distances du nœud à tous les autres
(valeur faible = nœud central) porte le nom de Larry Page (le fondateur de Google) car l’algorithme est
Stefania Dumbrava utilisé pour donner un rang aux pages qu’on obtient quand on fait une
Betweenness centrality : recenser le plus court chemin entre chaque paire recherche sur Google.
ENSIIE
de nœuds, comptabiliser le nombre de fois où il passe par le sommet étudié initialement, la mesure est définie comme :
(rapporté sur le nombre de plus courts chemins possibles entre ces nœuds).
07 Février 2022 Plus le betweenness centrality est grand, plus le sommet est central PR(T1 ) PR(Tn )
puisqu’il est situé à la “croisée” des chemins. PR(A) = (1 d) + d( + ... + )
C (T1 ) C (Tn )

ou on peut directement arriver sur la page A à partir des pages T1 , . . . , Tn ,

C (X ) est le nombre de pages rèférences par la page X et d = 0.85.

1/43 2/43 3/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Mesure PageRank Mesure PageRank Community Analytics

Exemple : La communication sur Twitter

des utilisateurs envoyent des tweets sur un sujet spécifique
les autres utilisateurs peuvent répondre avec un retweet
les utilisateurs peuvent êtres regroupés selon la topologie de leur
communication (graph clustering)
une analyse de leurs interactions peut aider à identifier :
des groupes d’utilisateurs
des motifs de communication (communication patterns)

Figure: Example : PageRank (I/II)

Figure: Example : PageRank (I/II)

4/43 4/43 5/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Qu’est-ce qu’une communauté ? Qu’est-ce qu’une communauté ? Qu’est-ce qu’une communauté ?

Intuition
un group de nœuds connectés plus densément que le reste.

Définition
pas de définition universelle
dépend du domaine d’application

Figure: Communautés dans les interactions cellulaires entre proteines

Figure: Communautés dans des interactions Twitter

6/43 6/43 6/43

 Introduction Introduction Introduction
Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Composantes d’un graphe Rappel : DFS/BFS Exercice

Composantes Connexes
ensemble des nœuds qui sont entièrement connectés à travers des
chemins, i.e., il existe un chemin entre chaque paire des nœuds Donner les parcours BFS et DFS sur le graphe suivant :
C ✓ V , t.q., 8vi , vj 2 C, 9p 2 G : p = vi . . . vj
en considérant l’orientation : composantes connexes fortes
(strongly connected components - SCC)
sans orientation : composantes connexes faibles
(weakly connected components - WCC)

Figure: Exemple parcours DFS/BFS d’un graphe

Figure: Exemple de SCC (gauche) et WCC (droite)

7/43 8/43 9/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Weakly Connected Components Strongly Connected Components Algorithme de Tarjan

Algorithme de Tarjan
trouver toutes les SCC d’un graphe oriénté
Comment trouver les WCC d’un graphe ? complexité linéaire O(|V | + |E |)
facile : une composante à la fois Intuition
on peut utiliser soit un parcours BFS ou DFS utiliser DFS pour les arêtes sortantes
commencer BFS/DFS sur un nœud donné trouver la connéxion arrière minimale (lowest back link)
parcourir en BFS/DFS sur les arêtes sortantes et entrantes Comptabiliser...
l’algorithme BFS/DFS va trouver toutes les WCC les nœuds pas visités
répéter avec le prochain nœud pas visité les nœuds visités dans une pile, selon l’ordre de visite
...jusqu’à avoir visité tous les nœuds la profondeur DFS avec un indexe pour chaque nœud visité
complexité linéaire O(|V | + |E |) les arêtes qui sont connectés en arrière (avec la partie du graphe
deja visité) sont prises en compte avec un index low link pour
chaque nœud visité (le low link est le index DFS le plus bas parmi
tous les voisins d’un nœud)

10/43 11/43 12/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Algorithme de Tarjan Algorithme de Tarjan

13/43 14/43 15/43

 Introduction Introduction Introduction
Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Algorithme de Tarjan Algorithme de Tarjan

16/43 17/43 18/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Algorithme de Tarjan Algorithme de Tarjan

19/43 20/43 21/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Algorithme de Tarjan Algorithme de Tarjan

22/43 23/43 24/43

 Introduction Introduction Introduction
Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Algorithme de Tarjan Algorithme de Tarjan

25/43 26/43 27/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Algorithme de Tarjan Algorithme de Tarjan

28/43 29/43 30/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Algorithme de Tarjan Clustering Clustering

partitionnement d’un graphe dans des sous-graphes (clusters) t.q il y
a un ensemble d’arêtes dense dans chaque cluster partitionnement d’un graphe dans des sous-graphes (clusters) t.q il y
a un ensemble d’arêtes dense dans chaque cluster
Mèthodes min-max cut
diviser un graphe dans des clusters A et B
minimisant le nombre des connexions entre A et B et
maximisant le nombre des connexions dans chaque cluster
Fonctionnement
cut : mesure le nombre d’arêtes qui doivent êtres suprimés pour
isoler les nœuds d’A de ceux de B
rechercher des clusters qui minimisent cut
s’assurer que la taille des clusters est equilibré
créer k > 2 clusters par récurrence

31/43 32/43 33/43

 Introduction Introduction Introduction
Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

Clustering Clustering SCAN

Algorithme Louvain : même principe que min-max, mais en prennant en compte Intuition
la modularité (la densité des arêtes à l’interieur d’une communauté comparé à Deux personnes similaires connaissent les mêmes personnes
celle à l’exterieur de la communauté).
Un groupe de personnes similaires est une communaute (cluster)
Fait partie de la librarie d’algorithmes sur les graphes de Neo4j (APOC) : Distance et similarité
https://neo4j.com/docs/graph-algorithms/current/algorithms/louvain/ Les voisins d’un nœud
N[v ] = {w 2 V |(v , w ) 2 E _ (w , v ) 2 E } [ {v }
... qui content aussi l’algorithme de Tarjan (SCC) :
La distance entre deux nœuds est (v , w ) = p|N[v ]\N[w ]| i.e., le
https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/ |N[v ]|·|N[w ]|
strongly-connected-components/ nombre des voisins communs normalisé par la moyenne geometrique
des tailles de leur voisinage
... ainsi que les mesures de centralité : Les distances entre les nœuds non-adjacents sont infinies
https://neo4j.com/docs/graph-algorithms/current/algorithms/centrality/ N✏ [v ] = {w 2 N[v ]| (v , w ) ✏} où ✏ définit un volume

34/43 35/43 36/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

SCAN SCAN SCAN

Cluster Core
le core (cœur) d’un cluster est l’ensemble des nœuds centraux Connectivité
v est le cœur d’un cluster (not. Core✏,µ (v )) si |N✏ [v ]| µ Deux nœuds qui sont atteignables à partir du même core sont
µ : seuil qui limite le nombre d’éléments per ✏-volume connectés : Connect✏,µ (v , w ) ⌘ 9u : Reach✏,µ (u, v ) ^ Reach✏,µ (u, w )
Atteignabilité Cluster
Tous les nœuds dans le ✏-voisinage d’un cœur sont directement atteignables Tous les nœuds qui sont connectés entre eux font partie du même
cluster : Cluster✏,µ (C ) ⌘ 8v , w 2 C : Connect✏,µ (v , w )
DirReach✏,µ (v , w ) ⌘ Core✏,µ (v ) ^ w 2 N✏ [v ] Clustering
L’ensemble de tous les clusters est un clustering :
L’atteignabilité est la clôture transitive de l’atteignabilité directe
Clustering✏,µ (P) ⌘ P = {C ✓ V |Cluster✏,µ (C )}

Reach✏,µ (v , w ) ⌘ 9u1 , . . . , vn : u1 = v ^ un = w ^ 8i 2 [1, n 1], DirReach✏,µ (vi , vi+1 )

37/43 38/43 39/43

Introduction Introduction Introduction

Composantes Connexes Composantes Connexes Composantes Connexes
Partitionnement d’un graphe Partitionnement d’un graphe Partitionnement d’un graphe

SCAN Algorithme SCAN SCAN

Hub
Un hub est un nœud qui n’est pas dans un cluster, mais qui a des
voisins dans plusieurs clusters d’un clustering
/ C ^ 9X , Y 2 P : X 6= Y ^ X \ Y \ (v ) 6= ;.
Hub✏,µ (v ) ⌘ 8C 2 P : v 2
Outlier
Un outlier est un nœud qui n’est pas dans un cluster, mais qui est t.q
soit tous ses voisins soit font partie tous du même cluster;
soit ses voisins ne font partie d’aucun cluster.

Figure: Algorithme SCAN pour ✏ = 0.7 et µ = 2

40/43 41/43 42/43

 Introduction
Composantes Connexes
Partitionnement d’un graphe

Résumé

mesures graphe : centralité et betweenness centrality; PageRank

composantes connexes : algorithme de Tarjan
graph clustering : mèthodes min-max, SCAN

43/43