User Tools

Site Tools


monfort_elhilali:matthias_monfort_sami_el_hilali

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Matthias Monfort & Sami El Hilali's corner

Identifying statistically significant edges in one-mode projections (Zachary Neal, 2012)


Les projections sur une dimension de données à deux dimensions sont des représentations graphiques d'intérêt dans l'analyse non triviale de données. Même si des méthodes d'analyse de réseaux à deux dimensions existent, la projection sur une dimension permet d'extraire des informations fiables sur les données. Il est en plus possible d'utiliser les technique classique d'analyse de données uni modales. Une structure bipartite (à deux dimensions) peut être projeté sur une de ses dimensions. Le résultat de cette projection peut être présenté sous plusieurs formes selon l'analyse. Un graphe pondéré peut par exemple être généré. Le poids des arêtes représente alors la qualité des interactions entre les deux modes. D'autre part, il est possible d'évaluer les interactions internes à la dimension sur laquelle la projection est effectuée en utilisant un seuil de tolérance au delà duquel on considère que deux membres interagissent. La détermination de ce seuil est l'étape indispensable à la création de données informatives. La plupart du temps ce seuil tient compte uniquement des conditions globales de l’ensemble des dimensions. Zachary Neal propose avec cette publication une méthode de projection n'incluant que les arêtes statistiquement significatives des conditions locales des membres considérés. Cette méthode filtre mieux le bruit, ce qui offre des données ayant de meilleures perspectives d’interprétation.


Données

L'auteur fait la démonstration de l'efficacité de son algorithme à l'aide de deux exemples. Un seul de ces jeux de données n'est accessible. Il est issu d'une publication de Davis et al.'s (1941). Il répertorie les informations relatives à la participation de 18 femmes (i.e. acteurs, ensemble de nœuds) à 14 événements culturels (i.e. autre ensemble de nœuds) aux U.S.A. Le jeu de données que nous avons étudié est la matrice binaire répertoriant ces informations (fichier annexe « davis.dat »).

davis.dat
DL
NR=18 NC=14
FORMAT = FULLMATRIX DIAGONAL PRESENT
ROW LABELS:
EVELYN
LAURA
THERESA
BRENDA
CHARLOTTE
FRANCES
ELEANOR
PEARL
RUTH
VERNE
MYRNA
KATHERINE
SYLVIA
NORA
HELEN
DOROTHY
OLIVIA
FLORA
COLUMN LABELS:
E1
E2
E3
E4
E5
E6
E7
E8
E9
E10
E11
E12
E13
E14
DATA:
 1 1 1 1 1 1 0 1 1 0 0 0 0 0
 1 1 1 0 1 1 1 1 0 0 0 0 0 0
 0 1 1 1 1 1 1 1 1 0 0 0 0 0
 1 0 1 1 1 1 1 1 0 0 0 0 0 0
 0 0 1 1 1 0 1 0 0 0 0 0 0 0
 0 0 1 0 1 1 0 1 0 0 0 0 0 0
 0 0 0 0 1 1 1 1 0 0 0 0 0 0
 0 0 0 0 0 1 0 1 1 0 0 0 0 0
 0 0 0 0 1 0 1 1 1 0 0 0 0 0
 0 0 0 0 0 0 1 1 1 0 0 1 0 0
 0 0 0 0 0 0 0 1 1 1 0 1 0 0
 0 0 0 0 0 0 0 1 1 1 0 1 1 1
 0 0 0 0 0 0 1 1 1 1 0 1 1 1
 0 0 0 0 0 1 1 0 1 1 1 1 1 1
 0 0 0 0 0 0 1 1 0 1 1 1 1 1
 0 0 0 0 0 0 0 1 1 1 0 1 0 0
 0 0 0 0 0 0 0 0 1 0 1 0 0 0
 0 0 0 0 0 0 0 0 1 0 1 0 0 0

Importation des données dans Tulip 

Import des données brutes

Nous avons écrit un script de parsage de ce fichier dans le but d'intégrer nos données dans Tulip. Pour cela, nous tirons parti du module complémentaire « AdjacencyMatrixImport » (AMI) intégré au logiciel. Le script traduit notre matrice en une matrice d'adjacence importable dans le module AMI dont le format est présenté par la figure suivante:



