Génération itérative de sous-réseaux

Génération itérative de sous-réseaux

Le processus de génération de sous-réseaux de M-QuBE3 est lui-même divisé en trois phases distinctes (Fig. 4.3). Le processus commence par une recherche par mot clé (partie A) afin de sélectionner des sommets. Ces sommets composent l’ensemble focus initial : une liste de sommets de référence permettant de définir une liste de sommets candidats qui seront potentiellement affichés dans le prochain sousgraphe à extraire. Un score est calculé pour ces sommets candidats en considérant les informations sémantiques des données ainsi que la structure du réseau afin d’obtenir une estimation d’intérêt pour l’utilisateur (partie B). A partir de ces scores, un classement est effectué pour déterminer une liste des sommets les plus intéressants (liste des élus) qui sont ensuite utilisés pour extraire le sous-réseau qui sera présenté à l’utilisateur (partie C). Les experts commençant avec un détail et progressant pas à pas, le processus est structuré de manière similaire. Les étapes de sélection et d’extraction peuvent donc être répétées itérativement afin d’explorer les données plus en détail et avec une précision croissante. L’utilisateur interagit avec le sous-graphe extrait en sélectionnant de nouveaux sommets qui lui semblent pertinents. Ces sommets vont venir enrichir l’ensemble focus et ainsi améliorer le prochain sous-réseau. Cet ensemble est conservé à travers les itérations et utilisé pour le calcul du prochain sous-réseau. Nous détaillons dans la suite les différentes étapes suivies pour chaque itération du processus. Dans les parties suivantes, les figures représentant en détail les parties A, B et C (Fig. 4.4, 4.5 et 4.6) sont toutes trois extraites de la figure globale de M-QuBE3 (Fig. 4.7). Les positionnements des éléments au sein des figures sont donc choisis afin de pouvoir être rassemblés dans la figure globale.

 Sélection de l’ensemble focus

Comme énoncé précédemment, l’ensemble focus est l’ensemble des sommets sélectionnés par l’utilisateur. Dans un premier temps, il doit être initialisé ou être mis à jour. S’il s’agit de la première itération, l’ensemble focus (Fig. 4.4, A3) est défini par une recherche par mot clé d’un ou plusieurs sommets (A1). Ensuite, entre chaque nouvelle itération, l’ensemble focus est modifié par l’ajout ou la suppression de sommets par l’utilisateur (A2). Les voisins de chaque sommet de l’ensemble focus (A4) composent ensuite un ensemble appelé la liste de candidats (voir section suivante : Fig. 4.5, B2). Cette liste contient les sommets potentiellement montrés dans le prochain sous-réseau extrait, en fonction de l’estimation d’intérêt calculée dans le partie B. Cette liste de candidats est amenée à évoluer au cours de processus. La prochaine phase est le calcul des différentes métriques utilisées pour déterminer le score d’intérêt final. 

Calcul d’intérêt 

La phase de calcul d’intérêt détermine un score (Fig. 4.5, B7) représentant l’intérêt de l’utilisateur pour un sommet donné n. Plus le score est élevé, plus la probabilité que le sommet n soit sélectionné et montré à l’utilisateur dans le prochain sous-réseau est grande (Fig. 4.6, C6). Le score final est une métrique définie à partir de plusieurs scores. Premièrement, un score directement lié à la volonté utilisateur, l’eScore (B3), ainsi qu’un score défini en fonction de la position des sommets dans le réseau, pScore (B4), sont calculés. Ces deux scores sont ensuite combinés en un score pondéré, le wScore (B5). Le score final est finalement obtenu en prenant en compte les scores des voisins (B3’ à B5’) à travers un calcul de diffusion de l’intérêt (B6). eScore (B3). L’eScore (exploratory Score) est une métrique d’estimation de l’intérêt calculée pour tous les sommets dans la liste de candidats (B1). L’objectif est de représenter la volonté générale de l’utilisateur notamment les contraintes et les objectifs à prendre en compte lors de la recherche. Lors d’une première utilisation de M-QuBE3 sur un nouveau jeu de données ou en cas d’objectifs imprécis ou encore non-définis de la part de l’utilisateur, il est tout à fait possible d’utiliser des métriques communément utilisées en sciences humaines et sociales (comme les exemples énoncés dans les travaux de Mainas [54] appliqués aux réseaux criminels). Notre solution spécialisée d’eScore pour les réseaux multi-couches est présentée dans la section 5.2 du chapitre 5 pour adapter précisément M-QuBE3aux réseaux issus des sciences humaines et sociales. pScore (B4). L’utilisateur interagit avec le processus en sélectionnant des sommets à chaque itération (Partie A, Fig. 4.4). Nous supposons que les sommets proches d’un sommet sélectionné dans le graphe ont plus de chances d’être considérés comme intéressants par l’utilisateur. A cette fin, la sélection de l’utilisateur constitue ce que nous appelons une zone focale et un sommet inclus ou proche de cette zone est pondéré positivement (voir le calcul du score pondéré ci-dessous). Pour ce faire, une fonction basée sur le centroïde est utilisée pour calculer la distance moyenne entre le sommet évalué x et les sommet de l’ensemble focus, déterminant ainsi sa position dans la zone focale. 

