Mème : Scrabble international

Nouvelle chaîne dans ma boîte mail, nouvelle analyse de mème sur ce blog (après la F-list, et fait-ou-pas) : le "Scrabble International".

Il s'agit d'une liste de mots de 6 lettres, à laquelle on doit ajouter un mot français :

- de 6 lettres pas encore présent dans la liste

- ayant exactement une lettre de différence avec le mot précédent (dont les lettres sont éventuellement réordonnées).

Sont ajoutés le prénom et la ville du participant, ainsi que sa date de participation. Voilà l'exemple de la liste que j'ai reçue (209 mots). J'en ai trouvé quatre autres sur le net, de 124, 85, 216 et 89 mots, qui montre que la liste a voyagé (par mail, pas sur la blogosphère apparemment) en Belgique d'où elle est partie, en France, en Algérie, en Suisse, au Canada, au Maroc... L'arbre de diffusion à gauche résume l'historique de ces listes.

Je me suis demandé quelle taille pourrait atteindre cette liste, en théorie. Eh oui, car en pratique, comme pour tous les mèmes, les participants ne suivent pas toujours les règles, éviter et tourbe sont deux fois dans la première liste, piéger et pingre dans la cinquième, et je ne parle pas de ceux qui oublient d'inscrire la date, ou prennent un malin plaisir à changer le format pour que je ne puisse pas récupérer toutes les infos facilement avec un script.

Bref, supposons que tout le monde suive les règles, le jeu correspond à construire un chemin qui ne repasse jamais pas le même sommet (en bleu dans l'illustration ci-dessous) dans un graphe :

- dont les sommets sont les mots français de 6 lettres

- dont les arêtes rejoignent deux mots qui ont une lettre de différence.

Quelles sont les propriétés de ce graphe ? Quelle est la taille du plus long chemin qu'il contient ? Est-ce que 6 lettres est la taille de mots la plus adaptée pour assurer le succès de ce mème ? Voici les quelques questions auxquelles je vais tenter de répondre dans ce billet, avant une suite éventuelle qui sera dédiée à une analyse des données des les 5 listes récoltées.

Première chose à faire, construire ce graphe à partir d'une liste de tous les mots français. Je récupère ça chez un collègue marseillais, regroupe les mots par taille en passant tout en minuscules et en enlevant les lettres accentuées : 2 mots de taille 1, 81 de taille 2, 427 de taille 3, 1799 de taille 4, 5897 de taille 5, 13931 de taille 6... Tiens tiens, ça augmente comme ça jusqu'à 50097 (taille 10) avant de redescendre. Mais la longueur du plus long chemin n'est pas directement reliée à la taille du graphe : certes, celui des mots de 10 lettres a plus de sommets, mais il est moins dense (moins d'arêtes), et contient donc probablement moins de longs chemins. Grâce à quelques scripts en Python, voici les réseaux obtenus pour les mots de taille 3, 4, 5, 6, 7, 8 (18 Mo pour le dernier...).

Première chose à faire, calculer les composantes connexes, les parties du graphes où toute paire de sommets est reliée par un chemin. Pour cela (merci Anaïs !) la bibliothèque iGraph en R fait tout le boulot. Téléchargez-la, installez-la (install.packages("igraph")), puis lancez le code suivant :

library(igraph)

g<-read.graph("http://philippe.gambette.free.fr/Blog/2011Scrabble/Mots6.graph.txt",format="ncol")

cc<-clusters(g)

cc$csize

On obtient une composante connexe de taille 13865, et 5 de taille 2. Pour avoir la composition des cinq paires :

V(g)[which(cc$membership==1)-1]

V(g)[which(cc$membership==2)-1]

...

Les 5 paires sont donc : {rococo, corozo}, {hiboux, bijoux}, {puffin, muffin}, {okoume, loukoum}, {zozota, zozote}.

Et la distribution des degrés ?

dd <- degree.distribution(g)

plot(dd)

On obtient l'image ci-contre, qui sent le Poisson...

