ENSAI Cours 4 – L’analyse des réseaux complexes

Avertissement devenant rituel : je ne sais pas (pas encore) rédiger correctement mes cours. Il s’agit donc plus ici de notes de cours grossièrement mises en forme que d’un cours en ligne à proprement parler. Ces notes seront utilement complétées par le visionnage de la présentation téléchargeable ici.

Introduction

Au milieu des années 90, l’étude des réseaux dans les différentes disciplines (sociologie, géographie, écologie etc.) a atteint un stade de “science normale” au sens kuhnien du terme : on sait quels réseaux étudier, comment recueillir les méthodes, comment les traiter et comment interpréter les résultats. Des raffinements sont proposés (multiniveau, modèles statistiques) mais chacun travaille dans son pré carré. L’arrivée brutale et inattendue des mathématiciens et surtout des physiciens à la fin des années 90 bouleverse le paysage scientifique relatif à l’analyse de réseaux.

1. Trois grandes familles de réseaux

Jusque 1998, l’étude des réseaux repose (implicitement ou explicitement) sur le modèle des graphes aléatoires défini dans les années 50 par Erdös et Renyi. Deux nouveaux modèles sont proposés à la fin des années 90 et prétendent révolutionner l’étude des réseaux, voire fonder une science des réseaux.

1.1 Le graphe aléatoire (random graph)

