User Tools

Site Tools


sdasilva_cbadiola:samuel_da_silva_clement_badiola

Bordeaux roadmap / Samuel Da Silva & Clément Badiola's corner

Le code source relatif au projet est disponible en suivant ce lien.
Le projet au format Tulip est disponible en suivant ce lien.
La présentation du projet est disponible en suivant ce lien.

Problème

Le problème que nous souhaitons étudier ici concerne la reconstitution d'une hiérarchie au sein d’une entreprise ou d’un organisme à partir d’un ensemble spécifique de données.

Est-il possible, à partir de données, de reconstruire la hiérarchie d’une institution ?

Cette question en soulève naturellement d'autres :

  • Est-il possible de pouvoir identifier et visualiser des groupes grâce à ces données ?
  • Peut-on identifier des équipes de projets, des clients ?
  • Peut-on, grâce à la visualisation, permettre une analyse des relations entre acteurs et mettre en exergue des facteurs de corrélations caractéristiques de ce type de problème ?
  • Des représentations visuelles peuvent-elles aboutir à un résultat pertinent pour ce type de problème ?

Notre problématique et les questions difficiles qui en découlent font encore l'objet de travaux de recherches de nombreuses équipes de spécialistes. Nous savons que les résoudre représente un défi probablement hors de portée pour un délai aussi court, mais ce champs de recherche est riche de possibilités et nous permet de faire face à des problématiques de la recherche actuelle.

Données

Le moyen de communication principal des organismes étant le mail, notre axe de recherche s’oriente à terme vers l’analyse visuelle des modèles de correspondances par courrier électronique.

En supposant que les équipes s'échangent de nombreux mails en interne et qu'un responsable se charge de la transmission à la hiérarchie et aux clients, nous pouvons imaginer que des ponts seront formés entre équipes internes, clients et supérieurs hiérarchiques. Chaque entité pourrait former des groupes. Les groupes pourront représenter des clients (groupes relativement isolés) ou des équipes de projet (groupes constitués d'un nombre de nœuds relativement important). Les supérieurs hiérarchiques formeront probablement un groupe à part, avec beaucoup de connexions entrantes.

Afin d’apporter des réponses à notre problème, nous avons donc choisi pour ensemble de données un réseau généré à l’aide de données de messagerie à partir de l'entreprise ENRON et préparé dans le cadre du projet CALO. L'ensemble de données a été à l'origine rendu publique et mis en ligne par la Federal Energy Regulatory Commission durant son enquête dans le cadre de la faillite d'Enron en 2001. Il a ensuite été racheté par Leslie Kaelbling du MIT et s'est avéré plein de problèmes d'intégrité. L'ensemble de données a été nettoyé une première fois. Des adresses invalides ont été transformées de manière à être exploitables, mais des erreurs subsistent, rendant l'exploitation du jeu de données encore difficile.

Le jeu de données retenu est donc « Enron Email Dataset »1), données téléchargées sur le site http://www.cs.cmu.edu/~enron/ 2).

Structure

Nous disposons d’un ensemble de données récoltées durant une période s’étendant d’octobre 2003 à 2005, sur 18 mois.

Le jeu de données est composé, entre autres, d'un demi million de mails échangés entre plus de 150 acteurs.

L'ensemble de données demande un gros effort d'analyse, car il n'est que très peu documenté. Les informations qui suivent ont été tirées de nos observations.

Chaque employé Enron est représenté par un dossier, qui contient tous les fichiers associés à sa boite mail. Ces fichiers peuvent être des mails, mais aussi des notes ou des filtres de mails. Un employé Enron peut disposer d'un nombre arbitraire de dossiers et de fichiers dans sa boite mail. Un dossier de mails contient des fichiers numérotés, chacun représentant un mail, classés par date de création.

Voici un exemple d'arborescence de fichiers :

Les informations que nous exploitons dans les mails sont les suivantes : - Date d’envoi ou de réception - Expéditeur - Destinaire(s)

Tous les employés Enron ne sont pas directement représentés, car certains ont été retirés de la base de données à leur demande.

Nous disposons de données partielles et parfois erronées. Leur exploitation est rendue difficile à cause de la détection de nouvelles erreurs dont l'origine est souvent inconnue.

Traitement des données

Nous avons vu précédemment que les mails sont répartis arbitrairement par les employés dans leurs boites mails. En effet, certains employés redirigent certains mails dans des dossiers spécifiques. De plus, certains employés possèdent des mails redirigés, vides ou erronés. Pour associer les bonnes données à la bonne personne, il faut donc éviter ces fichiers et dossiers spécifiques. Cependant, supprimer ces informations représenterait une perte d'éléments à traiter par la suite.

Nous avons donc noté les dossiers sans risques, mais nous n'avons pas traité la base de données préalablement.

Travail réalisé

Pour obtenir des résultats, nous avons réalisé plusieurs traitements en séquence :

  1. Traitement et affinage des données brutes.
  2. Calcul de métriques sur les données raffinées et sur le graphe brut résultant.
  3. Calcul d'un visuel sur le graphe brut.

Traitement et affinage des données

Rappelons tout d'abord que nous nous intéressons aux mails envoyés par chacun des employés d'Enron présent dans la base de données. Ces mails sont stockés dans un dossier sent_items ou dans un dossier sent. Certains employés possèdent les deux dossiers à la fois.