Quelle est la taille du plus long chemin dans ces graphes ? Eh bien ce problème est NP-complet (difficile à résoudre pour un ordinateur), et je n'ai pas encore essayé de le soumettre (pour les mots de taille 3, car je doute qu'il arrive à traiter un graphe à 10000 sommets et 400000 arêtes) au programme linéaire en nombres entiers récemment ajouté par Nathann dans Sage (au moins j'ai - enfin - installé le logiciel). En revanche j'ai programmé un script qui lance un millier de chemins au hasard, en partant d'un sommet également choisi au hasard, et enregistre la taille de chacun des chemins obtenus.

J'obtiens les valeurs moyennes suivantes : la longueur maximale parmi tous les chemins trouvés augmente jusqu'à 8 lettres inclus (je n'ai pas testé les graphes pour les mots de taille supérieure), en revanche la longueur moyenne des chemins atteint un maximum pour le graphe des mots de sept lettres (cliquez sur le graphique pour voir la distribution des longueurs de chemins obtenue) :

Vous me direz qu'en calculant simplement le degré moyen des sommets du graphe, on obtenait justement un maximum pour une taille de mots de 6, avec un nombre moyen de voisins de 28,7 qui correspond à peu près à la valeur où le pic de la loi de Poisson est atteint ci-dessus... J'aimerais bien savoir comment Eliane de Bruxelles a choisi la taille de 6 quand elle a conçu ce jeu. En tout cas c'était bien trouvé, et il ne reste plus qu'à trouver quelques milliers de participants pour commencer à rendre le jeu difficile... A moins que vous ne vouliez vous lancer dans une stratégie de blocage du jeu, en l'orientant vers un "cul-de-sac", soit en faisant revenir le chemin vers des sommets déjà visités, soit vers des sommets de faible degré...

Si vous avez participé au mème, et que vous avez une liste différente de celles montrées ci-dessus, ça m'intéresse, dans la perspective d'un prochain billet sur le sujet : indiquez en commentaire une adresse de page web où vous l'avez placée, ou envoyez-la moi par courriel en indiquant dans le sujet "Scrabble International". Et si vous voulez lancer le mème sur la blogosphère, faites-vous plaisir, en citant des blogs pour les inciter à propager la chose ! Plutôt des blogs féminins, au vu des prénoms dans mes listes...

Les sections d'un article scientifique (1/2)

J'utilise fréquemment le nombre de réponses Google : le plus souvent pour l'orthographe, mais aussi pour diverses expérimentations en soumettant un nombre massif de requêtes, comme dans mon billet précédent (ou tous ceux tagués par mon utilitaire qui permet de le faire, FuryPopularity). Même s'ils ne sont pas toujours fiables - j'y reviendrai au prochain billet de la série - ils sont le plus souvent assez parlants, comme peuvent l'illustrer ces dessins de XKCD.

Aujourd'hui, ils vont nous servir à visualiser le découpage traditionnel d'un article scientifique en sections. Le point clé est que l'on y annonce généralement son plan en introduction, en utilisant, de façon parfois un peu pesante, la formulation "In Section [X], we [VERB]", comme dans ce fameux article qui promettait : "In Section 7, we discuss how to draw a rooted split network" (comment ça j'ai pas le droit de faire ma pub sur mon blog ?).

Alors que fait-on quand on a une liste d'un peu plus de 3000 verbes anglais depuis cette expérience, et un Fury Popularity fonctionnel ? Eh bien on profite de ses nuits pour envoyer tout ça automatiquement à Google, en faisant varier le numéro de section X de 1 à 10... Par manque de temps, je repousse au prochain billet sur le sujet mes arguments sur le fait que ça a du sens, bien que tous les articles n'utilisent pas cette formulation en introduction, et je passe directement à la méthodologie. Tout d'abord, récupération des nombres Google :

• pour 3656 verbes anglais (cette liste de verbes était donnée à la fin de ce billet) pour X variant de 1 à 3.
• pour "seulement" les 940 verbes qui ont eu des résultats à cette étape précédente, pour X variant de 4 à 10.

Les données sont alors stockées dans ce fichier tableur, et normalisées :

• en colonne tout d'abord, divisées par le nombre total de résultats à X fixé, ce qui fournit pour chaque verbe un pourcentage d'apparition,
• en ligne ensuite : pour chaque verbe, soustraction de la moyenne de ses pourcentages d'apparition, puis division par l'écart type.

Avec les données ainsi obtenues, en gardant uniquement les verbes donnant plus de 5000 résultats au total, et en retirant les auxiliaires are, have et will, on obtient ce résultat :

Héhé, surpris, hein ? Pas de diagramme, pas d'arbre, pas du nuage ! Eh oui, après un module de biostats qui m'a initié à R, et avant de plonger dans les subtilités de l'utilisation de l'analyse factorielle en lexicométrie, cet essai de visualisation de données par analyse en composantes principales donne un résultat tout à fait convenable. Il permet en effet de représenter les données en deux dimensions, au lieu des 6 initiales (1 par section), de la meilleure façon possible.

Le code R (le logiciel est téléchargeable gratuitement ici) est le suivant :
donneesSections <- read.csv ("http://philippe.gambette.free.fr/Blog/200812Publis/ResultsR.csv", dec=",", sep=";",row.names=1)
mesures<-donneesSections[, c("Section1","Section2","Section3","Section4","Section5","Section6")]
acp<-princomp(mesures)
biplot(acp,cex=0.5)
acp<-princomp(mesures,cor=TRUE)
biplot(acp,cex=0.5)

Alors n'étant encore pas très familier avec la technique, j'ai quelques questions théoriques et pratiques, que j'espère bien résoudre bientôt (avec l'aide de mes lecteurs ?) :

• quelles sont les différences, fondamentales et pratiques, entre l'ACP qui fonctionne sur la matrice de corrélation (qui correspond à l'option cor=TRUE) et la matrice de covariance ?
• existe-t-il des options dans R pour choisir les dimensions du dessin ?
• existe-t-il des logiciels ou applications web qui fournissent les résultats d'une ACP dans un format plus pratique, permettant de choisir la taille des étiquettes, ou bien de visualiser deux étiquettes superposées

En ce qui concerne l'analyse de cette image, je détaillerai certainement plus les conclusions au prochain billet (en vérifiant notamment si les règles théoriques de rédaction d'un article scientifique trouvables ici ou là semblent vérifiées), mais voici quelques premières remarques :

• les sections 5 et 6, et surtout 1 et 2 semblent avoir des rôles très proches. Ceci peut s'expliquer pour 1 et 2 par le fait que le plan peut se trouver soit dans le résumé, hors section, soit dans la section 1 : ainsi, la partie introductive, à laquelle les verbes begin, introduce, start, recall, formulate sont associés, se trouve en section 1 ou 2, tout comme la partie d'état de l'art : review, survey, collect.
• Pour les sections 5 et 6, c'est la longueur variable des articles qui fait que les verbes indiquant la validation finale avec compare, evaluate, perform, explore, ou le bilan, summarize, conclude, ont des profils différenciant peu les sections 5 et 6.
• Les sections 3 et 4 sont visiblement dédiées aux gros morceaux : assume, investigate, describe, construct, calculate, determine, demonstrate ; discuss, analyze et extend, apparaissent alors qu'on se rapproche des sections finales.

A bientôt pour la fin de cette discussion, et le retour de quelques nuages ! Il y aura certainement un billet spécial XKCD entre les deux pour patienter.