Modèle mathématique de réseau proposé par Erdös et Rényi. Un mot sur Erdös : auteur de plus de 1500 articles, n’a jamais eu un poste fixe dans une institution, passe son temps à aller chez des collègues pour résoudre des problèmes avec eux. Il existe un jeu populaire chez les mathématiciens : le nombre d’Erdös (voir le site http://www.oakland.edu/enp). Le principe est simple : Erdös a 0, ses co-auteurs (plus de 500) ont 1, si l’on a écrit non avec Erdös lui-même mais avec un de ses co-auteurs, on a un nombre de 2 etc. La version grand public existe pour le cinéma : l’Oracle de Kevin Bacon (si un acteur ou une actrice a tourné dans un film avec Bacon, nombre de 1 etc.). Il s’agit d’un jeu développé par des étudiant-e-s américain-e-s dans les années 90 prétendant que Kevin Bacon était l’acteur le plus central du cinéma – ce qui est évidemment faux (https://oracleofbacon.org/) – mais leur a permis de passer dans une émission de télévision populaire à l’époque.

Erdös écrit huit articles avec Rényi entre 1959 et 1968 sur les réseaux (mais il a publié avant sur le sujet). Ils proposent un modèle mathématique de formation de graphe : fixer un nombre de sommets, une probabilité de relations entre ces sommets et générer des liens (non orientés) de manière aléatoire entre sommets (ni boucle ni liens multiples). Deux propriétés des graphes aléatoires peuvent être soulignées : si le graphe est grand, et malgré le (grâce au) placement aléatoire des liens, tous les sommets auront à peu près le même degré, ce dernier suivant une distribution de Poisson (et donc existence d’un pic permettant de résumer les propriétés du graphe) ; il y a émergence d’une composante connexe géante quand le degré moyen atteint 1. Ce modèle de réseau aléatoire ne prétend pas refléter une quelconque réalité sociale – les deux modèles suivants ont une toute autre prétention…

1.2 Le graphe petit-monde (small-world network)

Des recherches scientifiques devenues un mythe populaire : Milgram et les six degrés de séparation.

Milgram, sociologue américain, très connu pour ses travaux sur l’obéissance à l’autorité (From Obedience to Authority, Harper and Row, 1969 – cf I comme Icare) lance une expérience dans les années 60 : des personnes dans des trous perdus (Wichita, Kansas et Omaha, Nebraska) doivent envoyer un courrier à un agent de change à Boston. La consigne principale est d’envoyer le courrier à quelqu’un qu’ils connaissent (If you know the target person on a personal basis, mail this folder directly to him (her). Do this only if you have previously met the target person and know each other on a first name basis), l’objectif de la recherche étant de mesurer la longueur de la chaîne relationnelle créée. L’étude conclue par une longueur moyenne de 5. Ce résultat devient un mythe populaire : l’idée qu’il existe entre deux individus quelconques six degrés de séparation (six liens personnels). Or, des travaux récents (Kleinfeld, 2002) ont montré que les résultats de Milgram étaient peu solides : à l’origine, 300 personnes devaient expédier le courrier depuis le Nebraska. En fait, 100 vivaient à Boston, 200 dans le Nebraska dont la moitié appartenait au même milieu professionnel que la cible… Sur 96 personnes obéissant aux critères voulus, seules 18 lettres ont atteint leur cible…

En 1998, Watts et Strogatz, deux mathématiciens (un doctorant et son directeur de thèse), choisissent de renverser la perspective : non pas se demander si tel ou tel réseau est petit-monde mais prendre un réseau et le transformer pour qu’il devienne petit-monde. Watts avoue n’avoir à peu près rien lu sur le sujet pour ne pas se laisser décourager (la descendance de l’article de Milgram est très fournie). Le modèle est simple : partir d’un graphe k-régulier (tous les sommets ont le même degré), supprimer un lien et le remplacer par un lien aléatoire. Ils découvrent que la transitivité (qu’ils nomment clustering coefficient en raison de leurs lacunes bibliographiques) reste longtemps élevée mais la longueur moyenne des plus courts chemins chute très rapidement. Une deuxième version du modèle met en évidence le fait suivant : quelle que soit la taille du réseau, les 5 premiers liens aléatoires générés réduisent la longueur moyenne des chemins par deux.

L’article a un très fort impact et entraîne une multiplication frénétique des mesures : à peu près tous les réseaux (exceptés certains réseaux techniques en raison des contraintes de localisation) sont small-world… L’intérêt social est peu évident de l’aveu même de Watts (2003). Comme il l’écrit, “the real issue is that there is a big difference between two people being connected by a short path and their being able to find it.[p. 136] […] But even if it is true that everyone can be connected to everyone else in only six degrees of separation, so what? How far is six degrees anyway? From the point of view of getting a job, locating information, or getting yourself invited to a party, anyone more distant than a friend of a friend is for all intents and purposes, a stranger. So […] anything more than two degrees might as well be a thousand.” [p. 299-300]

1.3 Le graphe sans échelle (scale-free network)

Albert et Barabási (doctorante et directeur de thèse) s’intéressent à la distribution des degrés au sein des réseaux (notamment ceux étudiés par Watts et Strogatz) et découvrent qu’elle obéit à une loi de puissance, ce qui n’est prévu ni dans le cas du graphe aléatoire ni dans le cas du graphe petit-monde. Ils proposent alors un modèle dynamique de réseau (un sommet est ajouté à chaque temps t) fondé sur le mécanisme de l’attachement préférentiel : plus un sommet a un degré élevé, plus un nouveau sommet aura tendance à se connecter avec celui-ci. La distribution des degrés est donnée sous forme de probabilités : la probabilité qu’un sommet choisi aléatoirement ait un degré k suit une loi telle que P(k) = k^-γ. Ils proposent un article à Science en 1999 avec ces 2 principes, l’article est rejeté, l’auteur insiste auprès de la revue et l’article est finalement publié. Cet article a un impact étonnant, en physique et dans bien d’autres disciplines.

Pourquoi nommer ces réseaux sans échelle ? Dans un graphe aléatoire, la grande majorité des sommets a un même degré et les sommets s’écartant de cette moyenne sont rares. À l’inverse, la distribution en loi de puissance des degrés dans un réseau sans-échelle ne permet pas de donner une valeur résumant cette distribution. Une des limites du modèle proposé, limite qui sera résolue dans des articles ultérieurs, concerne la prime donnée au premier arrivant : plus un sommet est ancien, plus il doit être central or, qu’il s’agisse des portails de recherche sur internet (Google) ou des citations scientifiques, cette règle est régulièrement violée.

Cet article a eu un impact énorme alors qu’il mettait en évidence une découverte très relative. Les lois de puissance étaient connues (en sciences sociales et dures) depuis des décennies, tout comme le mécanisme de l’attachement préférentiel. Pareto au 19^e siècle met en évidence la très forte inégalité de distribution de richesse (une poignée de très riches, une large majorité de pauvres) ; Merton au 20^e met en évidence l’effet de Matthieu (Matthew effect – d’après la parabole biblique) : plus un acteur est fortement connecté, plus il a de chances d’attirer de nouveaux liens : la loi de puissance était également présente dans les modèles de Zipf (1949) ou d’Herbert Simon (1955). Cette découverte relative n’empêchera nullement Barabási et ses émules de prétendre trouver la solution à presque tous les problèmes économiques et sociaux imaginables (cf son ouvrage Linked).

2. Questions de recherche, données, méthodes

Les questions de recherche sur les réseaux dits complexes sont à peu près les mêmes qu’en SNA ou qu’en géographie : comment se forme le réseau ? quelles sont ses propriétés ? quels sont les acteurs ou les liens les plus centraux ? quelle est leur vulnérabilité ? etc. La nouveauté vient du type de réseaux étudiés (n’importe lequel pourvu qu’il soit grand…) ainsi que des méthodes (où la nouveauté est parfois relative). En ce qui concerne les données, the bigger the better et le sens thématique apparaît souvent très secondaire : tout ou presque peut être étudié à l’aide des méthodes proposées. Le recueil automatisé d’informations en ligne explique l’intérêt pour les réseaux sociaux de l’internet (facebook, twitter) et les base de données (bibliométrie). Si les formalisations mathématiques sont parfois innovantes, leur apport thématique est souvent limité, ce qui est d’ailleurs normal : comme le souligne Watts (2003, p. 6), “The essential problem is that the physicists developed their tools to adress physics questions; not social or economic ones […] The result is that the method looks very impressive and produces lots of elegant results, but it doesn’t solve the actual problem because it’s not about the actual problem” (en italique dans le texte).

De très nombreuses méthodes et mesures ont été proposées, certaines étant des adaptations de mesures existantes, voire des mesures déjà existantes renommées (cf le cas du clustering coefficient supra). La notion de graphe assortatif et disassortatif est intéressante : un graphe est dit assortatif lorsque les sommets de degrés comparables tendent à se connecter entre eux (les gros avec les gros, les petits avec les petits).

La taille des réseaux étudiés oblige à innover : les algorithmes de détection des cliques sont par exemple inadaptés aux grands réseaux ; les modèles statistiques type ERGM (cf cours 5) ont eux aussi inapplicables donc une autre famille de modèles – dont les principes sont proches – est proposée. Une des méthodes de partitionnement de graphe ayant eu le plus de succès est celle proposée par Newman et Girvan : a) calculer l’intermédiarité des liens du graphe, b) supprimer celui qui a la plus forte (en cas de betweenness égale, en tirer un au sort), c) recalculer l’intermédiarité des liens restants et b) à nouveau. La pertinence du découpage obtenu est vérifiée via le calcul de la modularité (modularity). Les partitions créées ne correspondent pas nécessairement dans ce dernier cas à des groupes fortement connexes (tout sommet est obligatoirement affecté à un cluster).

