User Tools

Site Tools


ecassan_tfaux:elodie_cassan_thomas_faux


Les fichiers contenant les scripts et les données sont disponibles ici : script_wiki_cassan_faux.tar.gz
La présentation est disponible ici : presentation_faux_cassan.pdf

Introduction

Pour étudier certains jeux de données une des solutions à notre disposition est la réalisation de graphe et l'utilisation d'outils de visualisation accompagné d'algorithmes qui permettent de se poser et de répondre à un certain nombre de questions. Le but de notre projet est de réaliser la visualisation et l'analyse d'un jeu de données en utilisant le logiciel Tulip accompagné de scripts python.

Le jeu de données choisi provient du site : http://snap.stanford.edu/data/wiki-Elec.html.
Les données ont été extraites à partir du site Wikipédia (édité le 3 Janvier 2008) et concernent les élections des administrateurs de celui ci.

Wikipedia en quelques chiffres:

  • Fondé en 2001
  • Contient à cette heure plus de 22,000,000 articles dans 285 langues.
  • Plus de 77 000 contributeurs actifs
  • 150 salariés à ce jour
  • Le 5ème site le plus visité au monde avec, en Février 2012, plus de 470 millions de visiteurs uniques

Wikipedia est une encyclopédie libre développée par des volontaire dans le monde entier. Une partie des utilisateurs actifs sont des administrateurs, et peuvent réaliser une maintenance via des outils techniques particuliers. Wikipédia compte actuellement 183 administrateurs sur Wikipédia en français, soit 1 % des utilisateurs actifs (1454 sur Wikipedia en anglais). L'utilisateur qui veut être élu au rang d'administrateur envoi une requête, puis, la communauté fait un vote via des discutions publiques pour lui donner ou non le status d'administrateur.

Problématique

Chaque jour Wikipédia enregistre de nombreuses créations d'articles, ainsi que des modifications des article existants. Il est nécessaire pour la crédibilité du site que ces modifications soient effectuées par des administrateurs. L'administrateur doit tout d'abord vérifier l'information et devra ensuite réaliser la maintenance car il est le seul à pouvoir modifier l'article. Réserver les outils d'administration à des utilisateurs actifs et expérimentés permet ainsi de limiter certains abus.

Les administrateurs sont élus par la communauté des utilisateurs de wikipédia, si l'un d'eux veut présenter sa candidature à la communauté un vote publique sera lancé et ses pairs voterons pour ou contre lui. Le vote se termine au bout d'un temps défini et si une majorité de pour est obtenue, le statut d'administrateur sera délivré au candidat.

Cette méthode permet en théorie de promouvoir la personne la plus qualifiée dans un certain domaine pour vérifier les articles et de les modifier selon ce qu'il juge nécessaire. Mais cela nous laisse nous poser la question de la crédibilité de telles élections. En effet, est ce qu'il n'y aurai pas des groupes dans la communauté et alors une forte tendance des gens d'un même groupe à voter entre eux, ou même à voter de façon négative pour un autre groupe de personnes? Un administrateur déjà en fonction n'a t'il pas une forte influence sur les votants et ne les amènes t'ils pas à voter comme lui ? Nous nous somment également posé la question de savoir comment évoluaient ces paramètres au cours du temps.

Présentation et récupération du jeu de données

A notre dispositions sur le site: http://snap.stanford.edu/data/wiki-Elec.html se trouvaient un fichier texte contenant les résultats des votes ainsi que deux articles portant sur l'étude des interactions dans les réseaux sociaux.

Le jeu de donnée choisi contient environ 2800 élection avec 7 000 participants, et 100 000 votes réalisés. L'ensemble de ces votes contient :

  • 83962 votes positif
  • 23118 votes neutre
  • 6960 votes négatif (contre le candidat)

Sur l'ensemble des élections 1 200 ont abouti a une élection. Environ la moitié des votes présents dans le jeu de données proviennent d'administrateurs.

Le fichier texte à notre disposition contient des informations sur la date du vote, le candidat, les votants et leur vote (positif,négatif ou neutre), l'administrateur ayant clôturé l'élection, la date de clôture ainsi que le résultat final du vote.

Structure du fichier:

E	1
T	2004-09-21 01:15:53
U	30	cjcurrie
N	32	andyl
V	1	3	2004-09-14 16:26:00	ludraman
V	-1	25	2004-09-14 16:53:00	blankfaze
V	1	4	2004-09-14 17:08:00	gzornenplatz
...
  • E indique le résultat du vote (positif 1, ou non 0)
  • T la date d’arrêt du vote,
  • U le candidat (identifiant et pseudonyme),
  • N l'administrateur (identifiant et pseudonyme),
  • V un vote réalisé avec en information le vote émit (1:positif, 0:neutre, -1:négatif), l'identifiant du votant,la date du vote et le pseudonyme du votant.

Ce jeu de données a permis d'en réaliser un autre plus léger contenant un graphe orienté représentant l'ensemble des votes positifs. wiki-Vote.txt Structure du fichier:

# Directed graph (each unordered pair of nodes is saved once): Wiki-Vote.txt 
# Wikipedia voting on promotion to administratorship (till January 2008). Directed edge A->B means user A voted on B becoming Wikipedia administrator.
# Nodes: 7115 Edges: 103689
# FromNodeId	ToNodeId
30	1412
30	3352
30	5254
30	5543
30	7478
3	28
3	30
3	39
...

Ceci signifie que la personne dont l'identifiant est dans la première colonne a voté pour la personne dont l'identifiant est dans la seconde colonne.

Nous nous somme tout d'abord servi de ce second fichier pour obtenir une première visualisation facile à obtenir puis nous avons exploité les informations du jeu de données principal.

Afin de constituer notre graphe principal nous avons réalisé un script qui construit celui ci (script init.py). Chaque personne qui se présente au titre d'administrateur forme un noeud noir et les votants forment un noeud rouge. Il a fallu faire attention à ne pas dupliquer les noeuds. Pour les candidats nous avons également ajouté un paramètre “succes” qui précise si le candidat a été élu ou non.

Les arêtes ont pour origine le votant et pour arrivée la personne à qui revient le vote. Pour chaque arête nous avons préciser un paramètre “datevote” contenant la date du vote ainsi qu'un paramètre “votegraphe” donnant la valeur du vote (positif, neutre ou négatif). Nous n'avons pas pris en compte l'identifiant de l'administrateur qui a clôturé le vote, ceci nous paressant inutile.

Nous obtenons un graphe contenant 7 194 points (votant + candidat au titre d’administrateur) et 114 040 arêtes (représentant les votes).

Traitements des données

Visualisation générale

Une fois les données récupérées, nous avons pu appliquer l'algorithme GEM Frick (OGDF) sur le graphe que nous avons obtenu. GEM est une classe d'algorithmes qui permettent de trouver le maximum de vraisemblance des paramètres de modèles probabilistes lorsque le modèle dépend de variables non observables.

Cette visualisation nous permet de remarquer que la plus grande partie de la communauté votante est regroupée. Les quelques exceptions sont des petits groupes composés de une à trois personnes et donc négligeables si l'on considère les questions que nous nous somment posées. En effet, ces petits groupes (représentant 0.7% des données) ne sont pas connectés à la masse générale des votants et ne nous renseigne donc en rien sur les intentions de votes des utilisateurs.

Calcul du degrés général de l'échantillon

Nous avons trouvé intéressant de connaître la connectivité générale de l'échantillon, nous avons alors, grâce à l'algorithme degrés, pu créer un histogramme des degrés des noeuds de l'échantillon:

Sur cette image est représenté en abscisse le nombre de connections du noeud et en ordonnée le nombre de noeuds. On peut voir qu'une grande partie des noeuds n'ont que peu de connections, mais une partie conséquente des noeuds de l'échantillon possèdent un degrés élevé. Les noeuds ayant un fort degrés représentent les membres les plus actifs et donc les plus intéressants pour nous.

Recherche de triades

Dans l'article fourni avec le jeu de données nous avons vu qu'un motif revenais souvent parmi les interactions sociales: les triades. Une triade dans un graphe est un ensemble de trois points qui sont connectés entre eux par des arêtes positives ou négatives. Nous avons décidés de nous concentrer sur les triades ayant uniquement des interactions positives pour pouvoir déceler les utilisateurs qui feraient des échanges de votes positifs.