Voyons le cheminement suivi pour obtenir un ensemble de données exploitables par Tulip :

  1. Pour chaque employé, nous constituons une liste de mails envoyés.
  2. Pour chaque mail de la liste d'un employé :
    1. nous récupérons l'adresse d'expédition, la ou les adresse(s) de réception, la date.
    2. Pour chaque adresse de réception :
      1. nous construisons une paire (destinataire, date d'envoi) associée à l'employé expéditeur 3).
    3. nous associons l'adresse d'expédition à l'employé. 4)
    4. nous traitons les adresses d'expédition et de destination pour les intégrer au graphe avec leurs relations de correspondance.
  3. Si un employé possède plusieurs adresses, nous les relions par un trait rouge.
  4. Pour chaque employé, nous calculons le temps moyen mis par ses mails pour obtenir une réponse.
Lecture d'un fichier mail

L'analyse des fichiers de mail est effectuée à l'aide de la classe HeaderParser importée du module email.parser de Python. Cette classe utilise en entrée des fichiers ou des mails représentés sous forme de texte stocké en mémoire. L'entrée doit respecter la norme RFC2822 ou l'extraction des information à partir du mail peut poser problème 5).

Voici un exemple d'utilisation de HeaderParser :

from email.parser import HeaderParser
 
inputMail = open(pathToParse+file, 'rb')
msg = HeaderParser().parse(inputMail)
 
expeditor = msg['From'].strip()
recipients = msg['To'].split(',')


Un mail qui ne respecte pas la norme RFC2822 peut produire des résultats incohérents. Pour éviter certains désagréments, nous vérifions le type d'élément renvoyé :

if type(msg['To']) is str:
    # msg['To'] is OK
else:
    # msg['To'] contains errors


Le traitement des dates est particulier puisqu'il faut prendre en compte le fuseau horaire et les réglages de chaque machine impliquée.

Voici notre solution pour obtenir des dates au format standard :

from email.utils import parsedate_tz
from email.utils import mktime_tz
from datetime import datetime
 
def extractDateFromMsg(msg):
    date = None
    date_str = msg['Date']
    if(date_str):
	date_tuple = parsedate_tz(date_str)
	if date_tuple:
	    date = datetime.fromtimestamp(mktime_tz(date_tuple))
    return date
Comptes mails multiples

On trouve des mails partagés dans le cas d'un directeur qui veut s'exprimer au nom de la direction. On peut également obtenir un mail différent au bout d'un certain temps passé au sein de l'entreprise, lors d'une promotion ou sur simple demande de l'employé.

Ceci amène les employés à disposer de plusieurs adresses mails, et à partager certaines adresses avec d'autres employés. Nous prendrons donc en compte toute les adresses d'un utilisateurs afin de ne pas perdre d'informations le concernant. Cependant, nous verrons par la suite que les mails multiples engendrent une dilution des statistiques sur l'utilisateurs puisque les statistiques sont calculés sur une adresse mail particulière. Ainsi donc, un utilisateur ayant 3 adresses mails différentes aura 3 statistiques différentes pour chacun de ses compte mails, ce qui bien sûr fausse la valeur réel de l'utilisateur qui s'en voit proportionnellement dilué en fonction du nombre d’adresse mail qu'il possède. Nous verrons par la suite comment nous avons fait face à ce problème.

Intégration des adresses au graphe Tulip

Nous avons choisis de représenter les échanges de mail sous la forme d'un graphe à l'aide de l'outil Tulip. Pour cela, nous représentons chaque compte mail par un noeud et si l'utilisateur i a communiqué avec l'utilisateur j en lui envoyant un mail alors nous ajoutons au graphe une arrête allant de i vers j. Le processus de création du graphe se fait en deux temps : traitement de l'expéditeur, puis traitement des destinataires d'un mail.

Voici le prototype de la fonction qui fait ce traitement :

def register(self, expeditor, recipients, person):


En entrée, nous avons l'adresse d'expédition, les potentiels destinataires et l'identifiant de l'employé Enron qui a envoyé le mail.

Nous commençons par vérifier que l'adresse d'expédition n'est pas déjà contenue dans le graphe Tulip. Si ce n'est pas le cas, nous l'y ajoutons, puis nous incrémentons le compteur de mails envoyés de l'adresse d'expédition de longueur(liste_destinataires) :

#Traitement de l'expediteur
flag = False
expeditor = expeditor.strip()
for nodes in self.g.getNodes():
    if expeditor == self.names[nodes]:
    flag = True
    expeditorNode = nodes
    break
if not flag:
    node = self.g.addNode()
    expeditorNode = node
    self.names[node] = expeditor
self.sentMails[expeditorNode] = self.sentMails[expeditorNode] + 1


Le traitement des adresses de destination s'effectue sur chaque élément de la liste de destinataire de manière similaire au traitement de l'adresse d'expéditeur. Le compteur des mails reçus pour chacune des adresse est augmenté à la fin du traitement. On prend bien garde à ne pas compter les adresses de destinations identiques aux adresses d'expédition pour éviter les cycles problématiques sur un noeud :

self.receivedMails[receptorNode] = self.receivedMails[receptorNode] + 1 


Pour éviter la duplication des connections entre adresses mail, nous vérifions systématiquement qu'une connection n'existe pas déjà avant de tenter d'en créer une nouvelle :

edge = self.g.existEdge(expeditorNode, receptorNode)
if not edge.isValid():
    self.g.addEdge(expeditorNode, receptorNode)

Au terme de cette étape de calcul, nous disposons d'un graphe Tulip exploitable par la plupart des algorithmes utilisés par la suite.

Calcul du temps moyen de réponse

Le temps moyen de réponse pour une adresse mail X est le temps mis en moyenne pour que chaque mail envoyé depuis X obtienne une réponse. Ce critère constitue une partie du score social d'une personne, permettant de la placer dans la hiérarchie d'Enron.

