Retour d’expérience d’un projet d’étudiant

Par Quentin MARINIE et Fabien VIOSSAT, étudiants 3A Telecom Bretagne.

social network concept

Sur Facebook, ce sont près de 10 milliards de messages et 4,75 milliards de partages qui sont enregistrés chaque jour. Sur Twitter, le maximum de tweets par seconde est de 143 199. Si l’on rapporte ces chiffres à la courte durée de vie de ces entreprises (respectivement 12 et 10 ans) on se rend compte de l’importance croissante des réseaux sociaux dans notre vie de tous les jours. Mais très certainement vous-même appartenez à d’autres réseaux sociaux ou communautés telles que Wikipédia, Copains d’avant, Instagram, LinkedIn ou encore la communauté de votre fournisseur de forfait téléphonique.

Ces nouvelles solutions de communication ont un potentiel énorme mais les entreprises font alors face à de nouvelles problématiques : Comment gérer des millions d’individus ? Comment savoir si un forum ou une communauté est en « bonne santé » ?

Ce sont les questions auxquelles Standing On Giants, fournisseur de plate-formes pour communautés et filiale de Telefonica (UK), tentent de répondre en collaboration avec le département LUSSI de Télécom Bretagne. Il nous a donc été proposé (Quentin MARINIE et Fabien VIOSSAT) dans le cadre du Projet Ingénieur de la filière ISA de mener une phase de cadrage de cette mission. Encadrés par Mme Cécile Bothorel et M. Laurent Brisson, tous deux enseignants-chercheurs dans ce même département, nous avons pu entamer la phase préliminaire du projet. Cet article constitue notre retour d’expérience sur notre mission intitulée « Mise à disposition d’une boîte à outils pour Data Scientist ».

Ancrer son travail dans la durée…

Présents sur les réseaux sociaux depuis plusieurs années, nous nous sommes aperçus que nous étions purement et simplement novices dans l’analyse de leur utilisation. Guidés par nos tuteurs, nous nous sommes intéressés aux statistiques ainsi qu’à la théorie des graphes qui, comme dans de nombreux cas, permettent de solutionner nombre de problèmes. Lecture de thèses, recherche d’ouvrages ou d’articles sur internet mais encore prise en main d’un serveur, découvertes de packages sur différents langages ont été notre quotidien. Les premiers instants s’apparentaient donc à un état de l’art du domaine, nous avons ainsi pu donner une orientation initiale au projet.

Cette démarche s’inscrivant dans une mission durable, nous devions constamment donner une traçabilité à nos recherches, rédiger des documents présentant nos résultats ou encore proposer des tutoriels sur l’utilisation de méthodes.

En effet, un des points importants était la pérennité des résultats : notre étude ne durant que 6 mois et la mission étant destinée à durer plus longtemps, nous nous devions de laisser des traces pour garantir la bonne compréhension de nos travaux.

Où chercher ? Que chercher ?

Un des intérêts d’une telle mission est que d’une semaine à l’autre, avec l’obtention de résultats, il est nécessaire de réorienter les recherches. Des réunions étaient donc prévues avec nos tuteurs de manière à présenter ces résultats, discuter de ceux-ci et enfin fixer les prochains objectifs.

S5_2016_Mission

Il a par conséquent fallut effectuer de nombreux tests sans savoir s’ils allaient être concluants. Comme prévu, nombres d’entre eux se sont révélés peu intéressants pour la poursuite de l’étude. Cet aspect peu motivant était pourtant nécessaire.

Nous avons certainement autant appris de nos échecs que de nos découvertes.

La présence de nos encadrants était bien évidemment essentielle, dotés d’une plus grande expérience dans ces domaines, leurs intuitions se sont souvent révélées utiles et vraies. Cet appui nous a permis d’avancer bien plus vite que par nos simples recherches et, avec plus de recul, nous réalisons que le projet final a très peu à voir avec l’idée initiale que nous en avions.

Le bon outil pour le bon usage !

Neo4J, Python, R, NetworkX voici les premières pistes que nous avions pour explorer les graphes. Après une première prise en main de certains et une recherche sur d’autres logiciels, langages ou packages, nous avons sélectionnés ceux qui nous paraissaient à première vue les plus adaptés. Par la suite, nous avons dû approfondir nos recherches sur ces solutions.

