27 avril 2007

Postures et énigme politicombinatoire

Avec les débats Royal-Bayrou demain et Royal-Sarkozy la semaine prochaine, on peut espérer que la campagne va toucher au fond des discours de chacun, après avoir plutôt touché le fond. La campagne du premier tour a été une succession de postures (et d'impostures ?).

Les trois candidats arrivés en tête ont tenu à incarner le politique nouveau, avec en particulier une liberté de ton rafraîchissante, à laquelle chacun a ajouté ses spécificités. Ségolène Royal s'est définie comme l'incarnation de l'ordre juste, de la femme, de la mère, du vote utile anti-Le Pen. Pour Nicolas Sarkozy, c'était la fermeté, la réforme ou rupture, et plus récemment le rassemblement. François Bayrou a commencé par être l'opposant aux puissances médiatiques, pour devenir le centriste en lutte contre le bipartisme, ou encore le vote utile anti-sarkozy.

Ces postures ont l'avantage d'être très faciles à médiatiser. Elles créent la polémique et peuvent facilement être démontées par les adversaires : les qualités mises en avant par le candidat sont retournées contre lui, ou tout simplement niées preuve à l'appui ou presque. Royal a donc subi le machisme et les accusations d'incompétence. Sarkozy est devenu un facho, ou l'héritier du bilan du gouvernement sortant. Bayrou, un utopiste sans majorité à l'assemblée profondément ancré à droite.

Le débat "proposition contre proposition" sur des questions précises n'a jamais été mis en avant à la télévision ou dans la presse écrite. Ce que j'aurais aimé avoir, ce n'est pas le catalogue de propositions de chacun des candidats, mais plutôt, sur chaque thème, les différents points de vue et les convergences. Des tentatives de synthèse ont été entreprises, mais elles ne faisaient pas apparaître clairement les consensus et les incompatibilités. C'est une démarche que j'aurais attendu de la part des centristes : combien de points du pacte présidentiel de Ségolène Royal seraient acceptés aussi par Nicolas Sarkozy ? On en a vu défiler, des pactes ou questionnaires (celui de Nicolas Hulot, du collectif AC Le Feu, des langues, le questionnaire sur les logiciels libres...) : ce sont devenus des packs de propositions ne donnant lieu à aucun débat contradictoire, aucun résumé synthétique.

Et les sites qui prétendaient avec une série d'une vingtaine de questions calculer votre similarité avec tous les candidats ? Où sont les tableaux des réponses des candidats à ces questions ? Pour une fois qu'on aurait pu avoir un avis clair (voire binaire) à des questions censées nous déterminer politiquement de la part de tous les prétendants...

On a préféré la politique spectacle, plus facile à "vendre", et plus ludique. Attention, je ne le critique pas totalement : déjà, ça a permis d'atteindre presque 85% de participation au premier tour. Je vais même plus loin, c'est l'appréciable, voire nécessaire, première étape d'une démarche qui me plaît : commencer par des légèretés pour motiver à "mettre les mains dans le cambouis". Exprimé par Stefan Zweig dans La Confusion des Sentiments : "celui qui n'est pas passionné devient tout au plus un pédagogue ; c'est toujours par l'intérieur qu'il faut aller aux choses, toujours, toujours en partant de la passion." Et si on a droit à de vrais débats de fond calmes et intéressants dans les jours qui viennent, après la passion de l'avant premier-tour, la campagne présidentielle de 2007 sera réussie !

Et maintenant à moi d'illustrer cette démarche, en motivant un problème combinatoire par une petite histoire de politique d'image et de posture : le Problème du Club de Réflexion, que j'appellerais presque le problème du siècle (issu d'une discussion initiée avec Nergal)...

F.B. affirme n'avoir pas parlé à N.S. depuis 3 ans. Ces deux hommes appartiennent à un même club de réflexion, qui se réunit tous les mois de la façon suivante : parmi tous ses n membres, un certain nombre est invité à venir manger à l'Automobile Club de France. Ils peuvent alors discuter autour de tables de k personnes. Disons qu'il y a t tables. En pratique il paraît que k=7, qu'environ 300 personnes participent à chaque dîner soit t=43, et que le club a environ n=700 membres. La première question, facile, consiste à déterminer quelle est la probabilité que F.B. n'ait en effet jamais dîné à la même table que N.S. depuis 3 ans, en supposant que les organisateurs des soirées invitent et placent leurs membres aléatoirement à chaque fois.