Il nécessite un traitement lourd car pour un mail donné envoyé, nous devons vérifier toutes les correspondances possibles de mails dans les dossiers de mails envoyés des personnes destinataires. Le temps de traitement augmente avec le nombre de mails envoyés et le nombre de destinataires.

Voici le prototype de la fonction qui calcule le temps moyen de réponse d'une personne :

def computeResponseTime(self, person):


person représente l'identifiant d'un employé Enron, et peut donc être associé à plusieurs adresses mails dans le cadre de l'utilisation de plusieurs comptes mails.

Nous considérons qu'une réponse à un mail peut arriver sur une autre adresse que celle utilisée d'origine pour initier la correspondance. Dans un premier temps, nous récoltons donc toutes les adresses utilisées par l'employé considéré :

for mail in self.peer:
    if self.peer[mail] == person:
	guyMails.append(mail)


Pour chaque mail envoyé, nous voulons trouver les réponses obtenues, mais seulement si la réponse provient d'un employé Enron :

for pair in self.users[person]["sent_list"]:
    # If the destination mail has an enron employee associated to itself.
    if self.peer.has_key(pair[0]):


Nous avions stocké auparavant les associations adresses mails - employés Enron dans la variable de classe peer. Maintenant, nous souhaitons parcourir les mails envoyés par les personnes destinataires du mail précédant :

for p in self.users[self.peer[pair[0]]]["sent_list"]:


Puis nous cherchons un mail qui constitue une réponse 6) et s'il est trouvé, alors le temps de réponse est mis à jour :

if p[0] in guyMails:
    # Computations on dates. If the gap is more than self.d, then this is not considered a response to our previous mail.
    if p[1] > pair[1]:
	delta = p[1] - pair[1]
	if delta <= self.d:
	    delta_cpt = delta_cpt + 1
	    self.users[person]["response_time"] = self.users[person]["response_time"] + delta.total_seconds()


Enfin, la moyenne des temps de réponse est calculée et le score est reporté sur les différentes adresses utilisées par l'employé considéré :

if delta_cpt > 0:
    self.users[person]["response_time"] = self.users[person]["response_time"] / delta_cpt
    for adr in guyMails:
	for node in self.g.getNodes():
	    if adr == self.names[node]:
		self.avgResponseTime[node] = self.users[person]["response_time"]
Un premier résultat

A ce stade du projet, nous avons donc réussit à créer un graphe représentant les échanges de mails entre les différents employés de la société Enron et les échanges de mails des employés Enron avec le monde extérieur. Nous aurions pu ignorer les échanges avec le monde extérieur mais nous pensons que ces échanges contribuent à déterminer l'importance d'une personne. En effet, un simple employé communique souvent simplement en interne avec les autres employés Enron tandis qu'un manager ou un président de société aura davantage de contact avec l'extérieur de l'entreprise (prise de contact avec les fournisseurs, les clients ect…). De plus, si une personne communique avec un client extérieur détecté comme “important” (c'est à dire un client qui reçoit par exemple beaucoup de mail de la part d'un haut gradé de la hiérarchie enron), nous pouvons alors penser que cette personne aura des chances d'être un acteur important de la société car ce sont souvent les employés les plus haut placés de la hiérarchie qui communique avec les plus gros clients).

Ainsi donc, grâce à un premier algorithme tel que l'algorithme “Balloon (OGDF)” de Tulip, nous avons pu obtenir un premier visuel permettant d'identifier par exemple les personnes de chez Enron qui communiquent le plus avec l'extérieur. Nous obtenons donc une série de cercle où le centre du cercle représente un employé de chez Enron et le contour du cercle représente les personnes extérieurs à la société, des clients par exemple. Ce graphe est composé de 14367 noeuds et 28636 arêtes.

Afin de pouvoir avoir une première analyse des résultats, nous avons fait des recherches sur les employés Enron qui apparaissent au centre des cercles du graphe, donc les personnes qui communiquent le plus avec l'extérieur. Nous avons donc constaté que ces personnes faisaient partie du haut de la hiérarchie Enron (Vice Président, CEO, Manager,Director). Ainsi donc, ce constat a confirmé notre hypothèse et notre choix de garder les échanges avec le monde extérieur.

Fusion des noeuds

Nous avons vu précédemment qu'un employé Enron pouvait disposer de plusieurs adresses mail, soit des adresses mails secondaires, soit des adresses mails partagées avec d'autres. Comme nous pouvons le voir sur le graphe ci-dessous représentant les mails envoyés par M. Lavorato (employé Enron), notre algorithme de construction de graphe ajoute une arête rouge d'un compte email vers un autre si un employé utilise des adresses mails différentes pour envoyer ses messages.

Afin de palier à ce problème, nous avons décider de fusionner les comptes mails appartenant à une même personne, pour cela nous avons donc implémenté un algorithme de fusion de noeuds. Nous avons également pris soin de prendre en compte les adresses mail partagées. En effet, si une adresse mail est partagée entre plusieurs personnes, il ne faut pas faire de fusion, sinon toutes les personnes utilisant ce mail en commun se verraient fusionnées en un seul noeud.

Notre algorithme va alors parcourir tous les noeuds du graphe, et dès qu'il trouve un noeud avec une arête entrante rouge, il va alors procéder à la fusion du noeud source de l'arête avec le noeud sur lequel on se trouve. On prendra évidement le soin de vérifier que l'on est pas sur un noeud partagé et que le noeud que l'on veut fusionner n'en n'est pas un non plus. Enfin, pour fusionner deux noeuds, nous redirigeons l'intégralité des arêtes du noeud distant à fusionner sur le noeud courant vers lequel doit avoir lieu la fusion.

