Jon Kleinberg, le roi rebelle du petit monde

Posté par (page perso) . Modéré par Christophe Guilloux.
Tags : aucun
10
18
mai
2009
Science
L'ACM (Association for Computing Machinery) a décerné son prix Infosys 2008 à Jon Kleinberg, professeur à l'université de Cornell, spécialiste des réseaux sociaux. C'est l'occasion de revenir sur cette notion au cœur de l'informatique actuelle.

La notion scientifique de réseau social est vraisemblablement due à Stanley Milgram. Pour vérifier une idée évoquée par Frigyes Karinthy dans sa nouvelle Chaînes, il lance une expérience en 1967 : il choisit une "cible" et des personnes de départ, puis il envoie à celles-ci des lettres leur demandant de contacter la cible ou, s'ils ne la connaissent pas, de passer le relais (postal) à la personne de leur entourage la plus susceptible de la connaître. Dans tous les cas, on envoie une carte à Milgram pour lui rendre compte. On peut donc considérer Milgram comme l'inventeur de traceroute, anticipant de vingt ans le programme informatique. Le résultat de cette expérience du petit monde est maintenant connu sous le nom de six degrés de séparation. C'est en effet le nombre moyen d'étapes que les lettres ont mis pour arriver à destination. De nombreuses applications, plus ou moins sérieuses, ont été tirées de ce constat. La plus connue est sans doute le nombre d'Erdős : le mathématicien hongrois Paul Erdős a le nombre 0, ses coauteurs 1, leurs coauteurs 2, etc. [1]

Plus scientifiquement, les réseaux sociaux prennent de nombreuses formes dans notre quotidien. Nos amis, notre famille, nos collègues sont autant de cercles dans lesquels nous transmettons des informations. Quel film recommandons-nous d'aller voir, quel produit conseillons-nous d'acheter : autant d'applications des réseaux sociaux qui intéressent beaucoup les professionnels du marketing, mais qui permettent aussi d'échapper à leur influence.

Depuis l'arrivée des nouvelles technologies de communication, les réseaux sociaux prennent d'autres formes. Ils s'appellent maintenant Facebook ou Jabber, mais aussi blogs et SMS, et, bien entendu, World Wide Web. Tous ces réseaux forment des petits mondes et alimentent le buzz actuel de la recherche en informatique.

Dans ce contexte, Jon Kleinberg est un pionnier. Considérant le Web comme un graphe, il a mis au point l'algorithme HITS, qui attribue à chaque site une valeur comme hub (au sens, en français, de plate-forme de correspondance) et une valeur comme autorité. Un bon hub est un site qui donne de nombreux liens de bonne qualité vers d'autres sites : Yahoo!, les listes de recommandations de ceux qui ont les mêmes goûts que vous, etc. Une bonne référence est un site qui contient des informations pertinentes pour vous : Wikipédia, Linuxfr.org, le site de la fédération nationale de votre sport… D'autres algorithmes ont été développés pour trouver automatiquement les pages Web correspondant le mieux à une requête donnée, dont PageRank, utilisé par Google.

Kleinberg travaille sur de nombreux aspects des petits mondes, un sujet important dans plusieurs domaines : informatique, mais aussi sciences sociales, économie… Il a reçu plusieurs récompenses, dont, en 2006, le très prestigieux prix Nevanlinna. Il est aussi connu pour ses excellentes qualités d'enseignant. Ses étudiants le surnomment Rebel King, un anagramme de Kleinberg. Crier une variante de "Kleinberg is Rebel King" en plein amphi est devenu une tradition (exemple en vidéo).

Comme quoi, Mme Michu avait raison avant les scientifiques : le monde est petit.