Quelle solution convient la mieux à nos objectifs ? Un package présent sur Python et R est-il mieux documenté ou plus efficace sur l’un ou l’autre des langages ? Là encore de nombreux tests ont été réalisés sur nos propres machines avec à nouveau des tentatives non concluantes mais permettant de comparer les différentes solutions.

Cependant, nous avons assez rapidement fait face aux limites de nos ordinateurs. N’étant pas en possession des datasets de Standing On Giants, nous avons testés différents algorithmes classiques d’études de graphes (clustering, proximité, centralité, taille de cliques…) sur des s5_2016_Scalabitydatasets trouvés sur internet et aux caractéristiques bien différentes (de 4000 individus à près de 10 millions). En concertation avec nos encadrants, nous nous sommes alors vus attribuer un serveur de calcul du département LUSSI. L’idée étant de tester la scalabilité des packages sur des graphes de dimensions semblables à ceux susceptibles d’être fournis par Standing On Giants. Nous voulions ainsi tenter de trouver des liens ou des généralisations entre le temps d’exécution de certains algorithmes gourmands en ressources et les paramètres même du graphe. Tout cela ayant pour finalité de pouvoir donner une évaluation du temps d’exécution d’un algorithme sur un graphe uniquement en fonction de ses paramètres (cf. notre article sur ce même blog). Un serveur de 128 Go de RAM et 32 cœurs a alors été mis à notre disposition pour la durée du projet.

De l’art d’utiliser un serveur !

L’utilisation de ce serveur nous a réservé quelques surprises. Entre les problèmes de connexion au serveur lui-même, les problèmes de connexion internet via tunnel SSH, les mises en place problématiques de nos environnements R et Python ou encore les scripts qui semblent tourner sans fin, il nous a fallu nous accrocher. Initialement, cela nous semblait tout aussi simple que de prendre en main un terminal sous Ubuntu mais nous nous sommes alors rendu compte qu’une tâche aussi banale qu’importer un fichier s’avérait compliquée. ferme_serveursUne fois le serveur et ses configurations mieux maîtrisées, les scripts ont pu être lancés (en tout une trentaine entre R et Python) dont certains ont été abandonnés car trop longs. De plus, une partie des résultats était à nouveau inexploitable ou n’apportaient pas d’informations quant aux relations entre temps d’exécution et paramètres du graphe (diamètre, densité, réciprocité…). Un serveur n’est pas aussi transparent qu’un ordinateur physique et cela implique pour son utilisation une grande maîtrise de ce dernier et des compétences d’administrateur système !

Ce qu’on en retient

Il y a donc différents aspects qui ressortent de ce projet.

Tout d’abord, il fut très intéressant de travailler sur une mission concrète d’entreprise d’autant plus lorsqu’elle a trait à des problématiques actuelles.

En effet, l’utilisation de la théorie des graphes pour décrire les réseaux sociaux est en pleine expansion et avoir pu en apprendre un peu plus auprès d’enseignants-chercheurs a été très enrichissant.

Cette approche assez exploratoire nous a également apporté un aperçu du travail effectué en recherche dans les différents laboratoires de Télécom ou même d’ailleurs.

Il n’est pas simple de devoir remettre souvent ses résultats en question et d’accepter que certaines tâches effectuées n’auront pas d’utilité pour la suite du projet. Enfin, et plus personnellement, cela nous a permis d’élargir notre domaine de connaissance : théorie des graphes, utilisation d’un serveur de calcul, découvertes de packages, lecture des thèses. Tous ces éléments ont fait de ce projet une expérience réellement intéressante et nous souhaiterions remercier nos deux encadrants, Cécile Bothorel ainsi que Laurent Brisson, de nous avoir soutenus, supportés et guidés lors de cette mission.

Faut-il passer sur une plate-forme Big Data ou non ?

Par Quentin MARINIE et Fabien VIOSSAT, étudiants 3A Telecom Bretagne.

L’objectif de notre projet est de pouvoir analyser des communautés de forums, parfois très populaires et très actives, à l’aide de la théorie des graphes. A terme, nous souhaitons équiper des Community Managers d’outils de monitoring de l’activité de leurs forums.

Notre projet d’étudiants en dernière année du parcours Data Science de la filière ISA est de faire un benchmark des outils existants et de pouvoir dimensionner la plate-forme d’analyse en fonction du volume des données à traiter.

Mise en place du benchmark

