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.
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.
OpenEdition vous propose de citer ce billet de la manière suivante :
Laurent Beauguitte (1 juillet 2013). P comme (réseau) petit-monde. groupe fmr (flux, matrices, réseaux). Consulté le 19 septembre 2024 à l’adresse https://doi.org/10.58079/p82r
2 réponses
[…] liés : M comme modèle, P comme (réseau) petit-monde, S comme (réseau) sans […]
[…] liés : E comme ERGM, P comme (réseau) petit-monde, S comme (réseau) sans […]