Bernhard Rieder : Historiographie du PageRank

Compte-rendu de la séance du 29 novembre 2012, « Le PageRank, la théorie des graphes et la mesure de l’autorité », avec Bernhard Rieder, Assistant Professor à l’Université d’Amsterdam.

Comment comprendre cet internet que nous avons aujourd’hui ? Quels chemins ont été pris et d’autres ignorés ? Cette recherche prend place dans la rédaction d’un livre entrepris depuis 3 ans, et s’appuie plus particulièrement sur un article publié récemment prenant pour objet l’histoire conceptuelle du PageRank de Google.

Deux approches choisies par B. Rieder permettent de comprendre l’état actuel de l’analyse des processus de recherche d’informations sur internet :

– conceptuelle (software studies) ; l’article en question est publié dans un journal dédié au courant (computation of cultures) ;

– travail empirique : production de logiciels et fouille de données (digital methods).

B. Rieder se concentre pour cette séance sur le premier volet : comment construire une approche conceptuelle et historique à l’internet, très ciblée sur le pagerank.

A) Les généalogies existantes de l’ordinateur et de l’internet sont difficilement séparables.

1) Histoire de la computation : elle prend pour objet le calcul, l’origine des mathématiques et leur mécanisation, les mathématiques computationnelles, les premiers ordinateurs, l’introduction au IXe siècle du terme algorithme, la « Pascaline », la première référence au pc… > c’est l’histoire dominante (Campbell-Kelly),

2) Histoire de l’informatique comme technologie industrielle : s’intéresse au traitement d’information, au management, à l’impact de l’ordinateur sur les industries mais aussi l’industrialisation de l’informatique, à la productivité, la réduction de coûts, l’histoire des objets, des entreprises… (Alfred Cortada) ; elle se place dans la lignée de l’histoire industrielle : Schandler).

3) Histoire de l’idéologie (militaire et politique) : histoire des positionnements de l’ordinateur dans des mouvements scientifico-idéologiques : cybernétique, guerre froide (Paul N. Edwards , « A closed world »)

4) Histoire de la machine médium : se penche sur les interfaces, les capacités médiatiques, l’arrivée du multimédia, la créativité (Bush, Engelbart, Alan Kay, Lev Manovich).

5) Histoire canonique de l’internet (réseaux, protocoles, applications) ; déroule un récit à 3 axes centrés sur le rôle de l’Arpa, la contribution de l’académie à l’internet qui se rapproche de l’histoire d’Unix et de l’opensource, et le réseautage alternatif (premiers hackers, usenets, etc.).

Les lignes dominantes dans l’historiographie comprennent la computation mathématique et mécanique, les machines, les logiciels, les infrastructures (produits finis), l’économie et la bureaucratisation, l’idéologie et la politique, associées aux grands hommes. Des postures plus en marges font l’investigation de la culture des créateurs et des usagers.

L’objectif n’est pas de remplacer les généaologies mais de constater qu’il manque quelque chose.

Les software studies se concentrent sur :

  • la notion de computation (qu’est-ce qu’un algorithme ?)
  • le code comme texte (quel type d’écriture)
  • l’appropriation artistique (code poetry)
  • l’interface et sea aspects médiatiques (texte fondateur : Matthew Fuller, « It looks like you are writing a letter »)
  • la rationalité du logiciel
  • les effets sociaux et culturels (domination logicielle) : approche critique.

Il manque des généalogies et des théories des connaissances du logiciel qui ne se limitent pas à la computation (rationalité) et la programmation (connaissance).

« What engineers know and how they know it » de Walter Vincenti : quels sont les types de connaissance de l’ingénieur ? Pour l’ingénieur, il existe un jeu entre ouverture et fermeture ; au-delà ds contraintes, on peut faire autrement.

B) Vers une épistémologie des techniques logicielles

Les techniques logicielles sont des connaissances (descriptives, prescriptives, tacites) qui se déploient à l’intérieur de l’espace ouvert par la computation.

C’est une approche méthodologique inspirée de Foucault puisqu’il s’agit d’aller vers les sources.

Qu’est-ce qui est dans un algorithme ? Pour connaître le cas du moteur de Google, il faut faire la généalogie du Pagerank selon une téléologie renversée : d’où ça vient ?