Grâce à cet algorithme de fusion, nous avons donc pu mettre en commun les différentes adresses mails appartenant à une même personne et donc ainsi éviter la dilution des statistiques sur les utilisateurs (statistiques que nous verrons plus loin). De plus, nous avons pu identifier visuellement une anomalie dans les mails, en effet, lorsque nous affichions seulement les arêtes rouges du graphe, nous nous sommes aperçu qu'il n'y avait qu'une seule adresse mail partagée, une adresse portant le nom de no.adress@enron.com.

Après quelques recherches sur Internet concernant cette adresses curieuse, nous avons lu que toutes les adresses de la bases Enron qui avaient été supprimées (pour raison de confidentialité ou adresse manquante) avaient été remplacées par l'adresse mail no.adress@enron.com. Ainsi donc, nous avons modifié notre parser pour qu'il ignore les emails portant l'adresse “no.adress@enron.com”. Après avoir implémenté ce filtre, nous avons ré-appliqué le même procédé et nous avons constaté qu'il n'y avait plus d'adresse mail partagée entre plusieurs utilisateurs mais seulement des adresses multiples possédées par une même personne. Grâce à la visualisation des données, nous avons donc pu investiguer sur ces différents points.

Calcul des métriques sociales

Chaque acteur influe sur le réseau à sa manière, avec plus ou moins d'impact. Certaines influences sont quantifiables et calculables grâce aux modèles qui en découlent. La difficulté majeure consiste à identifier ces modèles pour ensuite les exploiter et les vérifier.

L'exploitation des modèles de communication permet de déterminer automatiquement les caractéristiques suivantes :

  • Employés occupant une place majeure au sein de l'entreprise.
  • Groupes de rangs similaires et interactions entres groupes.
  • Interactions entre acteurs spécifiques d'un ou plusieurs groupes.

Nous calculons des métriques sociales pour chaque acteur du réseau et nous les normalisons ensuite pour pouvoir comparer et classer les différents acteurs grâce à ces métriques.

Pour classer les acteurs par ordre d'importance, nous calculons deux types de métriques.

Premièrement, nous collectons des données basées sur les flux d'informations, données de volume et de temps. Nous calculons le nombre de mails qu'un utilisateur a envoyé et reçu. Nous calculons également le temps de réponse moyen, c'est-à-dire le temps moyen mis par un mail envoyé pour recevoir une réponse. Le code pour ces calculs est décrit dans la partie “traitement et affinage des données”.

Deuxièmement, nous récoltons des données sur la nature des connections au sein du réseau de communication. Nous classons les utilisateurs en basant notre analyse sur les cliques maximales du graphe. Nous calculons le degré des noeuds et leur centralité. Nous pouvons déterminer quel acteur appartient au plus de cliques, quel acteur est dans les plus grandes cliques, et quel acteur est dans les cliques les plus importantes.

Les flux d'information

Nous considérons que le volume de mails échangés peut contribuer à la définition de l'importance d'un acteur au sein du réseau de communication, car un acteur qui communique beaucoup devrait, dans le cas général, occuper une place plus ou moins importante au sein du réseau. Nous calculons simplement ces statistiques au fur et à mesure du traitement de la base des données brutes, et ce pour chaque utilisateur.

De plus, nous supposons qu'un utilisateur i qui reçoit des réponses rapides de la part d'un utilisateur j doit être important par rapport à l'utilisateur j. Pour simplifier le problème, nous généralisons en faisant l'hypothèse qu'un utilisateur i ayant une moyenne de temps de réponse faible (donc des réponses rapides) sera une personne importante vis-à-vis de tous les autres employés. En d'autres termes, un utilisateur qui reçoit des réponses rapidement occupera probablement une position importante au sein de la hiérarchie de l'entreprise.

Les indicateurs structuraux

Nous disposons pour cette étape d'un graphe de relations brut où un noeud représente une adresse et où un arc i→j représente une communication établie originant de i et à destination de j.

Nous utilisons un algorithme basé sur une adaptation du travail de Bron et Kerbosch, l'algorithme 457, implémenté dans la librairie NetworkX, pour trouver la liste des cliques maximales de notre graphe. Cet algorithme travaillant habituellement sur un graphe en liste d'adjacences et ne disposant pas d'un tel graphe, nous avons dû fournir un effort d'adaptation important pour le rendre fonctionnel sur nos structures de données.

Ensuite, pour chaque utilisateur, nous déterminons les scores suivants :

  • Le nombre de cliques touchées, c'est à dire dans combien de clique l'utilisateur se trouve
  • Le score de clique, où pour chaque clique touchée, plus la clique est grande, plus le score augmente (le score utilisateur sera donc la somme des scores de clique dans lesquels il se trouve)
  • Le score de clique influencé, où le volume de mail échangé et le score de temps moyen de réponse de chaque membre de la clique sont pris en compte


Le score de clique R est calculé selon la formule suivante :

R = 2n-1

où n est le nombre d'utilisateurs contenus dans une clique.

Le score de clique influencé W est quand à lui calculé selon la formule suivante :

W = t.R

où t est le score du temps de réponse donné à l'utilisateur pour lequel on calcul W.