Extraction du sous-réseau 

Cette phase commence par le calcul de la liste des sommets choisis (Fig. 4.6, C3). Cette liste contient les sommets sélectionnés dans la liste des candidats pour composer le nouveau sous-réseau. Les sommets sélectionnés par l’utilisateur sont automatiquement dans la liste des sommets choisis. La finalité du processus complet est donc de remplir la liste des sommets choisis en fonction des scores obtenus afin d’avoir un sous-réseau d’intérêt optimal pour l’utilisateur. Un classement des sommets est effectué en utilisant les scores finaux des phases précédentes (C1) et le sommet ayant le score le plus élevé est ajouté à la liste des sommets choisis (C2). Si le nombre de sommets présent dans la liste des sommets choisis correspond au nombre souhaité par l’utilisateur (C4), on extrait le sousréseau composé des sommets de la liste et des liens présents entre ces sommets dans le réseau initial (C6).Si le nombre de sommets n’est pas suffisant, les sommets voisins du dernier sommet choisi sont ajoutés, s’ils n’y sont pas déjà (C5), à la liste des candidats. La mise à jour de la liste de candidats requiert alors que les nouveaux sommets n’ayant pas encore de scores soient traités. La procédure est alors répétée depuis B1. Les scores des sommets précédemment traités n’ont néanmoins donc besoin d’être ré-évalués car leurs scores ne subiront aucun changement. 

Processus de génération complet 

Une fois ces phases complétées (Fig. 4.7), un sous-réseau est généré. L’utilisateur peut alors sélectionner de nouveaux sommets qui lui semblent pertinents dans ce sous-réseau pour réitérer le processus depuis le début. Le processus complet recommence alors entièrement avec un nouvel ensemble focus enrichi des nouvelles sélections et dé-sélections de l’utilisateur (A2). De nouveaux scores sont calculés engendrant ainsi un nouveau sous-réseau sémantiquement plus proche des nouvelles indications de l’utilisateur. Cette procédure est réitérée jusqu’à satisfaction de l’utilisateur vis à vis des sous-réseaux obtenus. La répétition de ces étapes permet de générer des sous-réseaux se succédant. Il est néanmoins nécessaire de rappeler que chaque sous-réseau est extrait du graphe initial et généré à partir des sélections utilisateurs provenant d’un sous-réseau père. Chaque sous-réseau ayant alors un sous-réseau père mais potentiellement plusieurs sous-réseaux fils, cette succession n’est pas linéaire et il est alors nécessaire de proposer un moyen de représenter et d’utiliser cette arborescence de sous-réseaux. 

Arbre de traces 

La méthodologie de travail de nos experts est éminemment arborescente : lorsqu’une piste d’analyse est suivie, il est fréquent que de nouvelles opportunités apparaissent et ouvrent la voie à de nouvelles pistes à explorer. La méthode M-QuBE3 suit cette méthodologie en proposant à l’expert d’utiliser un “arbre de traces” interactif, inspiré par la notion d’“history tree” [14, 71]. Chaque action effectuée par l’utilisateur (sélection/dé-sélection d’un sommet, augmentation/diminution du nombre de sommets requis par sous-réseau ou changement de l’algorithme de positionnement des sommets) génère une “trace” dans l’arbre i.e. un sommet représentant le sous-réseau résultant de cette action. Ce sommet est lié à son père (le sous-réseau sur lequel on a effectué l’action) par une arête dont le type représente l’action effectuée (sélection, augmentation, positionnement). Cet arbre ne se contente pas d’être descriptif mais propose à l’utilisateur un système de navigation entre tous les sous-réseaux obtenus. Lorsque l’utilisateur clique sur un sommet de l’arbre de trace, le sous-réseau correspondant est sélectionné et affiché. Toute nouvelle action de la part de l’utilisateur va alors générer un sous-réseau dont le père est le sous-réseau sélectionné, permettant ainsi la création d’une nouvelle branche sur l’arbre de trace (Fig. 4.8). Ce mécanisme fait ainsi écho à la méthode de travail des experts en permettant de suivre et développer plusieurs pistes simultanément et a donc été particulièrement bien accueilli par les experts des données. Pour rendre cela possible sans pertes de performance et sans duplication de données entre les sous-réseaux, nous utilisons la structure de données Tulip [3] basée sur une hiérarchie de graphes. Ceci s’ancre dans la continuité des travaux commencés avec Porgy [66] dont le fonctionnement est aussi basé sur un graphe de graphes assuré par le modèle de données Tulip. Des informations supplémentaires quant à l’implémentation, l’emploi et les retours utilisateurs sont disponibles dans le chapitre 5.