Qu’est-ce qui est dedans ? On sait ce que c’est mais on ne sait pas de quoi c’est fait, ce qui fait la formule dans un contexte particulier. Comment est-il devenu possible d’écrire cette formule ? Qu’est-ce qui est venu avant ?

Il existe plus d’une centaine d’articles sur Pagerank, mais on ne sait pas ce que ça fait …

Récursion (du statut) : un lien qui vient d’une page d’un statut élevé va apporter plus de statut ; pour éviter les abus (fermes de lien par exemple), on crée une atténuation (dumping).

Démarche des software studies : il s’agit de respecter l’algorithme comme modèle et ne pas le métaphoriser. Pour le connaître on le fait tourner…

Exemple : un réseau aléatoire (taille des nœuds et nombre de liens entrants) : bleu, vert, jaune, rouge (a=0,85)…

Il faut aller lire les sources primaires : essentiellement deux brevets en 2001 et 2004 déposés par Page et Brin, et qui citent beaucoup ; quatre types de sources sont citées : information retrieval, sociométrie, analyse des citations, navigation hypertexte. C’est la sociométrie qui est la plus présente.

1) Moreno (1934) : Who shall survive ?  Inventeur de la sociométrie (sociologie mathématique : the mathematical study of psychological properties of populations).

Invention du test sociométrique (questionnaire).

Théorie de l’attraction/répulsion rendue visible par des questions qui relèvent du psychodrame (on demande aux enquêtés : avec qui voudrais-tu travailler ? ). C’est la première loi de puissance qui est appliquée au domaine du social : sur les questionnaires, si les gens ont plusieurs choix, par exemple 5, il y en a toujours un septième qui n’est choisi par personne (des gens choisis par tout le monde et des gens choisis par personne).

La théorie des graphes doit beaucoup à la sociologie. Mais les méthodes doivent évoluer : par exemple, les diagrammes sont dessinés à la main jusque dans les années 80.

2) Années 40 : génération de sociologues mathématiciens qui vont se greffer sur la sociométrie de Moreno. Forsythe and Katz, 1946 – représentation graphique de l’algèbre matricielle. La matrice est utilisée comme représentation. Algorithme visuel du tableau de croix qui à partir de colonnes et de lignes créent des « cliques ».

Interlude : une définition expérimentale du pouvoir,  question de la propagande, de l’influence, capacité de changer les opinions des gens (1940).

Deux concepts théoriques : perspective socio-psychologique expérimentale (propagande)  de Kurt Lewin (1951) et théorie formelle du pouvoir social de John French (1956) : la conception de l’être humain est appauvrie (A formal theory social of power, Kurt Lewy).

3) Léo Katz : initie l’histoire de la récursion en sociométrie en 1953 car il est mécontent du comptage du vote qui ne permet pas de découvrir les vrais leaders. Il trouve l’algorithme de Moreno insuffisant avec la logique du vote.

Qui vote ? Katz veut prendre en compte le statut des gens qui votent dans son calcul : de qui vient le vote ? La « Katz Centrality » calcule tous les chemins dans un réseau et évalue la longueur : plus le chemin est long moins il apporte.

4) Bonacich (1972) : au lieu de calculer tous les chemins, il va calculer les chemins les plus courts (« Eigen vector ») : les propriétés locales d’un réseau perdent de l’influence sur le calcul du statut et la topologie globale en gagne. Le Page Rank n’est pas une variante de Katz mais de Bonacich : cette métrie est plus résistante.

5) Pinski & Gross (1927) : analyse des citations. Comment une bibliothèque devrait choisir à quelles revues s’abonner ? Ce modèle devient vite un outil de décision (background : décider à quelles revues abonner une bibliothèque ; Gross and Gross 1972).

Garfield (1963, 1972) « impact factor » : « perhaps the most important application of citation analysis is in studies of science policy and research evaluation ».

6) Pinski & Narin (1976) : prennent en compte la taille des revues mais aussi celles qui font des recensions ou états de l’art ? (des articles qui citent beaucoup et sont beaucoup cités). Il se basent sur un modèle économique : le » input-output model » (Leontieff 1941). Ils font du récursif comme Katz.

La valeur d’un article d’une revue est la somme de la valeur des citations entrantes divisés par les citations sortantes : un article distribue son statut sur l’ensemble des articles qu’il va référencer.

Technique de spam : essayer d’avoir un réseau qui accumule du PR et canalise cette valeur d’un lien. Le spam est défini comme menace épistémologique car il détruit l’innocence des liens.