Calculons la probabilité à chaque réunion que F.B. ne soit pas à la même table que N.S. Est-ce que N.S. est là ? Il y a seulement tk invités, donc il n'est pas là avec proba (n-tk)/n. S'il est là, alors F.B. n'est pas là avec proba (n-tk)/(n-1), et il est là avec proba (tk-1)/(n-1). Si les deux sont là, alors une fois que N.S. est placé il y a k-1 chaises vides autour de lui, et il reste à placer tk-1 convives donc F.B. n'est pas à sa table avec proba (tk-k)/(tk-1). Comme on le voit avec l'arbre de toutes les possibilités ci dessous, on obtient la probabilité que F.B. ne soit pas à la table de N.S. à une réunion par la formule :

P=(n-tk)/n + tk/n ((n-tk)/(n-1) + (tk-1)/(n-1).(tk-k)/(tk-1))


Soit pour les valeurs de n, t et k données une probabilité de 99,6309% que F.B. et N.S. ne se rencontrent pas à une certaine réunion. On élève à la puissance 36 pour chacune des 36 réunions en 3 ans : il y a 87,5% de chances qu'ils n'aient effectivement pas mangé à la même table pendant tout ce temps...

La deuxième question, beaucoup plus compliquée, consiste à trouver la stratégie de placement des organisateurs. On considère raisonnablement qu'ils veulent que tout le monde parle avec tout le monde. Quel est donc le nombre minimum de réunions à effectuer pour qu'en effet tout le monde ait mangé au moins une fois avec tout le monde ? Et comment inviter et placer les membres pour atteindre ce minimum ? En déduire le nombre maximal de réunions consécutives où N.S. et F.B. ne mangent pas à la même table.

Si on prend la restriction de ce problème avec n=tk et k=2, ça revient à un problème d'organisation de tournoi d'échecs : on a n participants, et on fait jouer en parallèle t parties, en cherchant à minimiser le nombre de parties permettant que tout le monde ait joué contre tout le monde. Cela nous permet d'introduire de la théorie des graphes : on considère le graphe complet, c'est à dire qu'on relie un ensemble de 2k sommets (les joueurs) par toutes les arêtes possibles, chaque arête correspondant à une partie d'un joueur contre l'autre. On va colorier les arêtes de telle sorte que les couleurs correspondent à des parties qui peuvent se dérouler en parallèle, c'est à dire que deux arêtes partageant un même sommet n'auront pas la même couleur. On cherche à minimiser le nombre de couleurs, c'est à dire l'indice chromatique du graphe complet à 2k sommets. Le problème, classique ("promenade des demoiselles"), est résolu ici : 2k-1 couleurs (donc 2k-1 parties) suffisent, vous avez même la configuration des parties !

Pour le cas général je cherche encore, quelques variantes du problème sont réunies sur cette page...

23 avril 2007

Bilan des sondages du premier tour

SarkolèneLe premier tour des élections présidentielles hier a marqué un succès, celui des sondeurs, dont les estimations se sont révélées assez correctes.

Le journal Le Monde proposait une formidable visualisation en Flash de tous les sondages d'intentions de vote pour la présidentielle française parus depuis octobre 2006. Bon, Flash, c'est pas le meilleur format pour récupérer automatiquement les données... mais l'ergonomie permettait quand même une bonne récupération manuelle. Toutes ces données sont donc disponibles dans ce fichier Excel (ou OpenOffice), voici quelques graphiques qu'on peut en extraire et analyser, maintenant que des résultats définitifs ont été publiés.

L'interface du Monde permet de visualiser pour chaque institut l'ensemble des sondages qu'il a publiés : résultat, on obtient des courbes assez irrégulières dont les tendances générales n'apparaissent pas vraiment. Superposer tous les résultats donne un nuage de points beaucoup plus parlant (regardez ce que ça donne pour Bush chez le "Professor Pollkatz") :

