Filtrage, partitionnement et visualisation multi-échelles de graphes d’interactions à partir d’un focus

Les réseaux d’interactions jouent un rôle clé dans de nombreux domaines scientifiques. Il s’agit de structures d’information (graphes) mettant en jeu des acteurs et des relations entre ces acteurs. On les rencontre notamment en informatique (graphe du web, réseau internet), en bibliométrie (graphe de citations, graphe de co-auteurs), en sociologie (graphe des relations personnelles ou professionnelles), en biologie (graphe d’interactions de protéines), en géographie ou économie (réseaux de communications ou d’échanges). Les réseaux d’interactions réels sont souvent de nature dynamique. Initialement constitués d’un petit noyau d’acteurs, ils croissent à mesure que de nouveaux acteurs sont connectés. Les acteurs ayant déjà plusieurs connections ont généralement davantage de chance d’être connectés par les nouveaux acteurs (principe d’attachement préférentiel). Il a été montré (Barabási et Albert 1999) que ce processus de croissance entraîne une distribution des degrés proche d’une loi de puissance : peu d’acteurs assurent l’essentiel des relations. Les réseaux ayant cette propriété sont dits « sans échelle ». Ils possèdent souvent un noyau très dense interconnectant l’ensemble des acteurs. Par ailleurs, les réseaux d’interactions issus du monde réel présentent habituellement les deux propriétés « petit monde » (Milgram 1967; Watts et Strogatz 1998) : le diamètre moyen du réseau est faible, et deux acteurs liés ont de fortes chances de partager des relations communes. Les réseaux « petit monde » sont constitués de communautés interconnectées.

Quelle structure construire pour organiser les réseaux d’interactions ? 

L’arbre est une structure naturelle mais « simpliste » pour décrire des graphes « petit monde sans échelle ». Nous proposons de généraliser la structure d’arbre à la structure de graphe « arboré » : il s’agit d’un arbre connectant des communautés de nœuds. Intuitivement, un graphe « arboré » est facilement visualisable (comme un arbre) par un algorithme de dessin de graphe classique. De plus, les communautés ont des chances d’être clairement séparées comme nous le verrons sur des exemples.

Filtre de nœuds basé sur un indice de centralité globale 

Le degré d’un nœud peut être vu comme un indice de centralité locale puisque son calcul ne dépend que du voisinage direct du nœud considéré. Différents indices permettent de définir la centralité globale d’un nœud dans le graphe (Freeman 1979; Bonacich 1987; Friedkin 1991; Brandes 2001; Costenbader et Valente 2003). Il s’agit notamment de la centralité de proximité (closeness centrality), de l’inter centralité (betweenness centrality BC) et de la centralité par vecteur propre (eigen vector centrality) (Brandes et Willhalm 2002).

Définition . La centralité de proximité d’un nœud est définie par la distance moyenne de ce nœud aux autres nœuds du graphe. Dans un graphe « sans échelle » à comportement « petit monde », l’utilisation d’un tel indice permet de filtrer les nœuds en périphérie du noyau central. Cepandant il ne permet généralement pas de dégager des composantes intéressantes dans le noyau.

Définition . L’inter centralité d’un nœud (BC) (Freeman 1979) est la fraction de nombre de plus courts chemins entre deux nœuds passant par le nœud sélectionné.

Filtrage d’arêtes suivant leur coefficient de centralité 

L’inter centralité d’une arête (betweenness centrality BC) (Freeman 1979) peut être utilisée pour séparer des composantes . Une arête à inter centralité forte a des chances d’être centrale dans le graphe (nombreux chemins passent par elles) et de s’apparenter localement à un isthme.

Extraction d’un squelette du graphe 

Extraire un squelette du graphe connexe revient à trouver un graphe simplifié (Reid, Fan et al. 2004) ou un arbre possédant certaines propriétés intéressantes du graphe (Botafogo, Rivlin et al. 1992; Huang, P. et al. 1998).

Extraction d’un graphe squelette

L’algorithme FADE (Quigley et Eades 2000) basé sur un clustering géométrique, propose l’extraction de divers squelettes d’un graphe suivant le niveau de détail choisi . Cette technique s’appuie sur un calcul géométrique à partir du placement. La technique peut être satisfaisante pour un graphe « arboré » . Elle est cependant mal adaptée à la simplification de réseaux « sans échelle » très denses (de type : YEAST ou co-auteurs). En effet, le placement de ces graphes dépend fortement du placement initial.

Extraction d’un arbre squelette 