3. Apports et limites des complex networks studies

Les physiciens ont donné un coup de fouet salutaire à l’analyse de réseaux en général. Il y a eu un essor énorme (sans doute plus quantitatif que qualitatif) des études sur les réseaux. Deux phases peuvent être distinguées : celle du prédateur dominant ; celle du prédateur collaboratif. La première phase était (est parfois encore) marquée par une ouverture disciplinaire nulle, la redécouverte de mesures anciennes sans citation des premiers auteurs, la prétention à aborder et à résoudre tous les problèmes (économiques, sociaux, technologiques etc.). La deuxième phase (inégalement atteinte) montre besoin de collaborer avec les autres disciplines, et notamment les SHS, pour donner un sens aux résultats obtenus.

Ces deux modèles ont fortement percolé dans les autres disciplines et des phénomènes d’imitation/importation plus ou moins maîtrisés sont apparus. Comment l’expliquer ? Il y a sans doute un aspect lié à l’habitus disciplinaire des physiciens : force de frappe, accès aux revues prestigieuses (Nature, Science), budgets différents (i.e. très largement supérieurs), habitudes de publication (accès ouvert via arXiv, articles courts, illustrés, paraissant à un rythme soutenu), partage des données, sens de la communication (moins de 3 ans pour Watts et Barabási pour écrire des ouvrages de vulgarisation) et choix peu risqué des sujets de recherche (pour citer Watts une dernière fois : “Physicists, it turns out, are almost perfectly suited to invading other people’s disciplines, being not only extremely clever but also generally much less fussy than most about the problems they choose to study”). Les études small-world/scale-free ont donné lieu à un véritable effet de mode scientifique – qui dure encore aujourd’hui. Les physiciens ont également proposé des outils adaptés à l’étude des grands réseaux (ex. réseaux de villes, de multinationales) susceptibles d’intéresser d’autres disciplines (géographie, science régionale).

En ce qui concerne les apports, la proposition de modèles alternatifs au graphe aléatoire (statistiquement intéressant mais d’une pertinence sociale très limitée) est très utile : même s’il s’agit d’un recyclage pour le réseau scale-free, et même s’il est rare de trouver des réseaux qui ne soient pas small-world. L’autre apport majeur consiste dans les méthodes pour analyser et surtout pour représenter les propriétés des grands réseaux. Utiliser par exemple la distribution des degrés pour résumer une propriété d’un réseau au lieu du traditionnel graphe était une idée brillante.

Deux articles

Duncan J. Watts et Steven H. Strogatz. “Collective dynamics of ‘small-world’networks” Nature 393.6684 (1998): 440-442 (plus 24 500 citations selon Google scholar, consulté le 8 janvier 2015)

R. Guimera, S. Mossa, A. Turtschi et L.N. Amaral. The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles. Proceedings of the National Academy of Sciences, 2005, 102(22), p. 7794-7799.

• Quelles sont les questions de recherche ?
• Quelles sont les données utilisées ?
• Quelles sont les méthodes utilisées et quels sont les principaux résultats ?
• Quel type d’illustration est utilisé ?

Références

Albert-László Barabási, 2003, Linked. How Everything is Connected to Everything Else and What It Means for Business, Science, and Everyday Life, Plume book, New York
Judith S. Kleinfeld, 2002, The small world problem, Society, 39(2):61-66 et 2002; Could it be a big world after all? The six degrees of separation myth, Society, 12.
Mark Newman, 2010, Network: An Introduction, Oxford University Press
Duncan J. Watts, 2003, Six degrees. The science of a Connected Age, William Heinemann, London

---

---