En février dernier, l’équipe de chercheurs DNET* à l’ENS de Lyon, lançait une expérience, Fellows, pour mettre en application un algorithme permettant de mieux identifier les communautés recouvrantes. Un article vient de paraître pour annoncer les résultats après six mois d’expérimentation. Selon les chercheurs, la pratique a bien validé la théorie. "Nous avons confirmé que notre métrique, la cohésion est une mesure de qualité", explique le professeur Eric Fleury, directeur de l’équipe DNET. Leur algorithme de génération de groupe, selon le chercheur, permet de dépasser les modèles actuels d’identification de communautés, et d’être plus réaliste. Dans leur idée, il pourrait par exemple servir à mieux organiser ses groupes dans Facebook, ou ses cercles dans Google +.
Des triangles pour mieux capturer la cohésion
Sur Facebook, par exemple, tous les liens entre individus sont similaires : tout le monde est "ami". L’approche manque de granularité. "Dans les graphes plus standards, un noeud (un ami) appartient en général à une seule communauté. Ce n’est pas conforme à la réalité : on sait très bien que dans la vraie vie, des noeuds peuvent se recouvrir. Ces derniers sont d’ailleurs importants, puisque ce sont ceux qui font passer une information d’une communauté à l’autre", explique Eric Fleury. L’équipe a eu l’idée de s’inspirer de la sociologie et de la notion fondamentale de triangle, et de l’appliquer à l’analyse des réseaux, pour arriver à une identification de communautés plus juste. "Le principe n’a rien de révolutionnaire, et est très simple : si deux personnes sont amies avec une troisième, elles sont amies entre elles", reprend Eric. Les chercheurs exploitent les informations "qui est ami avec qui" sous la forme d’une mesure. C’est la cohésion, qui est la pierre angulaire de leur algorithme, et qui quantifie à quel point un ensemble de personnes forment un groupe social.L’expérience a validé le modèle
Fellows a permis de confronter la théorie à la réalité et prouver que la cohésion était une approche valable. L’expérience a été menée à large échelle sur Facebook. L’utilisateur s’y connecte et valide l’accès à son compte Facebook (via une API). Le programme présente ensuite à l’utilisateur la liste des groupes proposés automatiquement et demande de les noter, de une à quatre étoiles selon la pertinence. Par ailleurs, Fellows propose — si l’utilisateur le souhaite — de créer automatiquement des listes d’amis dans Facebook, réduisant ainsi le temps qu’il lui est nécessaire pour le faire lui-même. Selon l’article, en six mois, les 2157 participants ont amené à la détection de 67750 groupes, et 43589 ont reçu une note. 25,1% ont eu une étoile, 21,8 % deux étoiles, 22,5 % ont reçu trois étoiles, et 30,7 % ont reçu quatre étoiles. Le but n’était pas d’obtenir la plus haute proportion de 4 étoiles, mais bien de vérifier la pertinence de leur modèle. "Nous avons pu prouver qu’il existe une corrélation entre la cohésion, et les notes données à chaque groupe. Ceci prouve que notre algorithme fait sens", conclut Eric Fleury. Les prochains travaux de l’équipe porteront sur l’adaptation de ce modèle aux réseaux complexes.* L'equipe DNET est commune à l'institut et à l'École Normale Supérieure de Lyon, au sein du laboratoire LIP (Laboratoire de l'Informatique du Parallélisme). Elle conduit des recherches théoriques et expérimentales sur les réseaux sociaux afin de mieux appréhender leur structuration et la dynamique des processus de diffusion d'information en leur sein. Elle est dirigée par Eric Fleury, professeur ENS Lyon. Les travaux de recherche liés à fellows et l'expérimentation associée sont menés par Adrien Friggeri, doctorant dans l'équipe DNET.
Publié le 29 juillet 2011
http://www.atelier.net/articles/cohesion-une-mesure-fiable-identifier-communautes
Aucun commentaire:
Enregistrer un commentaire