Dans le cas d’un graphe connexe « sans échelle » à comportement « petit monde », il peut être intéressant d’extraire un arbre couvrant ayant également une distribution des degrés suivant une loi de puissance. Une technique a été proposée (Kim, Noh et al. 2004) pour construire un tel squelette appelé aussi noyau de communication du graphe :

Définition . Le noyau de communication est un arbre couvrant dont l’ensemble des arêtes maximise la somme des indices d’inter centralité.
Algorithme : À l’étape 1, l’arbre T1 est constitué de l’arête de plus fort indice. A l’étape k, l’arête adjacente de plus fort indice ne formant pas de cycle est ajoutée à l’arbre Tk-1. L’arbre couvrant obtenu est « sans échelle » (Kim, Noh et al. 2004). Nous obtenons le même type de résultat empiriquement en utilisant non pas l’indice d’inter centralité mais le degré. Il s’ensuit un gain de performance par économie du calcul de l’indice d’inter centralité.

Filtrage contextuel 

Les techniques de filtrage décrites précédemment sont globales. Il peut être cependant intéressant d’avoir différentes perspectives d’un même graphe dépendant du focus choisi. Nous présentons dans cette section des techniques prenant en compte un focus utilisateur.

Une technique de filtrage contextuelle a été introduite (Furnas 1986) appelée « fisheye généralisé » : considérant un focus donné, le degré d’intérêt (degree of interest : DOI) d’un nœud est défini par son importance a priori et sa distance au focus. La technique de filtrage contextuelle consiste alors à visualiser les nœuds de DOI important. Ce qui permet de relativiser l’importance d’un nœud selon sa distance au focus. Ainsi, un nœud peu important mais proche du focus aura plus de poids qu’un nœud de la même importance mais éloigné du focus. De même un nœud lointain mais important aura peut-être moins de poids qu’un nœud moins important mais proche du focus.

L’objectif du filtre de Furnas est d’assurer une vue détaillée autour du focus tout en gardant le contexte du graphe. Ce filtre sémantique est différent du fisheye graphique de Sarkar (Sarkar et Brown 1992) qui propose une déformation géométrique de la vue autour du focus sans supprimer de nœuds. Le fisheye généralisé de Furnas a été utilisé essentiellement pour visualiser des listes ou des arbres, mais peu de travaux se sont intéressés au filtrage sémantique de graphes. Cela s’explique par une difficulté d’appréhension de la suppression et de l’ajout de nœuds lors d’un changement de focus. Une double technique utilisant un fisheye sémantique et un fisheye géométrique a été développée (Schaffer, Zhenping et al. 1996) pour faciliter la navigation d’un graphe clusterisé. Dans le graphe (Figure 63a), l’utilisateur peut sélectionner un cluster focus pour l’agrandir et avoir un niveau de détail supérieur. Les autres clusters sont alors réduits géométriquement ou sémantiquement.

Table des matières