C'est une matrice triangulaire. Un nœud est for. On y perd les informations de colonnes et de lignes, réunies en une diagonale, mais une notation différentielle des deux modes permet de conserver cette information (i.e. $NOM , ~EVENEMENT). Chaque cellule de cette diagonale forme un nœud dans le graphe, la valeur de la cellule est stockée automatiquement par le module dans la variable viewLabel du noeud. Les autres cellules indiquent s'il n'y a aucune relation ( # ) entre les nœuds ou au contraire, la valeur de l'arête à créer si la relation existe. Ici, la valeur indique l'événement auquel l'acteur a participé. Elle est stockée dans la variable viewMetric associée à l'arête.

Extraction de la matrice bi-modale à partir d'un graphe bi-partite

Grâce aux informations conservées dans les noms des nœuds et dans la variable viewMetric des arêtes on peut reconstruire la matrice d'origine dans Tulip, à partir du graphe. Une itération sur les arêtes permet de retrouver les couples de nœuds reliés par une arête. On sélectionne dans chaque couple la dimension qui servira à la projection. La matrice est stockée sou forme de dictionnaire : matrice = { '<noeud_acteur1>' : [ i1, i2, i3 …, in ], … }

Projection

La projection P de La matrice binaire est une autre matrice où Pij est le nombre d'événement commun entre l'acteur i et j. Pii (en diagonale) est le nombre total d'événement auquel l'acteur i participe avec 0 ≤ Pii ≤ E (E le nombre d'événements total). Si l'on considère la participation commune de deux acteurs à des événements comme étant une preuve d'interaction sociale, on peut alors émettre l'hypothèse qu'un Pij élevé indique une relation d'ordre positive entre i et j. Pour valider cette hypothèse, on détermine un seuil permettant d'évaluer si le nombre de co-participation C au delà duquel la co-participation de deux acteurs i et j à un nombre d’événements Pij n'est pas due au hasard. La mesure de la probabilité que deux acteurs co-participent à exactement C événements est donnée par la formule suivante :


C varie de 0 au maximum de co-participations possibles (c'est à dire le nombre de participations minimum d'un acteur Pii ou Pjj). Cette formule est décrite par une loi binomiale ayant la densité de probabilité apparaissant sur la figure 1 (les valeurs E=100, Pii=45, Pjj=40 sont données à titre d'exemple et ne proviennent pas des données utilisées) :


Les valeurs C=14 et C=22 correspondent respectivement au « seuil inférieur » (lower threshold) et au « seuil supérieur » (upper threshold). Ce valeurs permettent de déterminer l'ordre de la relation entre les acteurs i et j et ainsi d'obtenir le lot d'arêtes significatives à représenter sur le graphe projeté. Si les acteurs ont un co-participation supérieure au seuil supérieur alors il y a moins de 5 % de chances que ces co-participations soient dues au hasard (même raisonnement pour des acteurs ayant une co-participation inférieure au seuil inférieur). Dans cet exemple, le test utilisé est bilatéral, la projection est dite « signée » dans la mesure où l'hypothèse permet d'identifier des relations « positives» et « négatives » entre les acteurs.

Implémentation

La résultat de la projection sur 1 mode d'un graphe bi-partite est une matrice carrée. La construction de cette matrice implique de déterminer pour chaque couple d'acteurs ( i.e. couples de nœuds) si une arête les relient et le cas échéant le type de celle-ci. Le type est déterminé en comparant le nombre de co-participations aux bornes définies par les seuils. Le graphe est ainsi parcouru en calculant pour chaque acteur si il a une relation avec les autres acteurs. Seul le seuil supérieur est pris en compte dans le script fournit. On obtiens ainsi des relations entre les acteurs qui ont co-participé à plus d 'événements que ce que le hasard prédit. On effectue une analyse unidirectionnelle de la densité de probabilité décrivant une loi binomiale. La matrice obtenue par projection permet ensuite de construire un nouveau graphe ne faisant apparaître que les liaisons entre acteurs ayant une « relation ».

Reproduction des résultats

Les résultats générés par Zachary Neal pour le jeu de données de Davis et al.'s (1941) n'ont pas pu être reproduit. Une approximation manque vraisemblablement à sa démonstration. Pour illustrer notre propos nous étudierons l'exemple des interactions de Pearl. Le fichier de données « davis.dat » indique qu'elle a participé aux événements E6, E8 et E9. On prend alors pour cette démonstration Pii=3 est le nombre de participations totales de Pearl. Le graphe projeté présenté par l'auteur fait apparaître une relation entre Pearl et Dorothy. Dorothy participe aux évènements E8, E9, E10, E12.. On prend alors Pjj=4. Le nombre de co-participation entre ces acteurs est de 2. Si l'on prend maintenant Ruth en acteur j alors on note qu'elle participe aux événements E5, E7, E8, E9 soit Pjj=4 et et Pij=2 (Pij est la co-participation entre les acteurs i et j). La stricte résolution de l'équation Pr(pij=C)=0.05 ne permet donc pas de discriminer ces deux relations qui ont la même signification statistique. On déduis de ces résultats qu'une approximation a été faite par l'auteur au cours de la projection. Celle-ci n'étant pas évoquée dans la publication, les résultats ne peuvent pas être reproduits.

Construction du graphe projeté

La nouvelle matrice contenant la projection binaire des données est utilisée pour créer un nouveau graphe dans Tulip. Le résultat est un graphe synthétisant les relations statistiquement significatives entre les différents acteurs. Notre graphe est un sous graphe construit avec les nœuds de type « acteur » (soit la dimension projetée). Une itération sur la matrice permet de repérer les liens entre 2 nœuds Ni et Nj (valeur +1 dans la cellule ij), on crée alors une nouvelle arête entre ceux-ci. Pour isoler le sous graphe on ajoute un nouveau paneau en utilisant la représentation « Node link diagram » (clic droit sur le sous graphe → add panel → Node Link Diagram view). Dans le cas d'une projection signée, on doit distinguer les arêtes de type -1 (relations « négatives » significatives), de type 0 (relations dues au hasard) et de type +1 (relations « positives » significatives). Ces informations supplémentaire peuvent être par exemple symbolisées par une couleur différente de l'arête en fonction de son type.

Conclusion

La projection de donnée associée à une dichotomisation selon un seuil local permet une analyse non triviale des données. A l'inverse de la dichotomisation avec seuil global, le seuil local permet de filtrer le bruit ainsi que d'extraire des informations statistique par rapport à la qualité des interactions. La qualité des interactions est définie par l'hypothèse statistique posée par l'utilisateur. L'utilisation d'un test bilatéral est nécessaire pour effectuer une progression signée et extraire de l'information supplémentaire.

Script

matrice d'adjacence initiale
Adjacency_matrix.txt
~E1
# ~E2
# # ~E3
# # # ~E4
# # # # ~E5
# # # # # ~E6
# # # # # # ~E7
# # # # # # # ~E8
# # # # # # # # ~E9
# # # # # # # # # ~E10
# # # # # # # # # # ~E11
# # # # # # # # # # # ~E12
# # # # # # # # # # # # ~E13
# # # # # # # # # # # # # ~E14
1 2 3 4 5 6 # 8 9 # # # # # $EVELYN
1 2 3 # 5 6 7 8 # # # # # # # $LAURA
# 2 3 4 5 6 7 8 9 # # # # # # # $THERESA
1 # 3 4 5 6 7 8 # # # # # # # # # $BRENDA
# # 3 4 5 # 7 # # # # # # # # # # # $CHARLOTTE
# # 3 # 5 6 # 8 # # # # # # # # # # # $FRANCES
# # # # 5 6 7 8 # # # # # # # # # # # # $ELEANOR
# # # # # 6 # 8 9 # # # # # # # # # # # # $PEARL
# # # # 5 # 7 8 9 # # # # # # # # # # # # # $RUTH
# # # # # # 7 8 9 # # 12 # # # # # # # # # # # $VERNE
# # # # # # # 8 9 10 # 12 # # # # # # # # # # # # $MYRNA
# # # # # # # 8 9 10 # 12 13 14 # # # # # # # # # # # $KATHERINE
# # # # # # 7 8 9 10 # 12 13 14 # # # # # # # # # # # # $SYLVIA
# # # # # 6 7 # 9 10 11 12 13 14 # # # # # # # # # # # # # $NORA
# # # # # # 7 8 # 10 11 12 13 14 # # # # # # # # # # # # # # $HELEN
# # # # # # # 8 9 10 # 12 # # # # # # # # # # # # # # # # # $DOROTHY
# # # # # # # # 9 # 11 # # # # # # # # # # # # # # # # # # # $OLIVIA
# # # # # # # # 9 # 11 # # # # # # # # # # # # # # # # # # # # $FLORA
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/monfort_elhilali/matthias_monfort_sami_el_hilali.txt · Last modified: 2014/01/17 18:15 by selhilali