Par la suite, nous calculons les critères supplémentaires suivants sur notre graphe des relations de communications :

  • Le degré de chaque noeud : On calcule ici l'activité d'un noeud en se basant sur l'hypothèse que plus un acteur est central, plus il est “actif”
  • Le coefficient de clusterisation grâce à l'algorithme clusteringCoefficient de Tulip : Nous allons ici étudier la tendance des acteurs à se regrouper, une “tendance à la grégarité” (= vivre et évoluer en groupe). Pour mieux comprendre, imaginons que deux employés Enron communiquent tous les deux avec une troisième personne. Nous allons alors regarder si par hasard ces deux personnes ne se connaissent pas ( = échange des mails).
  • Centralité de proximité (closeness) donnée par le plugin Eccentricity de Tulip : on va ici calculer la moyenne de la plus courte distance entre chaque paire de noeud pour un noeud donné. Cela va nous permettre de déterminer la distance qui sépare un acteur et tous les autres acteurs du graphe. On va alors avec cette métrique mesurer le nombre minimum de pas qu’un acteur doit effectuer pour entrer en contact avec les autres acteurs du système. De ce point de vue, plus un acteur est central, plus il est « proche » des autres, plus il entre vite en contact ou interagit facilement avec eux. On peut interpréter cela comme une mesure d’autonomie, d’indépendance à l’égard du contrôle exercé par d’autres.
  • Le score de Centralité d’intermédiarité (betweeness) de chaque noeud : On calcule ici le nombre de fois qu'un noeud sert d'intermédiaire ou de pont lors du calcul des plus courts chemins entre un noeud et tous les autres noeuds du graphe. En effet, lorsque deux acteurs ne sont pas adjacents, ils dépendent d’autres acteurs du groupe pour leurs échanges, il faut un intermédiaire pour joindre les deux bouts. Cette métrique va donc nous permettre de répondre à la question : Est ce qu'il y a un flux d'échange important qui me traverse, suis-je central à ce flux ?
  • Les scores d'autorité et de hub fournis par notre adaptation de l'algorithme HITS de Jon Kleinberg que nous expliquons en détail dans la partie suivante.
Le calcul du score de HITS

L'algorithme de Jon Kleinberg, connu sous les noms de Hyperlink-Induced Topic Search ou hubs and authorities, permet de calculer deux caractéristiques pour des pages web : le hub et le authority.

Une page avec un bon score de hub pointera vers de nombreuses “bonnes” pages. Une page avec un bon score de authority, considérée comme une “bonne” page, aura beaucoup de liens pointant vers elle. De façon analogue, nous avons décidé d'appliquer cet algorithme sur notre graphe, les pages étant alors ici remplacées par des personnes et le pointage des liens par un échange de mail, est ce que j'envoie des mails à des personnes importantes ? Est ce que je reçois des mails de la part de personnes importantes ?

Pour un noeud, on calcule ses scores de HITS en initialisant les scores de chaque noeud du graphe considéré à 1/nb_noeuds. Ensuite, on applique les étapes suivante :

  1. Mettre à jour le score d'autorité
  2. Mettre à jour le score de hub
  3. Normaliser les scores
  4. Répéter les étapes précédentes

L'algorithme HITS recalcule ses deux scores itérativement indéfiniment et ne garantit pas la convergence de ces valeurs.

Il était donc nécessaire d'y apporter quelques modifications que nous vous présentons à l'aide de notre code Python.
Commençons par le prototype de la fonction :

def hits(graph, auth, hub, max_iter=100, tol=1.0e-8):


On limite le nombre d'itérations (par défaut 100) et on définit une valeur de tolérance pour la convergence (par défaut 1.0e-8).
On initialise ensuite les scores des noeuds :

for n in graph.getNodes():
    auth[n] = hub[n] = 1.0 / graph.numberOfNodes()


Puis on itère indéfiniment pour appliquer les traitements de mise à jour des scores, normaliser ces scores et vérifier la convergence.

Pour normaliser les valeurs, nous utilisons la formule norme = 1.0/somme(scores), où scores désigne la valeur à normaliser de chaque élément considéré. Ensuite, le score de chaque élément est multiplié par norme.

Pour vérifier la convergence, nous comparons les valeurs dernièrement calculées aux valeurs précédentes :

for n in graph.getNodes():
    err = err + abs(hub[n] - hublast[n])


Si err est inférieur à notre valeur de tolérance, alors le calcul est terminé. Sinon, si le nombre d'itération est supérieur à max_iter, une exception est levée et le calcul est stoppé. Dans tous les autres cas, le calcul continue.

Normalisation des données

Les scores sont tous calculés sur leur propre échelle de valeur. Avant exploitation, ils sont normalisés pour s'insérer dans une échelle de valeurs allant de 0 à 100.
Voyons le prototype de notre fonction Python :

def NormalizeMetricValue(graph, metric):


Nous calculons un minimum et un maximum sur la métrique passée en argument, puis nous normalisons de la manière suivante :

for n in graph.getNodes():
    normalizedValue = (100 * ((metric.getNodeValue(n) - min) / (max - min)))
    metric.setNodeValue(n, normalizedValue)
Le score social

Nous voilà rendu à la fin de notre projet dont le but était de réussir à trouver les acteurs les plus importants de la sociétés Enron, ses acteurs principaux, les piliers de la société. Peut-t-on réussir à trouver et à identifier dans une base de donnée gigantesque d'échanges de mails les acteurs les plus haut placés de la hiérarchie Enron ? Après avoir calculé un total de 10 métriques différentes qui nous semblaient significatives et pertinentes pour notre étude, nous avons calculé pour chaque noeud, c'est à dire pour chaque acteur du graphe, son score social, c'est à dire, sa valeur d'importance en tant qu'acteur.