Ceci dit, tout ça n'est pas vraiment parlant si on veut visualiser les 12 candidats (ou comparer plusieurs indices), pour cela il vaut mieux effectuer une moyenne, qui aura pour effet de fournir une courbe un peu plus lissée. C'est donc ce que j'ai fait, en calculant pour chaque jour la moyenne obtenue d'après le dernier sondage paru pour chaque institut (ça se fait très bien avec les formules Excel/OpenOffice, et franchement, c'est plus joli/lisible/rigoureux que les courbes du CEVIPOF, non ?).

Présidentielles sondages premier tourEvidemment l'extrémité droite de la courbe correspond aux résultats réels. On remarque que les trois principaux candidats avaient été généralement sous-évalués, et Jean-Marie Le Pen sur-évalué, et supposé assez haut par les électeurs pour motiver un vote "utile" pour Ségolène Royal au premier tour visiblement. La montée de François Bayrou commence à la mi-janvier, mais il décroît un mois avant la date fatidique. Tiens, ce serait intéressant de les superposer précisément avec sa courbe de Presse2007, j'ai l'impression à l'oeil nu que celle des sondages précède légèrement la popularité dans la presse (sachant que la courbe des sondages présente un retard intrinsèque lié au délai de publication, et à une sorte de délai d'harmonisation des 6 instituts puisque c'est une moyenne...).

Au passage, on peut s'amuser des approximations faites par les différents instituts, dont la somme des intentions de votes publiées n'atteint pas toujours 100%. Puisque les nombres ne sont pas "bruts" et sont issus d'une petite cuisine secrète, ils pourraient quand même s'arranger pour les arrondir dans ce sens. Ceci dit, ce cas arrive assez rarement, et ceux qui mettaient à jour le document Flash du site du Monde auraient pu tester à chaque fois la somme, pour vérifier leurs chiffres (qui font apparaître quelques petites erreurs... bah, au moins, ils les corrigent rapidement).

Et maintenant voyons quels instituts avaient le mieux deviné les résultats. Pour ça, on peut calculer une distance (je n'indique pas l'échelle qui ne veut pas dire grand chose, il suffit de retenir que plus c'est haut, plus l'erreur est grande, voir le fichier Excel pour les détails ou essayer d'autres distances) entre les résultats prévus (dernier sondage paru vendredi dernier ou avant), et ceux réellement obtenus : bravo à Ipsos (labosonic m'alerte en commentaires sur le fait qu'il existait des données pour vendredi pour BVA aussi, qui fait alors mieux que Ipsos) ! J'ai ajouté aussi la moyenne des sondages des 6 instituts et le dernier sondage du site Votez2007.com. Avec ce dernier, on se rend compte que publier des sondages sérieux nécessite une expérience que ces professionnels revendiquent et détaillent quand ils sont mis en cause. Il peut sembler contre-intuitif que la moyenne donne de moins bons résultats que 4 sondages parmi 6. En fait on découvre en apprentissage automatique que combiner de bons outils pour en faire un meilleur ne se fait pas vraiment naïvement (par une moyenne), mais avec des techniques un peu sophistiquées.
Voir aussi : une excellente analyse, plus détaillée, des taux d'erreur des sondeurs.

On peut donc faire totalement confiance à nos chers sondeurs pour nous prévoir le résultat du second tour... Ou pas. Vous avez entendu les sondages à la sortie des urnes ? Pour ça il ne fallait pas lire les blogs, mais écouter la radio suisse romande : vers 18h30, on apprenait que Royal et Sarkozy étaient à 26%, Le Pen à 17 et Bayrou à 16 ! Quelques minutes plus tard heureusement, les premières estimations tombaient, un peu plus conformes à la réalité.

La suite ici (bilan des sondages de 2002)...

20 avril 2007

Analyse du buzz F-List de la blogosphère francophone (3/3)

Ouf ! Après plusieurs soirées passées à corriger le corpus, les résultats intermédiaires, et quelques 800 lignes de code, voilà enfin le post de conclusion sur les F-listes.

Où l'on remarque l'importance de l'effet de gratitude dans la poursuite de la chaîne ; où l'on découvre une liste de blogs francophones intéressants que la F-list était censée promouvoir ; où l'on détermine la liste des blogs qui ont le plus bénéficié de la chaîne ; où l'on voit que cette seconde liste ne contient naturellement pas la première...

Commençons par l'effet de gratitude, c'est le principe du "tu me cites ? je te cite !". 95 blogs sur 185, soit plus de 51% des participants, étaient déjà présents dans la F-list récupérée pour construire la leur (voir l'arbre de diffusion ici) ! On peut donc supposer qu'ils n'ont pas découvert la liste simplement en lisant leur blog favori, mais plutôt en se voyant cités, grâce aux rétroliens, ou peut-être en identifiant un blog leur amenant des visiteurs grâce à des outils de statistiques de fréquentation, ou encore... eh bien demandons-leur ! Si vous êtes dans la liste ci-dessous, c'est que vous faites partie de ces participants qui ont repris une F-liste dans laquelle ils avaient déjà été ajoutés : comment l'avez-vous découverte ? Merci de répondre en commentaires ! En ce qui me concerne, c'est dans les rétroliens du blog de Jean Véronis.

fiuuu.com bluebayou34.free.fr/dotclear/index.php www.digiboy.fr www.spirit-of.com hisaux.free.fr blog.localingo.com www.underdeepwater.com/lab.oratoire yellowman.wordpress.com blog.gloups-news.info stephanerangaya.kyotek.com www.tagle.ca/wordpress www.yannicklejeune.com www.eyes-wide-shoot.be mallo-blog.new.fr www.libert-fr.com lafrange.wordpress.com befaure.blogspot.com mesgoutsmescouleurs.blogspirit.com www.net-marketing.fr damdam.typepad.com www.estrade.ca www.go-referencement.org www.stephguerin.com fredfortin.net/Blog ambiome.net/blog www.martinbreton.com www.supergab.com christellefv.com/weblog www.zecanada.com hamadiblog.blogspot.com akratique.blogspot.com fraises.blogspot.com leperiscope.blogspot.com www.goudaille.com www.nayezpaspeur.ca journal.covonline.net leblogdemateusz.blogspot.com osmany.hautetfort.com www.melissamonaco.com/wordpress maheanuu.free.fr family-counts.blogspot.com stephanetauziede.com mmelovecraft.livejournal.com ancienetmoderne.blogspot.com arnolux.typepad.fr aodai.typepad.com fredofenua.blogspot.com www.darjeeling-in-the-teapot.com lemondedetitus.blogs.letelegramme.com hysteriesilencieuse.free.fr soleilentete.canalblog.com karamailhe.canalblog.com phinebacker.blogspot.com www.netwizz.net/blog blog.galerie-net.com www.williamperes.com ru3.com/luc marcus.retais.fr les5sensselonchristian.typepad.com lesfemmesendisent.blogs-handicap.com planetargonautes.typepad.fr www.emich.be www.benjaweb.be/blog www.vinch.be/blog blog.barbayellow.com www.zewoc.com arkandis.blogsome.com www.nellio.com lovnyterrestre.vox.com bayart.typepad.com/blog www.buzzdunet.com www.greg-b.net corps-et-sante.typepad.fr www.buzztogether.net gaduman.blogspot.com www.netandco.info misstics.canalblog.com utovic.hautetfort.com viralbuzzandco.blogspot.com www.commalad.com cheguerilla.blogspirit.com sendtofriend.blogspot.com www.sylvainbriant.com www.page2007.com vmaurin.free.fr/dotclear elayeillon.hautetfort.com www.voxinablog.com www.arts-et-talents.com fadhilabrahimi.blogspirit.com www.duperrin.com www.cooperatique.com www.bizfriz.com www.jbouteiller.net 2ro.free.fr/blog le.bisounours.eu/index.php

Xavier, en démarrant la chaîne, motivait son initiative par la découverte de petits blogs francophones intéressants. On peut supposer que c'est le cas de blogs qui ont été insérés dans la F-list par plusieurs blogueurs différents. Voici la liste des 39 blogs ajoutés indépendamment plus de quatre fois (il y en a une centaine qui ont été ajoutés plus de trois fois) :

Si vous avez été cité dans la F-list, vous pouvez savoir qui vous a ajouté en recherchant votre blog parmi la liste complète disponible ici !

Comme vous avez pu le constater, les blogs ajoutés souvent à la F-list n'ont pas nécessairement été ceux le plus souvent cités, et finalement les grands gagnants en termes de citations (voir aussi : classement Technorati, voir aussi : pagerank) sont les suivants (93 blogs avec 50 citations ou plus, dont 18 participants à la F-list) :Bilan, si vous voulez créer le prochain buzz viral de la blogosphère francophone, citez des blogs de la première liste (ils vous le rendent bien), arrangez pour le faire connaître de ceux de la seconde (ils sont lus par des gens susceptibles de réagir sur leur blog), et il ne vous servira à rien de citer les blogs de la troisième qui ne sont pas en gras (s'ils ont vu passer la F-List, ils ont choisi de ne pas y participer).

N'hésitez pas si vous avez d'autres aspects du phénomène sur lequel vous voulez des précisions, vous pouvez aussi utiliser directement les fichiers générés au cours de l'étude.

1 avril 2007

Analyse du buzz F-List de la blogosphère francophone (2/3)

Le voilà enfin, l'arbre de diffusion de la F-list que je promettais il y a une semaine :

Cliquez sur l'image pour naviguer sur l'arbre et voir à quel blog correspond chaque point. Cet arbre donne tout de même une bonne interprétation du déroulement du phénomène : on peut voir un certain nombre de paliers qui rythment la transmission de la F-liste, c'est à mon avis là qu'il faut chercher les sites influents de la blogosphère (parmi les participants). Le site dont la F-list a été reprise directement le plus souvent est sendtofriend, dont le noeud, repassé en bleu dans l'arbre, a 11 fils (on remarque toutefois que ces fils ). La profondeur de l'arbre (la longueur de la plus longue chaîne, indiquée en rouge) est 18 :
Xavier - Bozarblog - BAO - 2ro - Jérôme Bouteiller - Bertrand Duperrin - Activeille - Démodéouss - Le web a meilleur goût - Mimie In Vivo - Planetargonautes - Marcus Retais - Luc - Woueb - Loneline - Ataegina - William Peres - Art pour tous.

Je détaille la méthode de construction, que je tenais à faire de façon automatique, et qui s'est révélée moins efficace que prévu. La principe de la F-list était qu'un blogueur B reprenait celle du blogueur A par qui il l'avait découverte, pour y ajouter ses propres liens favoris. Théoriquement donc, si la liste est transmise du blogueur A vers le blogueur B, celle de B contient celle de A. L'idée était donc de construire le graphe d'inclusion des F-listes, c'est à dire un ensemble de points (ou "noeuds") représentant chacun une F-liste, qu'on relie par une flèche (un "arc orienté") si une des listes contient l'autre. Si l'on dessine ce graphe, il est assez illisible à cause de la transitivité de la relation d'inclusion : si A contient B et que B contient C, alors A contient C, il y a donc des arêtes "superflues" dans le graphe. Les éliminer correspond à l'opération de réduction transitive, décrite dans la figure ci-dessous. Pour tout arc reliant A à B, s'il existe un arc reliant B à C et un arc reliant A à C, alors celui reliant A à C est superflu donc il faut l'effacer.

Si l'on effectue cette opération le plus de fois possible, on obtient un diagramme de Hasse qui représente très lisiblement les inclusions entre les listes étudiées, comme on le voit sur la figure ci-dessous (à côté de chaque noeud j'ai mis un exemple de F-list contenant les liens a, b, c, d, e ou f, le sens des flèches correspond au fait qu'une liste en contient une autre, c'est donc le sens inverse du sens de transmission des listes).

En faisant un tel traitement des listes, je comptais obtenir un arbre (où les branches ne se rejoignent jamais). En fait, le cas représenté dans la figure ci-dessus, c'est à dire que deux blogueurs ajoutent indépendamment les mêmes blogs dans leur liste (b c et d dans la figure), apparaît assez souvent, pour une quarantaine de listes. Je suis donc allé vérifier dans chacun de ces cas douteux où le blogueur disait avoir trouvé la liste (pour certains, comme Miss Tics, j'ai encore un doute...). Dans d'autres cas, le blogueur avait fait une erreur en recopiant la liste (ou avait choisi de ne pas la recopier).

J'ai donc vérifié l'ensemble de l'arbre, et le résultat de la méthode automatique n'est pas vraiment brillant : 77 erreurs d'identification du "père" sur un ensemble de 184 F-listes. Il faut tout de même relativiser ce taux d'erreur de 42% en notant que de nombreux blogueurs ont publié des F-lists ne respectant pas scrupuleusement les règles, qui n'étaient pas tout à fait claires (il n'était pas évident qu'il fallait ajouter les blogs lus régulièrement à la fin de la F-list, ce qui aurait pourtant facilité l'interprétation des listes, les chaînes de diffusion se trouvant alors en début de liste).

Conclusion : l'épisode 3 !