Voici un exemple de Triade positive: Nous avons donc créer un algorithme qui crée des sous-graphe composés de triades (fonction rechercheGroupeDeTriades() dans le script recherchesousgroupe.py). Notre algorithme nous permet donc de regrouper les noeuds en groupes de triades, si un groupe de plus de 10 triades est repéré, un sous-graphe est crée et contiendra l'ensemble. Voici un exemple de sous-graphe contenant un ensemble de triades:

Nous remarquons alors qu'il existe de fortes communautés votant uniquement de façon positive pour ses membres. Au centre de chaque groupe de triades se trouve le noeud qui possède le plus fort degrés, il est le “centre” de ce groupe. Les noeuds faisant partie de ce groupe peuvent être le centre de leur propre groupe de triades.

Réalisation d'un clustering

(script dans recherchesousgroupe.py fonction grapheOrganiseCluster(graph)) Nous avons vu la présence de sous-groupes composés de triades donc possédant une relation forte. La prochaine étape consiste donc à voir si il est possible de faire une clusterisation sur l'ensemble des données. Nous verrons alors si il existe réellement des groupes distincts qui votent positivement entre eux et négativement pour les autres ou si tout ces sous-groupes sont reliés entre eux et ne forment qu'une seule communauté. Pour cela nous avons choisi de faire une variante de l'algorithme de Louvain. Tout d'abord chaque noeud représente un cluster. La seconde étape consiste à assembler entre eux les noeuds pour qui il existe un vote réciproque.La troisième étape assemble entre eux les clusters dont le score ((vote positif + vote neutre +vote négatif) / nombre de vote) entre deux ces clusters est supérieur a un seuil.
Les différentes étapes sont expliquées dans les schémas suivant:


Une fois que tous les noeuds sont dans des clusters différents on va réaliser une première étape de fusion. On parcours les clusters, ici on commence par le cluster A, puis on regarde si il existe des clusters avec lesquels celui-ci possède un vote réciproque non négatif. On obtient le cluster [A,B,C] (cf image de gauche). On va ensuite parcourir ce cluster et y ajouter tous les autres clusters qui possèdent cette même caractéristique, tout en vérifiant qu'il n'y ai pas plus d'un vote négatif avec les autres noeuds du cluster. On ajoute donc ici le noeud D (image de droite). On passe ensuite au cluster suivant,ici au cluster [E].


Après la seconde étape on va fusionner les clusters qui possèdent un score supérieur au seuil fixé de 0,2. Nous avons fait attention à ne pas comparer 2 fois les mêmes clusters. Après cette étape on obtient des clusters qui possèdent un fort taux de votes positifs à l'intérieur de ceux ci, et un fort taux de votes négatifs (ou pas de lien) entre eux.

Aprés avoir appliqué cet algorithme sur notre graphe,on obtient alors un ensemble de cluster qui contient beaucoup de clusters qui ne sont composés que d'un seul ou de très peu de noeuds et un cluster principal à l’intérieur duquel la liaison est forte. Sur l'image ci dessous nous pouvons voir en jaune les noeuds présents dans le cluster principal.

La communauté Wikipédia semble donc ne former qu'un seul groupe. Nous avons ensuite appliqué l'algorithme de betweenness centrality pour voir si à l'interieur de ce groupe étaient présents des personnes plus interconnectées que d'autre. L'algorithme betweenness centrality est un algorithme qui calcule la centralité d'un noeud dans un réseau. La centralité d'un noeud est le nombre de plus cours chemins passant par ce noeud de tout les sommets à tout les autres du graphe.

Après avoir appliqué cette algorithme combiné avec un algorithme de colorisation nous obtenons la visualisation suivante:

On peut clairement identifier 3 personnes autour desquels la communauté s'articule. On peut donc émettre l’hypothèse que la communauté s'est construite peu à peu autour de ces personnes.

Evolution au cours du temps

La dernière étape de notre projet est d'observer au cours du temps l'évolution du processus de vote de wikipédia. Le graphe contenant l'ensemble des votes a donc été divisé en sous graphes contenant chaque année. L'année 2008 ne comptant qu'un seul mois n'a pas été pris en compte. Les graphes contenant les votes par années ont ensuite été divisés en sous graphes contenant les mois. Nous obtenons au cours des années les représentations suivantes:

Nous pouvons observer une nette augmentation du nombre de votant et du nombre de personnes qui se sont présentés au rang d'administrateur (surtout de 2004 à 2005).

Nous voulons maintenant voir si une personne élue et au centre d'une triade une année joue un rôle de “chef” au cours du temps, et donc si les personnes qui l'entourent suivent son vote au cours du temps.

Nous avons donc appliqué à chaque sous graphe représentant les années l'algorithme de recherche des triades, pour obtenir ces sous-groupes. les triades sont ensuite parcourues pour trouver l'utilisateur au centre de la triade, autrement dit l'utilisateur ayant le plus fort degrés entrant de chaque triade.

Pour chaque “centre” de triade trouvé, nous parcourons l'ensemble de ses votes et stockons ceux qui sont ultérieurs à son élection. Nous pouvons alors parcourir les votes stockés pour les comparer à ceux des membres de la triade d'intérêt. Le résultat de cette opération est le pourcentage, pour chaque session de vote, de votes identiques au sien de la part des membres de sa triade. Pour un administrateur donné, et pour un vote donné, nous regardons si les utilisateur appartenant à sa triade votent comme lui. Le résultat sort sous forme d'un tableau de pourcentages ou chaque case contiens le pourcentage de gens ayant voté de la même façon que lui pour une session donnée.

Ensuite nous faisons la moyenne par élu pour tout les votes qu'il a fait et au final nous obtenons un pourcentage de vote dans son sens de chaque administrateur élu au sein d'une triade au cours du temps.

Nous avons obtenu les statistiques suivantes:

Sur les trois histogrammes en bleu sont représentés en abscisse les « centres » de triades élus, et en ordonnée le pourcentage moyen des membres de sa triade qui votent comme lui pour chaque années. L'année 2004 a été exclue car elle ne contenais que deux données. On peu remarquer qu'au fil des années de plus en plus de membres de triades sont élus, mais on peu aussi remarquer qu'ils sont de plus en plus suivis au cours des années. Pour représenter cette évolution nous avons calculée la moyenne de tout les élus par années représentée dans le dernier histogramme.

Le nombre de personne ayant été élues et ayant une moyenne de 0 % étant élevé, nous en avons conclu qu'une grande partie de ces élus avaient été choisis par une triade désormais inactive. Nous avons donc décidé d'exclure ces élus qui ne sont pas significatifs. Nous obtenons un nouvel histogramme pour le calcul des moyennes par années qui représente bien l'évolution des votes au cours du temps.

Conclusion et Perspectives

Les différentes visualisations et algorithmes réalisés nous ont permis de démontrer que les utilisateurs de Wikipédia ont tendance à se regrouper et à s'entraider pour accéder au statut d'administrateur. On peut remarquer la formation de triades positives, témoin d'un lien “d'amitié” fort et de formation de sous groupe. Ces triades sont des communautés dont l'influence devient de plus en plus fortes avec le temps. En effet les administrateurs au sein de triades ont ces dernières années en particuliers une influence sur les votes des utilisateurs issus de la même triade que lui. Néanmoins l'ensemble des triades est interconnectés, nous n'avons pas pu mettre en évidence des groupes votant positivement à l’intérieur de ceux-ci et négativement entre-eux.

Nous avons donc bien répondu à la problématique. D’après nos observations les utilisateurs de Wikipédia constituent une communauté uni, qui vote dans le même sens. Cependant les individus d'une triade ont de plus en plus tendance à suivre la personne au centre de celle ci. Le phénomène de leader a l'air de se mettre doucement en place. Des analyses seraient à réaliser sur les années suivantes pour voir si cette tendance se poursuit ou non.

Des informations sur la localisation des votants et sur les liens d'amitiés entre ceux-ci auraient été des données très intéressantes à intégrer dans notre analyse.

Sources d'informations

  • J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. CHI 2010.
  • J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/ecassan_tfaux/elodie_cassan_thomas_faux.txt · Last modified: 2013/01/11 16:16 by ecassan