Le score social est une valeur calculée sur une échelle de 0 à 100 qui résulte de la combinaison avec facteurs (la moyenne) des métriques auparavant calculées :

  • du nombre de mails échangé
  • du temps de réponse moyen
  • des différents scores de clique
  • du degré
  • du coefficient de clusterisation
  • des calculs sur la centralité
  • du hub/authority.

Chacune de ces métriques peut être pondérée en fonction de son importance et de son rôle (par exemple, selon nous, le nombre de mails échangés n'est pas l'élément le plus significatif contrairement à la centralité ou au coefficient de clusterisation, qui nous semblent beaucoup plus représentatifs et plus juste en terme de jugement).

Ainsi donc, plus une personne aura un score social important (score normalisé sur une échelle de 0 à 100), plus elle occupera une place élevée dans la hiérarchie de l'entreprise.

Analyse des résultats intermédiaires

Afin d'avoir une première analyse de nos résultats, nous avons sélectionné les 10 employés avec le plus haut score social et nous avons fait des recherches sur ces personnes là afin de connaître leur réel valeur dans l'entreprise. Les résultats de cette analyse ont été plutôt positifs puisque nous avons retrouvé dans ce top 10 les employés ayant le statut de CEO, Président, Vice président etc.. Cependant, nous avions quelques parasites, des employés qui ne devaient pas être dans ce top 10 et des Président qui se retrouvaient un peu trop bas dans la hiérarchie. Bien que nous ayons obtenu des résultats plutôt cohérents, nos calculs devaient être affinés, il fallait donc pondérer correctement nos métriques afin d'avoir le meilleur résultat possible.

Afin de pondérer au mieux nos métriques, nous nous sommes tout d'abord demandé si toutes notre métriques allaient dans un même sens, c'est à dire, est ce que chacune de nos métriques vont globalement dans le sens du résultat final ou au contraire, est ce que nous avons des métriques qui n'ont pas de lien avec le résultat final. Nous avons alors fait un scatter plot de toutes les métriques calculées avec le score social obtenu.

Nous voyons ci-dessus que nos métriques vont globalement dans le même sens, c'est à dire que nous avons bien une corrélation entre le social Score et la métrique en question. Cependant, il est très nettement visible que pour d'autres métrique, cela n'est pas le cas !

Parmi les métriques qui semblent aller dans le sens du social score nous avons : - Hub - Clique Number - Node Degree - Shortest Path (Centralité de proximité) - BetweenessCentrality - RawCliqueScore (score de clique)

Parmi les métriques qui ne vont pas dans le sens du social score, c'est à dire qui n'ont pas vraiment de lien avec le social score nous trouvons : - Le Clustering Coefficient qui va complètement à l'envers du social Score - Response Time - weightedCliqueScore (comme il est lié au Response Time, celà est normal) - Total Mail

Ainsi donc, nous avons pu identifier les métriques qui n'avaient pas vraiment de lien avec le score social obtenu. La question qui s'est alors posé est : pourquoi ? Le response Time est souvent 0 pour les utilisateurs car on ne trouve pas de réponse aux messages datant de moins de 3 jours, cela est nous pensons dû au fait qu'il y a beaucoup de “trous” dans les messages dans la base de donnée. On a des séries de messages supprimées ou manquantes, ce qui nous empêche alors de savoir si on avait une réponse ou non. Autre facteur plus important, si un utilisateur envoie un message a un employé ou une personne que nous n'avons pas dans notre base de 150 employés Enron, et bien nous ne pourrons pas savoir si ce destinataire a répondu ou non puisque nous n'avons pas son dossier de mails envoyés. Donc dans ces conditions là, cette métrique n'est pas exploitable bien que pertinente dans la théorie.

Le nombre de mail total n'est pas non plus un facteur très corrélé au score Social, c'est assez approximatif. En effet, le nombre de mails envoyés et reçus n'est ici pas très représentatif. Pour certaines personnes, la moitié de ses mails envoyés a été supprimée, et pour d'autres, la totalité des mails envoyés est encore là. Donc la quantité de mails dont nous disposons est très variable, et pour le coup, cela ne représente pas vraiment la réalité du nombre de mails envoyés par une personne. Pour que cette métrique fonctionne, il aurait fallut avoir pour chaque personne l'intégralité des mails envoyés durant la période, mais après investigation nous nous sommes rendu compte que ce n'est pas le cas. Voilà pourquoi il n'y a finalement pas de réelle corrélation. Ce critère là n'est donc pas vraiment fiable dans notre cas précis.

En ce qui concerne le Clustering Coefficient, à notre grande surprise, la corrélation est bien là, mais à l'envers ! C'est à dire que plus une personne est haute dans la hiérarchie, et plus son Clustering Coefficient sera faible, c'est à dire qu'elle n'aura pas une tendance à la grégarité. Après réflexion, cela nous semble cohérent, en effet, lorsqu'on est un simple employé, on aura tendance à communiquer dans une petite communauté où tout le monde semble se connaître, on a donc un effet de regroupement, tandis que si on est un directeur général, nos communications seront beaucoup plus vastes et nous communiquerons avec plusieurs directeurs et haut gradés de la hiérarchie qui ont des réseaux de communication différents, donc on ne restera pas cloisonné à des communautés particulières où “mes destinataires se connaissent entre eux”, on aura un effet de regroupement beaucoup plus atténué.

