Modèle de Watts–Strogatz

Le modèle de Watts–Strogatz est un modèle de génération de graphe aléatoire produisant des graphes disposant de la propriété de petit monde. Il a été introduit en 1998 par Duncan Watts et Steven Strogatz^[1].

Graphe à 100 nœuds généré avec le modèle de Watts–Strogatz.

Motivation

L'étude des graphes aléatoires remonte aux travaux de Paul Erdős et d'Alfréd Rényi sur le modèle portant leur nom, qui fournit un modèle simple avec beaucoup d'applications^[2]. Cependant, ce modèle ne vérifie pas deux importantes propriétés typiques des réseaux réels :

• il produit des graphes à faible coefficient de clustering ;
• sa distribution de degré converge vers une loi de Poisson, plutôt que vers une loi de puissance observée dans les réseaux réels sans échelle.

Algorithme

Illustration du processus de reconnexion d'arête.

Graphe obtenu par le modèle de Watts–Strogatz avec ${\displaystyle n=20}$, ${\displaystyle k=4}$, ${\displaystyle p={\text{0,2}}}$, avec la bibliothèque NetworkX.

Étant donnés le nombre de nœuds ${\displaystyle n}$, le degré moyen ${\displaystyle k=2m}$ supposé pair et vérifiant la relation ${\displaystyle n\gg k\gg \ln(n)\gg 1}$, ainsi qu'un paramètre ${\displaystyle p}$, l'algorithme construit un graphe non orienté à ${\displaystyle {\frac {nk}{2}}}$ arêtes de la façon suivante :

1. On part d'un graphe en anneau en treillis (Graphe de Cayley): chacun des ${\displaystyle n}$ nœud est connecté à ${\displaystyle k}$ voisins, ${\displaystyle k/2=m}$ de chaque côté ;
2. Pour chaque nœud et chacune de ses arêtes, on change la destination de cette arête avec probabilité ${\displaystyle p}$, en évitant de dupliquer des arêtes existantes et de relier un nœud à lui-même.

Propriétés

Informellement, la structure initiale en anneau donne un coefficient de clustering local élevé, tandis que les arêtes reconnectées réduisent la longueur moyenne du plus court chemin et confèrent ainsi au graphe la propriété de petit monde.

Petit monde et coefficient de clustering

Dans le cas limite ${\displaystyle p=0}$, la longueur moyenne du plus court chemin est ${\displaystyle \ell (0)\sim {\frac {n}{2k}}\gg 1}$ : le graphe initial ne dispose pas de la propriété de petit monde, à l'inverse de l'autre cas limite ${\displaystyle p=1}$, c'est-à-dire celui du graphe aléatoire, où ${\displaystyle \ell (1)\sim {\frac {\ln(n)}{\ln(k)}}}$^[1].

Dans le cas limite ${\displaystyle p=0}$, le coefficient de clustering est celui du graphe initial en anneau et s'écrit ${\displaystyle C(0)={\frac {3(k-2)}{4(k-1)}}={\frac {3(m-1)}{2(2m-1)}}}$. Il ne dépend donc que de la topologie du réseau et pas de sa taille^[3],[4]. Dans le cas limite ${\displaystyle p=1}$, le coefficient de clustering se comporte comme celui d'un graphe aléatoire : ${\displaystyle C(1)\sim {\frac {k}{n}}}$^[4]. Pour ${\displaystyle 0<p<1}$, le coefficient de clustering dépend peu de ${\displaystyle n}$ et se comporte en ${\displaystyle C(p)\approx C(0)(1-p)^{3}}$^[3].

Watts et Strogatz ont mis en évidence un intervalle pour ${\displaystyle p}$ où ${\displaystyle \ell (p)}$ est proche de ${\displaystyle \ell (1)}$ mais avec ${\displaystyle C(p)\gg C(1)}$. Il en résulte des réseaux hautement agglomérés et disposant de la propriété de petit monde^[1].

Distribution de degré

Pour une probabilité de reconnexion ${\displaystyle 0<p<1}$, on obtient pour ${\displaystyle c\geq m}$ la distribution de degré suivante^[3] :

${\displaystyle P(c)=\sum _{n=0}^{\min(c-m,m)}{{m} \choose {n}}(1-p)^{n}p^{m-n}{\frac {(pm)^{c-m-n}}{(c-m-n)!}}e^{-pm}}$

La forme de la distribution de degré est similaire à celle d'un réseau aléatoire. Elle possède un pic à ${\displaystyle c=2m=k}$ et décroit exponentiellement pour ${\displaystyle c}$ élevé. Le modèle de Watts–Strogatz est donc relativement homogène en degré, les nœuds du réseau ayant un degré proche du degré moyen^[4].

Centralité d'intermédiarité

Malgré l'homogénéité en degré du modèle de Watts–Strogatz, sa distribution en intermédiarité est hétérogène, sans toutefois vérifier une loi de puissance que l'on retrouve par exemple dans le modèle de Barabási-Albert^[5].

Variante

Dans une variante de ce modèle proposée par Newman et Watts, les arêtes aléatoires sont ajoutées au graphe initial plutôt que construites par reconnexion d'arêtes existantes^[6].

Voir aussi

• Théorie des réseaux
• Modèle de Barabási-Albert
• Étude du petit monde
• Réseau « petit monde »