[1] Personnellement j'ai 5, mais je travaille actuellement avec un 2, donc la promotion est en vue :-D
  • # Imprécision

    Posté par . Évalué à -1.

    C'est en effet le nombre moyen d'étapes que les lettres ont mis pour arriver à destination.

    6 est le nombre maximal.
    • [^] # Re: Imprécision

      Posté par . Évalué à 4.

      Pas du tout.

      Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

    • [^] # Re: Imprécision

      Posté par (page perso) . Évalué à 2.

      D'après Wikipedia (en) :
      Among these chains, the average path length fell around 5.5 or six
      • [^] # Re: Imprécision

        Posté par . Évalué à 4.

        Au temps pour moi, mais c'est bien ce qui est insinué sur l'article de WP francophone, non ?

        Les six degrés de séparation est une théorie établie par le hongrois Frigyes Karinthy en 1929 qui évoque la possibilité que toute personne sur le globe peut être reliée à n'importe quelle autre, au travers d'une chaîne de relations individuelles comprenant au plus cinq autres maillons.

        Ou ça vient de la différence entre la théorie et la preuve ?
        • [^] # Re: Imprécision

          Posté par (page perso) . Évalué à 4.

          La lettre peut passer entre 7 ou 8 mains mais cela ne veut pas dire qu'il n'y avait pas un plus court chemin passant par 6 personnes.
        • [^] # Re: Imprécision

          Posté par . Évalué à 3.

          Il me semble que dit un peu plus formellement ca donne:

          Les six degrés de séparation est une théorie établie par le hongrois Frigyes Karinthy en 1929 qui évoque qu'entre deux personnes quelconques, il existe une chaîne de taille inférieure ou égale à 6 reliant ces deux personnes.

          Bref je ne vois pas de contradiction.
  • # En voilà des approximations...

    Posté par (page perso) . Évalué à 7.

    La notion de réseau social n'est pas du tout une création de Milgram. Les premières mentions sont bien plus anciennes (Simmel dès le début du XXème) et les premières études scientifiques aussi (Moreno dans les années 1930).

    L'expérience de Milgram est très critiquable pour de nombreuses raisons, en particulier le fait que la longueur des chaînes n'est mesurée que dans le cas du succès. Techniquement les données sont censurées (au sens mathématique du terme) : on observe seulement les chaînes qui arrivent à destination. Dans ce cas, la moyenne obtenue (5,5) est une sous estimation grossière de la vraie moyenne sous-jacente. D'autre part, l'expérience n'a bien entendu rien à voir (ou presque) avec l'algorithme utilisé par traceroute.

    Enfin, sans vouloir le moins du monde remettre en question l'apport scientifique de Kleinberg, l'algorithme du pagerank de Page est antérieur à HITS.
    • [^] # Re: En voilà des approximations...

      Posté par (page perso) . Évalué à 2.

      Les premières mentions sont bien plus anciennes (Simmel dès le début du XXème) et les premières études scientifiques aussi (Moreno dans les années 1930)
      Au sens où on l'entend actuellement ? Ce n'est pas l'impression que j'ai eue, mais je suis preneur de références.

      L'expérience de Milgram est très critiquable
      Oui. On peut aussi ajouter plein d'autres choses plus ou moins intéressantes pour la moule moyenne, et obtenir une dépêche trop longue qui ne sera pas lue.

      l'algorithme du pagerank de Page est antérieur à HITS.
      Je te laisse compléter en précisant l'endroit où j'ai dit le contraire.
      • [^] # Re: En voilà des approximations...

        Posté par (page perso) . Évalué à 5.

        je suis preneur de références

        http://en.wikipedia.org/wiki/Social_network en particulier la partie historique.

        On peut aussi ajouter plein d'autres choses plus ou moins intéressantes pour la moule moyenne, et obtenir une dépêche trop longue qui ne sera pas lue.

        On peut aussi éviter les analogies sans intérêt et surtout sans pertinence : au lieu de parler des petits mondes par leur côté médiatique des six degrés de séparation qui n'est pas établi scientifiquement, on peut par exemple parler des travaux de Watts et Strogatz. Mais encore faudrait il connaître le sujet, plutôt que de s'inspirer de la dépêche approximative de l'ACM.

        Je te laisse compléter en précisant l'endroit où j'ai dit le contraire.

        Tu dis que Kleinberg est un pionner des réseaux sociaux (ce qui est très discutable) en citant HITS d'une façon qui laisse entendre que son travail dans le domaine (qui n'a rien à voir avec les réseaux sociaux) est pionner, ce qui est aussi discutable.
        • [^] # Re: En voilà des approximations...

          Posté par (page perso) . Évalué à 3.

          Tu dis que Kleinberg est un pionner des réseaux sociaux
          Des petits mondes. Après relecture, la transition aurait gagné à être plus marquée.

          les analogies sans intérêt
          Je te présente donc mes plus plates excuses pour avoir gaspillé 42.3141592 secondes de ta vie.

          leur côté médiatique des six degrés de séparation
          Ni plus médiatique ni moins pertinent (pour leurs domaines respectifs, bien entendu) que la "loi" de Moore, par exemple. Il ne faudrait pas en parler non plus ?

          on peut par exemple parler des travaux de Watts et Strogatz.
          Je t'en prie. DLFP est ce qu'en font ses contributeurs.
        • [^] # Re: En voilà des approximations...

          Posté par (page perso) . Évalué à 3.

          >>> ais encore faudrait il connaître le sujet, plutôt que de s'inspirer de la dépêche approximative de l'ACM.

          C'est pas très sympa de rabrouer ainsi l'auteur d'une belle news.
          Nul doute qu'un spécialiste d'un sujet peut trouver des imprécisions dans n'importe quel compte-rendu...il n'en demeure pas moins que la dépêche est très intéressante et qu'elle incite à lire d'autres ressources sur le web si on veut approfondir.
          • [^] # Re: En voilà des approximations...

            Posté par (page perso) . Évalué à 3.

            Je n'ai fait que corriger les imprécisions d'une dépêche qui m'a appris l'obtention de ce prix par Kleinberg, ce dont je remercie l'auteur. Mon but n'était pas qu'il prenne mes précisions mal, ce qu'il semble avoir fait, vu le ton de sa première réponse...

            Quant à savoir si c'est une belle dépêche, je suppose que ça dépend du point de vue. Ayant été victime d'un pico emballement médiatique (je dis bien pico, voire femto) suite à un de mes articles de recherche sur un sujet connexe, je dois dire que ma méfiance à l'égard des comptes rendus journalistiques de résultats scientifiques est devenue très forte. La dépêche a à mon avis tous les défauts du genre : analogies infondées, imprécisions, exagération, etc. La dépêche ACM d'origine est dans le même esprit, donc, encore une fois, je ne blâme pas l'auteur.
            • [^] # Re: En voilà des approximations...

              Posté par (page perso) . Évalué à 3.

              Mon but n'était pas qu'il prenne mes précisions mal
              Il y survivra.

              ça dépend du point de vue
              Le tien est typique du scientifique qui n'accepte pas la vulgarisation. Dans les livres, émissions, et autres médias qui présentent des sujets pointus au grand public, l'objectif n'est pas d'atteindre une grande précision mais de faire passer simplement un message. On s'appuie sur ce dont les gens ont entendu parler, on prend des exemples triviaux mais illustratifs. On n'est pas là pour s'assurer qu'on a bien couvert toutes les implications du point (b) du théorème 42 du dernier article paru dans le domaine.

              J'ai pris conscience de ce genre de problèmes en touchant à la vulgarisation, par exemple en participant à l'abécédaire de l'informatique [1]. Tu peux écrire un commentaire du même type que pour cette dépêche pour chaque lettre, et sur le fond tu auras raison. Pour autant ce sera hors sujet, car écrire dans ce format et être précis est impossible et de toutes façons inutile. On s'adresse à des gens qui ont envie d'un peu de culture générale, pas de 26 cours de niveau licence. Rappelle-toi, la prochaine fois que tu auras l'impression de comprendre comment fonctionne une aurore boréale, la transmission d'une maladie ou la formation d'un volcan : pour que ce contenu arrive jusqu'à toi, il a fallu jeter 99% du contenu des articles scientifiques qui en parlent, ajouter des références peu ou pas scientifiques expliquées en des termes volontairement simples, et ne pas trop écouter les réactions des spécialistes.

              [1] http://interstices.info/display.jsp?id=c_24463
              • [^] # Re: En voilà des approximations...

                Posté par (page perso) . Évalué à 4.

                Il se trouve que je connais bien la vulgarisation scientifique (http://apiacoa.org/publications/vulgarisation.fr.html ) et que je ne vois pas bien en quoi elle imposerait de dire des choses fausses. Dire « La notion scientifique de réseau social est vraisemblablement due à Stanley Milgram » est faux et je ne vois pas en quoi ça peut améliorer la compréhension du sujet. Mais on ne peut pas non plus en chier une pendule, n'est-ce pas :-) ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.