Ainsi, grâce à cette première analyse, nous avons pu obtenir une première orientation dans nos pondérations. Afin d'avoir une vision encore plus juste des métriques, nous avons fait un second scatter plot des valeurs en prenant cette fois ci 20 personnes de l'entreprise (présente dans le graphe), 20 personnes pour lesquelles nous connaissons leur statut au sein de l'entreprise. Nous avons ensuite attribué un score social de 0 à 100 en fonction de leur poste (100 pour l'employé avec le plus grand poste, 0 pour l'employé avec le plus petit poste). Enfin, nous avons, de façon analogue à précédemment, généré plusieurs scatter plot avec d'un côté le score social que l'on a attribué à la personne en fonction de son poste et de l'autre la valeur que l'on avait calculé expérimentalement pour une métrique donnée. Ainsi donc, nous avons identifié les métriques ayant les meilleurs corrélations avec le score Social réel (= score qu'on devrait avoir dans l'idéal), c'est à dire les métriques qui permettaient le mieux de déterminer l'importance de l'employé.

Les métriques ont alors été classées par ordre de priorité en fonction des résultats obtenu avec le scatter plot : Centralité de proximité - Hub - RawCliqueScore (score de clique) - Clique number - Betweeness Centrality

Grâce à cette analyse, nous avons alors pu pondérer correctement les métriques pour le calcul du social Score. Voici les pondérations affectées :

  • Centralité de proximité : 5
  • Hub: 4
  • RawCliqueScore (score de clique) : 4
  • Clique Number : 2
  • Betweeness : 2
  • Node Degree : 2
  • Auth : 1
  • ClusteringCoeff : 1
  • Total Mail : 0,5
  • Response Time : 0
  • weightedCliqueScore : 0

Visualisation de la hiérarchie

A ce stade du projet, il nous restait à trouver une visualisation appropriée afin de retranscrire de la façon la plus compréhensible possible l'importance d'une personne et sa position dans la hiérarchie dans la société Enron. Comment d'un seul coup d'oeil pouvoir comprendre qui sont les personnes les plus importantes chez Enron ? Nous avons pris la décision de produire une représentation sous forme de pyramide à plusieurs niveau afin de représenter l'importance des employés Enron, où chaque niveau correspond alors à un interval du score obtenu pour le social Score :

  • Niveau 1 : 84-100
  • Niveau 2 : 57-84
  • Niveau 3 : 44-57
  • Niveau 4 : 32-44
  • Niveau 5 : 21-32
  • Niveau 6 : 0-21