On connaît un interlude avec la crise de la sociométrie qui provoque un changement de théorie dans les années1960 : on assiste à la migration de la métrique vers la « social exchange theory »  (Emerson, Burt, Blau, Granovetter).

On pense à présent que l’on peut analyser des situations sociales avec des analyses économiques selon une nouvelle base théorique (c’est l’économique qui prend le relais).

Une relation est une opportunité, une ressource. Un réseau social est littéralement un capital  (Putnam, 2000). Bonding vs Bridging (Between centrality) : trous structurels.

Pourquoi l’atténuation ?

Justification 1 : problème technique de la boucle infernale.

Justification 2 : modèle du surfeur aléatoire, qui ne passe pas par des liens hypertextes (tape une url, lance un bookmarke, il saute), le facteur d’atténuation exprime une probabilité que le « surfeur saute ».

Justification 3 : le coût de calcul est réduit (le plus d’atténuation = le moins de calcul).

Page et Brin ne font pas référence aux « véritables leaders » de Katz. Google a gardé la rhétorique du vote, mais ne reconnaît pas l’héritage conceptuel en termes de justification. Reste à savoir quelles sont les interprétations que l’on peut trouver ailleurs qui citeraient le Katz de 1953.

7) Monacich introduit en 1987 un facteur d’atténuation plus puissant.

Plus il y a d’atténuation plus le nombre de liens compte, du global vers le local.

Il peut être bénéfique d’être connecté à des gens qui possèdent peu de capital social.

–       avec a qui tend vers 1, le web devient machiavélique (il est important d’être ami avec le fort) et favorise le positionnement stratégique ; la topologie globale domine selon un modèle conservateur, réformiste (il faut affecter le réseau de manière considérable pour obtenir un changement, et cela en plusieurs endroits) ;

–       avec a qui tend vers 0, la topologie locale domine, selon un modèle insurrectionnel, populiste, révolutionnaire (le changement peut commencer avec un petit groupe très motivé, c’est le nombre qui compte).

Depuis 2005, Google ne communique plus sur la valeur qu’il utilise (0.85 pour alpha).

Réinterprétation de Pagerank : le « Status authoring device » (Rogers, 2009) confère de la visibilité à ceux dont le statut est élevé, selon un effet cumulatif / boule de neige. Statut et pouvoir deviennent autorité et pertinence.

Réinterprétation du lien :

–       fin de l’innocence du lien par Pagerank ?

–       méritocratie (inégalité « éclairée » canonique) contre ploutocratie (inégalité du lien basé sur différentes formes de pouvoir).

Existence d’un spamrank ?

Le Pagerank est conçu pour mesure des réputations des personnes.

La question des alternatives à cet algorithme : est-ce que l’on peut formuler une théorie des graphes sur d’autres bases ? par exemple l’ ANT (Actor Network Theory), HITS et Gabriel Tarde ?

HITS (Jon Kleinberg) : 2 métriques pour deux types d’acteurs. Le calcul d’autorité est localisé, à chaque niveau. « Hits metrics » : autorité et hub (calculé sur le document et localisé, et non sur le réseau).

1 pagerank = 1 réseau

Hits cherche d’abord les documents. Le réseau est calculé à partir des textes trouvés. 1 requête = 1 réseau. Alors que dans le PR, un site peut dominer sur un large ensemble de sujets.

Débat :

On précise la différence entre des techniques de graphes destinées à interpréter des situations sociales, à favoriser la compréhension et l’utilisation de ces techniques qui prescrivent des comportements.

Camille Paloque-Berges demande si ce modèle est utilisé pour analyser des données dans un déroulement temporel, comparer des ensembles de données dans le temps. Cela existe, mais l’analyse diachronique reste difficile en termes de théorie des graphes. On reste de plus soumis à des outils imparfaits : par exemple, l’analyse d’un corpus de données sur l’histoire de la blogosphère néerlandaise à l’University d’Amsterdam reste tributaire de la Wayback Machine (archive.org).

La question de la surinterprétation des liens est posée. Claire Scopsi remarque qu’il faut changer les paramètres en fonction du terrain, d’où la difficulté dans l’utilisation de la théorie des graphes pour l’interprétation. Elle souligne que manque souvent une approche critique de cette démarche analytique.