Nous avons, dans un premier temps établi un panorama des outils existants permettant d’analyse des réseaux d’interactions représentant l’activité d’échange sur des forums. Nous avons fait un comparatif des performances de ces outils. Ce cmontreomparatif des performances est tourné uniquement vers l’utilisation d’algorithmes d’Analyse de Réseaux Sociaux (Social Network Analysis en anglais) tel que le calcul de diamètre d’un graphe, le calcul de centralités (intermédiarité, proximité, etc.).

La première information importante que l’on a pu tirer de cela est le fait que nos machines personnelles (laptop) ne nous permettent pas de traiter des graphes de la taille des communautés de forums visées, soit quelques millions de nœuds. Nous avons donc eu recours à un serveur de recherche de l’équipe CNRS Decide du Labsticc à Télécom Bretagne (128 Go de RAM et 32 cœurs) dans l’espoir d’arriver à exécuter ces algorithmes.

S5_2016_igraph

Nous avons récupéré un panel de datasets sur le site SNAP de l’université de Stanford. Ces jeux de données réels sont échelonnés en nombre de nœuds et nombre d’arêtes, allant de 4000 nœuds et 88000 arêtes jusqu’à 3 millions de nœuds et 6 millions d’arêtes. Pour chacun de ces datasets nous avons pu calculer les caractéristiques descriptives des graphes qui nous importaient pour chacune des deux librairies en lice, Igraph-R et Igraph-Python, qui s’avèrent les plus performantes parmi les 7 librairies sélectionnées au départ dont NetworkX.

Igraph-R vs. Igraph-Python : nous avons fait un rapide comparatif des performances de 4 algorithmes sur 6 jeux de données : diamètre, intermédiarité des sommets, centralité de proximité, taille de la clique maximale. Cela nous a montré que Igraph-R est plus performant que Igraph-Python dans 23 des 24 cas comparés.

Notre machine sera-t-elle suffisante pour ce réseau d’interaction ?

Big data ou non ? Dans quel cas de forum faudra-t-il changer de paradigme et passer à une plate-forme Big Data ? Sachant les caractéristiques simples de notre forum, l’outillage sur notre serveur sera-t-il suffisant ?

La problématique est ici simple (et très répandue !)  : « puis-je continuer à utiliser mes outils historiques, que je maîtrise et qui procurent une grande valeur ajoutée, pour ce nouveau jeu de données ? Ou bien dois-je passer à une autre plate-forme, moins riche… et que je maîtrise moins ? »

s5_2016_methodo

Notre volonté de prédire les temps d’exécution des algorithmes s’applique avant tout aux algorithmes de base, utilisés par nos outils maison, et gourmands en termes de temps. Les trois principaux étant :

  • le calcul d’intermédiarité des sommets,
  • la proximité des sommets,
  • le calcul du diamètre du graphe.

Nous n’avons pas eu besoin de considérer la prédiction du calcul du diamètre car des méthodes permettant d’approximer cette valeur existent et réalisent le calcul en un temps machine négligeable (voir par exemple ce que nous avons utilisé : l’algorithme du bout du monde).

Nous avons alors effectué de multiples régressions en changeant la variable explicative de manière à trouver des corrélations avs5_2016_caracteristiques_graphesec les temps d’exécutions.

Les variables explicatives sont des descripteurs simples à calculer sur un nouveau jeu de données : on peut citer ici des caractéristiques de réseaux sociaux classiques tels que le nombre de noeuds, d’arêtes, la densité d’arêtes, ou encore le diamètre (avec la technique linéaire de calcul, nous pouvons nous servir de cette mesure comme caractéristique descriptive de notre réseau).

Ainsi, c’est prêt d’une trentaine de graphes qui ont été tracés et qui n’ont pu aboutir à aucune régression. Toutefois, nous avons obtenu les résultats suivants pour le paramètre composé : diamètre * nombre d’arêtes.

On peut constater que le coefficient de corrélation est ici de 1 avec la combinaison (diamètre * nombre d’arêtes) pour l’ensemble des datasets pris en compte. Il est important de savoir que le coefficient de corrélation maximum obtenu sur l’ensemble des autres graphes était de 0.86 lorsque l’on ne considérait que le nombre d’arêtes et qu’il était impossible d’interpoler la grande majorité des graphiques.

s5_2016_regressions

De multiples axes de progressions semblent possibles, tant sur la validation des régressions que nous avons pu réaliser, que sur les possibilités que cela pourrait apporter.