Introduction générale
Chapitre 1 Graphes
1.1 Définitions préliminaires
1.1.1 Graphes
1.1.2 Connexité
1.1.3 Distances
1.1.4 Arbres
1.2 Modèles de graphes
1.2.1 Graphes aléatoires
1.2.2 Graphes « petit monde »
1.2.2.1 Définitions
1.2.2.2 Construction de Watts et Strogatz
1.2.2.3 Construction de Kleinberg
1.2.3 Graphes « sans échelle »
1.2.4 Nouveau modèle : graphe « petit monde sans échelle »
1.2.5 Nouveau modèle : graphe « arboré »
1.3 Réseaux issus du monde réel
1.3.1 Réseaux « petit monde arborés »
1.3.1.1 Graphe de CiteSeer de taille moyenne
1.3.1.2 Petit graphe de CiteSeer
1.3.1.3 Gros graphe de CiteSeer
1.3.1.4 Graphes des amitiés et sympathies entre étudiants
1.3.1.5 Commentaires sur les graphes « petit monde arborés »
1.3.2 Réseaux « petit monde sans échelle »
1.3.2.1 Graphe de co-auteurs du LIRMM
1.3.2.2 Graphe dual des co-publications du LIRMM
1.3.2.3 Graphe de citations d’InfoVis Contest 2004
1.3.2.4 Graphe d’interactions de protéines – « YEAST »
1.3.2.5 Graphes « petit monde sans échelle » : commentaires
Chapitre 2 Filtrage de graphes
2.1 Choix d’une métrique
2.2 Filtrage de nœuds
2.2.1 Filtrage aléatoire de noeuds
2.2.2 Filtrage de nœuds selon leur degré
2.2.3 Filtre de nœuds basé sur un indice de centralité globale
2.2.4 Filtrage de nœuds basé sur le coefficient de clustering
2.2.5 Filtrage de nœuds – discussion
2.3 Filtrage d’arêtes
2.3.1 Extraction de motifs du graphe
2.3.1.1 Filtrage d’arêtes suivant leur force
2.3.1.2 Filtrage d’arêtes suivant leur coefficient de centralité
2.3.2 Extraction d’un squelette du graphe
2.3.2.1 Extraction d’un graphe squelette
2.3.2.2 Extraction d’un arbre squelette
2.4 Filtrage contextuel
2.5 Nouvelle technique d’extraction conjointe de motifs et squelette
2.5.1 Algorithme
2.5.2 Propriétés
2.5.3 Variantes
2.5.3.1 Variante sans extraction d’arbre couvrant
2.5.3.2 Arbre couvrant reposant sur un focus utilisateur
2.5.3.3 Méthodes mixtes
Chapitre 3 Partitionnement de graphe
3.1 Structures de partitionnement
3.1.1 Etat de l’art
3.1.1.1 Partitionnement simple
3.1.1.2 Graphe clusterisé hiérarchique
3.1.1.3 Graphe composé
3.1.2 Nouvelles structures de partitionnement
3.1.2.1 Arbre d’ensembles
3.1.2.2 Arbre composé simple
3.1.2.3 Arbre composé multi niveaux
3.2 Partitionnement géométrique
3.2.1 Placement du graphe dans un espace euclidien
3.2.1.1 Plongement naturel
3.2.1.2 Réduction du nombre de facteurs – méthode factorielle
3.2.1.3 Placement de graphes utilisant un modèle de forces
3.2.2 Segmentation géométrique par un hyperplan
3.2.3 Segmentation basée sur un calcul d’inertie
3.2.4 Segmentation géométrique par cercle ou sphère
3.2.5 Méthode de partitionnement des centres mobiles
3.2.6 Partitionnement par suppression des arêtes « longues »
3.2.7 Partitionnement géométrique de graphes « arborés »
3.3 Partitionnement basé sur une métrique
3.3.1 Partitionnement ascendant hiérarchique
3.3.2 Partitionnement mixte
3.3.3 Partitionnement descendant par filtrage d’arêtes
3.3.4 Partitionnement avec métrique de graphes « arborés »
3.4 Partitionnement structurel
3.4.1 Partitionnement basé sur un parcours du graphe
3.4.2 Echange de sommets et Min Cut
3.4.3 Méthode de flux
3.4.4 Méthode spectrale
3.4.5 Partitionnement structurel de graphes « arborés »
3.5 Techniques complémentaires
3.5.1 Méthode de recuit simulé
3.5.2 Recherche tabou
3.5.3 Algorithme génétique
3.6 Nouvelles techniques de partitionnement dépendant d’un focus
3.6.1 Arbre de clusters
3.6.1.1 Définitions préliminaires et notations
3.6.1.2 Cluster : ensemble d’articulation du graphe
3.6.1.3 Optimisation du calcul des clusters
3.6.1.4 Description de l’algorithme sur un exemple
3.6.2 Arbre de silhouettes
3.6.2.1 Recouvrement par composantes biconnexes et triviales
3.6.2.2 Partition en silhouettes
3.6.2.3 Relations entre clusters et silhouettes
3.6.3 Arbre de clusters emboîtés
3.6.4 Arbre de silhouettes emboîtées
3.6.5 Optimisation du calcul de contours emboîtés
Chapitre 4 Visualisation de graphes et interaction
4.1 Visualisation de graphes : état de l’art
4.1.1 Les arbres
4.1.1.1 Vue verticale (ou horizontale)
4.1.1.2 Vue radiale
4.1.1.3 Vue 3D
4.1.1.4 Vue hyperbolique
4.1.1.5 Intérêt des surfaces emboîtées
4.1.1.6 Rectangles emboîtés
4.1.1.7 Cercles emboîtés
4.1.1.8 Secteurs angulaires emboîtés
4.1.2 Les graphes
4.1.2.1 Placement radial d’un graphe
4.1.2.2 Algorithmes basés sur un modèle de forces
4.1.2.3 Technique de recuit simulé : optimisation avec contraintes
4.1.2.4 Dessin de graphes acycliques orientés (DAG)
4.1.2.5 Dessin de graphes planaires
4.1.3 Les structures de graphes multi-échelles
4.1.3.1 Vues générales
4.1.3.2 Vues par niveau de partitionnement
4.1.4 Graphes composés orientés
Conclusion générale

Télécharger le rapport complet