On peut ici remarquer que plus on descend dans les niveaux, et plus les intervalles de social Score se resserrent (de 20 en 20 environ pour les premiers niveaux puis environ de 10 en 10 pour les niveaux inférieurs. Cela est dû au fait qu'il y a beaucoup plus de personne dans les niveaux inférieurs).

Ces 6 niveaux d'importance nous permettent d'avoir une vision bien découpée des acteurs les plus importants chez Enron parmi les 150 employés.

Une fois que l'importance d'un employé Enron était clairement identifiable de par notre représentation pyramidale, nous avons voulu retranscrire par un système de couleur les correspondances théoriques entre le score social et le poste équivalent dans la vie réel.

Nous avons identifié 5 grands postes majeurs :

  • Chef de direction (CEO) ou Chef des opérations (COO) - 57 à 100
  • Président, Vice Président - 44 à 57
  • Directeur d'agence/ Managers - 32 à 44
  • Chef d'équipe/Responsable - 21 à 32
  • Employé classique - 0 à 21

Une fois le jeux de couleurs mis en place, nous avons voulu donner une identification visuelle sur l'activité d'un employé, c'est à dire à savoir s'il est actif dans la societé Enron (node degree), où au contraire s'il communique uniquement avec une ou deux personnes. Pour cela, nous avons joué sur l'opacité du noeud. Plus un noeud est opaque, plus il participe activement au sein de la societé Enron, et à contrario, plus il est transparent, et moins sa participation est élevée.

Nous avons également voulu donner une information visuelle sur l'influence qu'un employé pouvait avoir sur le reste du réseau Enron. Pour cela nous avons utilisé la métrique Hub qui nous permet de savoir si la personne communique essentiellement avec les personnes importantes du réseaux ou au contraire les personnes en bas de la hiérarchie. Pour celà, nous avons joué sur la taille des cercles, plus un cercle sera grand, plus il aura de l'influence dans le réseau Enron car plus il dialoguera avec les hauts placés Enron.

Une autre indication visuelle concerne l'activité d'un employé chez Enron, c'est à dire, est ce qu'il participe activement au sein du réseau Enron en communiquant avec beaucoup d'acteurs différents ou est ce que son activité reste très local, et donc vis à vis du réseau entier plutôt restreinte. Pour mettre en exergue visuellement cette information, nous avons joué sur l'opacité des noeuds.

Enfin, au vu du grand nombre d'arêtes (1349), nous avons joué sur l'opacité des flèches, plus un flux de communication est intense, plus l'opacité sera élevée. Celà permet essentiellement d'atténuer les flux de communication faibles (et donc peu significatif) et de mettre en avant les flux de communication plus intenses et significatif.

Analyse de la hiérarchie

Une fois les données affichées et clairement exploitables visuellement, nous avons fait une phase de vérification. En effet, pour juger de la qualité de notre résultat, une vérification de la cohérence de la hiérarchie nous a semblé indispensable. Nous avons donc pour chacun des employés importants de la hiérarchie effectué une recherche sur Internet pour voir quel poste il avait occupé dans la réalité. Le résultat fut plutôt satisfaisant, nous avons constaté que notre but avait été atteint en ce qui concerne les personnes les plus importantes de la hiérarchie, on les retrouve bien dans le top 10, mais nous avons également constaté que plus on descendait bas dans les niveaux et plus le jugement était approximatif.

Cette étude a été reporté sur la visualisation ci-dessous pour comparatif :

Conclusion

Bilan

En conclusion, nous pouvons dire que le bilan général est plutôt bon. Nous avons globalement répondu à notre problématique et à nos objectifs initiaux.

Au niveau du traitement de la base de données, les erreurs d'intégrité détectées et les problèmes rencontrés ont été contournés pour finalement obtenir des données exploitables, qui induisent des résultats vérifiables et vérifiés, notamment grâce aux matrices de scatter plot.

Au niveau des métriques sociales, nous couvrons différents aspects avec assez de marge de manœuvre et d'expérimentations préalables pour affirmer que les mesures utilisées sont pertinentes.

Au niveau des outils de visualisation, nous avons su retranscrire les données calculées d'une façon clair et synthétique de façon à ce que le lecteur puisse immédiatement identifier les employés les plus importants, les employés les plus actifs, les employés les plus influant ainsi que le poste attribué à chacun des employés.

Échecs

Malgré ce bilan positif, nous avons deux échecs à déplorer. Tout d'abord, étant donné la complexité et les difficultés associées au traitement et à l'affinage des données, nous avons dû nous résoudre à passer la plus grande partie de notre temps à travailler sur des aspects préparatoire à la visualisation. Nous étions d'accord dés le début sur le fait que notre ensemble de données serait très complexe à exploiter, et que la qualité des visualisations obtenus aurait la priorité sur l'ajout de fonctionnalités. Nous nous sommes donc concentrés sur le problème principal, à savoir la reconstruction fidèle de la hiérarchie de l'entreprise avec ses acteurs principaux.

L'autre échec concerne l'aspect innovant de nos visualisation, puisque nous avons dû favoriser la qualité, la justesse et la pertinence de nos résultats, par choix et par manque de temps. En effet, la représentation par niveau pyramidale n'est pas la représentation la plus innovante.

Perspectives

Enfin, nous ne pouvons pas terminer sans parler de ce qu'il reste à faire, ce que nous aurions pu faire si nous avions eu plus de temps.

A court terme, il faudra améliorer la granularité de la visualisation de la hiérarchie pour que l'outil visuel soit exploitable dans le bas de la hiérarchie sans avoir à zoomer. En effet, dans l'état actuel des choses, il est très difficile de distinguer sans zoomer les éléments en bas de hiérarchie, car leur nombre est trop élevé et les éléments distinctifs sont trop peu nombreux.

Il faudra aussi envisager de créer d'autres outils visuels pour pouvoir identifier les communautés (avec les différents pôles de chez Enron) et différencier les types de relations entre acteurs et groupes d'acteurs.

Enfin, un nettoyage de l'ensemble de données permettrait de garantir plus de fiabilité au niveau des résultats obtenus, puisque les données présentent actuellement des problèmes d'intégrité qui ne sont pas résolus, mais qui sont contournés au niveau des algorithmes de traitement.

Si c'était à refaire

Si c'était à refaire et que nous disposions de plus de temps ou de données exploitables plus facilement, nous aurions privilégié l'aspect créatif et personnalisé nos visualisations pour répondre aux problématiques de la recherche actuelle de manière différente et innovante. Nous aurions exploité les relations entre acteurs pour les caractériser en différents types. Nous aurions également exploité le facteur temps pour découper les échanges de mails en périodes, permettant ainsi de mettre en exergue les mouvements au sein de la hiérarchie (promotions, licenciement, requalifications) et au niveau du travail (mise en place/démantèlement de projets internes, changement de clientèle etc.). Enfin, nous aurions pu exploiter les corpus des mails pour, par exemple, utiliser des mots-clefs et parfaire nos résultats.

Bibliographie

Cohen W. (2009) Enron Email Dataset. [Online]. http://www.cs.cmu.edu/~enron
CALO Project [Online]. http://www.ai.sri.com/project/CALO
Leslie Pack Kaelbling [Online]. http://people.csail.mit.edu/lpk/
Dr Melinda Gervasio [Online]. http://www.ai.sri.com/~gervasio/
Enron Scandal at a Glance. BBC News. [Online]. http://news.bbc.co.uk/1/hi/business/1780075.stm.2002
F. Cazals, C. Karande. Jan 30, 2008. A note on the problem of reporting maximal cliques
Frederic Gilbert, Paolo Simonetto, Faraz Zaidi, Fabien Jourdan, Romain Bourqui. 5 Oct, 2010. Communities and hierarchical structures in dynamic social networks: analysis and visualization
Yi Wang, Marios Iliofotou, Michalis Faloutsos, Bin Wu. [Online]. http://www.cs.ucr.edu/~marios/Papers/nsw.pdf
Galileo Mark S. Namata Jr. Inferring Formal Titles in Organizational Email Archives. http://www.cs.umd.edu/Grad/scholarlypapers/papers/GalileoNamata.pdf
Minoo Erfani Joorabchi, Ji-Dong Yim and Christopher D. Shaw. EmailTime: Visual Analytics of Emails. http://www.sfu.ca/~shaw/papers/Joorabchi-EmailTime-AbstractVAST10.pdf

1) Le jeu de données qui a été nettoyé une première fois
2) Il faut environ 500 Mo d'espace libre pour le format compressé et 1,5 Go pour le format extrait
3) Pour le calcul ultérieur de la métrique du temps de réponse moyen
4) Un employé peut disposer de plusieurs adresses mail
5) Obtention de données erronées, plantages etc.
6) Nous considérons que si le temps de réponse est supérieur à 4 jours, alors le mail considéré ne constitue pas une réponse au mail précédant.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/sdasilva_cbadiola/samuel_da_silva_clement_badiola.txt · Last modified: 2013/01/10 15:08 by cbadiola