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].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Watts-Strogatz_small-world_model_100nodes.png/220px-Watts-Strogatz_small-world_model_100nodes.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Watts-Strogatz-rewire.png/220px-Watts-Strogatz-rewire.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Watts_strogatz.svg/220px-Watts_strogatz.svg.png)
Étant donnés le nombre de nœuds , le degré moyen
supposé pair et vérifiant la relation
, ainsi qu'un paramètre
, l'algorithme construit un graphe non orienté à
arêtes de la façon suivante :
- On part d'un graphe en anneau en treillis (Graphe de Cayley): chacun des
nœud est connecté à
voisins,
de chaque côté ;
- Pour chaque nœud et chacune de ses arêtes, on change la destination de cette arête avec probabilité
, 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 , la longueur moyenne du plus court chemin est
: le graphe initial ne dispose pas de la propriété de petit monde, à l'inverse de l'autre cas limite
, c'est-à-dire celui du graphe aléatoire, où
[1].
Dans le cas limite , le coefficient de clustering est celui du graphe initial en anneau et s'écrit
. Il ne dépend donc que de la topologie du réseau et pas de sa taille[3],[4]. Dans le cas limite
, le coefficient de clustering se comporte comme celui d'un graphe aléatoire :
[4]. Pour
, le coefficient de clustering dépend peu de
et se comporte en
[3].
Watts et Strogatz ont mis en évidence un intervalle pour où
est proche de
mais avec
. 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 , on obtient pour
la distribution de degré suivante[3] :
La forme de la distribution de degré est similaire à celle d'un réseau aléatoire. Elle possède un pic à et décroit exponentiellement pour
é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].