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 c
omparatif 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.
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 ? »
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 av
ec 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.
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.