P comme (réseau) petit-monde

Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).

Un réseau est dit petit-monde (small-world network) quand il présente deux caractéristiques :
– la distance  moyenne entre toute paire de sommets est faible ;
– le niveau de clustering local est élevé, c’est-à-dire que les sommets sont généralement très connectés à leurs voisins immédiats.

Par définition, il est nécessaire que le graphe de départ soit connexe : un chemin doit exister entre toutes les paires de sommets.

La méthode de construction choisie par les mathématiciens Watts et Strogatz en 1998 consiste à partir d’un graphe k-régulier (tous les sommets ont  un même degré k) et à modifier de façon aléatoire un lien. La distance moyenne chute rapidement tandis que le niveau de clustering reste longtemps élevé. Les deux figures ci-dessous, extraites de leur article paru dans Nature en 1998, résument les caractéristiques de ces réseaux. Contrairement aux réseaux sans échelle qui ont été construits d’après des observations empiriques, les graphes petits-mondes sont d’abord une construction théorique.

Smallworld network 1

Réseau small-world

Le nom proposé par les auteurs fait explicitement référence à l’expérience de Stanley Milgran en 1961 et aux « six degrés de séparation » (l’idée qu’il est possible de joindre deux personnes quelconque via une chaîne de connaissances réduite). L’un des inconvénients est que les chaînes les plus courtes entre deux sommets, si elles sont faciles à déterminer quand on considère le graphe dans son ensemble, sont généralement inconnues si l’on se place du point de vue des sommets.

Si la méthode de construction est élégante, si la définition est intuitive, l’un des défauts majeurs de cette famille de graphes est qu’elle est susceptible de comprendre la très grande majorité de tous les réseaux empiriques existants. Comme pour les réseaux sans-échelle, l’intérêt réside peut-être moins dans la caractérisation de tel ou tel graphe que dans la création d’un nouveau modèle de graphe.

Billets liés : C comme (réseau) complexe, S comme (réseau) sans échelle.

Retour au glossaire


Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *