User Tools

Site Tools


maribon_rocher:paul_maribon_ferret_tatiana_rocher

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Paul Maribon-Ferret & Tatiana Rocher's corner

Rapport Marvel


Le csv avec les données initiales contient les relations entre les héros (/!\ il a des doublons dans ces relations).

1) Transformation des données


A partir de ce fichier, nous avons fait un premier script python remove_doubles.py pour générer hero-doublesRemoved.csv auquel nous avons supprimé les doublons des noms de héros et les doublons des relations. De plus nous avons rajouté la colonne nbRelations qui représente le nombre de fois que la relation apparaissait.
Ensuite, nous avons utilisé un deuxième script python nodes_list.py pour générer hero-nodesList.csv qui contient la liste des noeuds récupérés à partir de hero-doublesRemoved.csv. On obtiens ainsi un graphe avec 6421 noeuds et 167219 arêtes. Nous avons supprimé tous les sommets de degré 1 car ils n’ont pas d’informations importantes (il y en avait 52).
Le héros qui a le plus de relation est Captain America avec 1907 relations. Nous pouvons remarquer qu’il est possible d’extraire l’ensemble des héros en gardant seulement ceux qui sont de plus haut degré. Mais nous avons préféré un autre algorithme.

2) Utilisation des données


Nous avons utilisé l’algorithme Betweeness centraly déjà fourni dans Tulip et avons sélectionné les sommets qui possèdent le plus grand ratio. Sachant que le plus grand est autour de 150 000 et que la courbe décroît très rapidement nous avons choisi de garder les personnages qui sont au dessus 4000.
Grâce à cette manière nous obtenons un ensemble de héros. (Attention, un humain peut apparaître lorsqu’il est souvent avec un héros.)
Nous avons ensuite implémenté un algorithme de recherche de cliques 1) pour trouver la plus grande communauté de héros travaillant ensemble. Il est extrêmement long. La clique apparaît ensuite en rouge sur le graphe.


Ici, nous avons lancé clique sur une communauté de 33 héros.

Nous avons implémenté un dernier algorithme afin de trouver la communauté humaine entourant un héros. Pour cela nous prenons tous les voisins humains d’un héros et nous les avons triés en deux catégories : citoyens de la ville du héros et possible citoyens lorsque ceux-ci sont apparus en même temps que d’autres héros (nous avons fixé la limite à 3 héros en même temps car deux héros peuvent provenir de la même ville). Les citoyens apparaissent en rouge tandis que les possibles citoyens sont en violet. Cela nous permet de voir la famille et les amis humains du héros.


Voici les relations humaines de Captain America.

3) Tests

Nous avons présenté notre programme sur un ensemble de 1000 sommets (d'où les 33 héros seulement) afin de voir tourner tous les algorithmes rapidement. Mais Betweeness centrality fonctionne facilement jusqu'à 3000 sommets, nous n'avons donc pas pu le tester pour l'ensemble des sommets.
L'algorithme clique tourne en 2h pour 80 sommets.
Pour l'ensemble des données, la recherche d'amitié/famille est très rapide.

1000_nodes.tlpx

marvel_scripts.zip

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/maribon_rocher/paul_maribon_ferret_tatiana_rocher.txt · Last modified: 2014/01/17 11:22 by trocher