User Tools

Site Tools


dimitri_ranc:projet

Bio-Info Visualisation

Mathieu SCHAEFFER & Dimitri RANC 2015/01/23 16:53

Il est possible de récupérer le rapport au format pdf ici.

Comment mettre en évidence les cercles d’amis via Facebook ? Les amis les plus influents ? La distance entre les amis ?

Nous allons étudié le graphe fournis par Tulip avec le plugin Facebook. En se connectant via le logiciel, on peut récupérer le graphique suivant :

Graphe des relations entre ami

Au centre, le propriétaire du compte Facebook que nous appellerons par la suite noeud source. Chaque noeud correspond à un ami du compte source et chaque arrête correspond à une relation entre deux personnes.

Afin de rendre le graphique plus lisible et plus “aéré”, nous avons décidé de supprimer le noeud source (ainsi que toutes ses relations). De cette manière les futurs calculs seront aussi simplifiés. On obtient alors le graphique suivant :

Graphe des relations entre amis sans le noeud source

Nous pouvons d’ores et déjà voir clairement apparaître des sortes de zones plus sombres, elles correspondent sur le graphique à des régions plus concentrées en points et surtout une concentration de lien entre les sommets plus importante. Nous allons essayer de mettre en évidence que ces zones correspondent en fait à des “cercles de connaissances”.

Les personnes influentes

Dans notre étude, on considère qu’une personne est influente et a du poids si elle a beaucoup de voisins. C’est à dire si elle a beaucoup d’amis en commun avec le noeud source. Pour cela on utilise simplement le code suivant qui nous permet de retrouver le nombre d’amis par amis.

def nbAmis(graph):
	nbAmis = graph.getIntegerProperty("nbAmis")
	for node in graph.getNodes():
		nbAmis[node] = 0
		for voisin in graph.getInOutNodes(node):
			nbAmis[node] += 1

On obtient alors le diagramme suivant :

Histogramme du nombre d’amis par personne

On voit alors que la majorité des noeuds sont très peu influents (entre 0 et 25 amis en commun) tandis que certains on un poids fort (plus de 50) voir très fort (plus de 75). On peut donc penser que ses personnes sont le centre de ce que l’on a appelé les “cercles de connaissances”.

Facebook, ce petit monde

On souhaite maintenant mettre en évidence que Facebook est un petit monde. Pour être plus précis, on veut montrer que nos amis Facebook ont en commun beaucoup d’amis avec nous. Pour cela, on peut comparer les listes d’amis et voir si les différences sont importantes. Nous avons fait le choix de plutôt calculer la distance maximum dans le graphique pour chacun de nos amis. De cette manière, on va pouvoir mettre en évidence que nos amis sont généralement proches des autres amis (parfois en contact direct parfois à plus grande échelle, des amis d’amis, des amis d’amis d’amis …) et donc que le graphe est fortement connexe. Afin de voir plus facilement, on a choisi de faire varier les couleurs des noeuds. L’algorithme suivant affiche en vert les noeuds s’ils sont proches de la source et en rouge s’ils en sont loin (en blanc s’ils ne sont pas connectés).

def drawDistanceGraph(graph, node):
	distanceProperty = graph.getIntegerProperty("distanceProperty")
	viewColor =  graph.getColorProperty("viewColor")
 
	tlp.maxDistance(graph, node, distanceProperty)	
	max = 0
	for n in graph.getNodes():
		if distanceProperty[n] > max:
			max = distanceProperty[n]
 
	pas = 255/max
 
	for n in graph.getNodes():
		if distanceProperty[n] == -1:
			viewColor[n] = tlp.Color.White
		else:
			viewColor[n] = tlp.Color(pas*distanceProperty[n], 255-pas*distanceProperty[n], 0)

On obtient alors le graphique suivant :

Graphe de la répartition des distances des noeuds, on a choisit un noeud au hasard et on calcule la distance des noeuds par rapport à ce noeud

On voit très clairement une prédominance de la couleur verte ce qui veut dire que les amis sont proches les uns des autres sans forcément être amis entre eux. La moyenne est en effet de 6 avec un histogramme des répartition comme suit. Les données recueillies ne sont pas répartie équitablement ce qui prouve que les noeuds sont très liés et qu’il n’y a pas forcément certains noeuds qui se démarquent.

Histogramme des distances maximums pour chaque noeud

On peut rapprocher ce résultat avec la théorie de Frigyes Karinthy en 1929 : les six degrés de séparation. Cette théorie évoque la possibilité que toute personne sur le globe peut être reliée à n'importe quelle autre, au travers d'une chaîne de relations individuelles comprenant au plus cinq autres maillons (source).

Les distances égales à 0 concernent les noeuds n’ayant aucun ami en commun avec le compte source (qui a été supprimé au début des traitements).

Nous avons donc mis en évidence que bien que le nombre d’amis ne soit pas forcément grand, il est très facile de parcourir le graphe entièrement en passant par un minimum de noeuds.

Graphe des cercles d’amis

Nous allons mettre en évidence la présence de groupes distincts d’amis au sein de ce super-groupe d’amis. Cette construction se fera par étapes, visibles progressivement sur l’espace de travail. Nous allons maintenant détailler chacune de ces étapes. Pour cela, nous allons tout d’abord attribuer un sous-groupe pour chaque personne. Puis, pour chaque personne, calculer son meilleur ami en fonction du nombre d’amis en commun entre les deux et rejoindre son groupe.

Si le groupe de la première personne rejoignant son meilleur ami, contenait d’autres personnes, le groupe sera supprimé et ses occupants seront transférés dans le groupe du meilleur ami.

Graphe montrant les différents groupes représentés par différentes couleurs

On récupère ainsi un certain nombre de groupes de très bons amis. Pour chacun de ces groupes, on créée un méta-noeud, portant le nom de la personne avec le plus de relations dans le groupe. On supprime également dans le sous groupe des méta-noeuds, les personnes ne faisant partis d’aucun cercles d’amis car aucune autre relation que le noeud source. Pour finir, on réalise en plus des super méta-noeuds avec les méta-noeuds connectés.

Vue du résultats final avec les cercles d’amis regroupés dans des métanoeuds

Une fois le nouveau graphe réalisé, on y ajoute quelques améliorations visuelles pour une meilleure appréciation des cercles d’amis.

Par un double clic sur un méta-noeud, on peut rentrer dedans et observer les sous-groupes d’amis et ainsi de suite. Par exemple dans ce cas, rentrer dans le super méta-noeud de Dimitri RANC

Zoom sur un gros métanoeud contenant des petits métanoeuds

Nous n'arrivons pas à mettre le code complet de cet algorythme sur le wiki mais vous pouvez le récupérer ici.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/dimitri_ranc/projet.txt · Last modified: 2015/01/23 17:00 by ranc