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.

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. 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 

É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ù .

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. Dans le cas limite , le coefficient de clustering se comporte comme celui d'un graphe aléatoire : . Pour , le coefficient de clustering dépend peu de  et se comporte en .

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.

Distribution de degré 
Pour une probabilité de reconnexion , on obtient pour  la distribution de degré suivante :

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.

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.

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.

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

Notes et références 

Algorithme de la théorie des graphes
Analyse des réseaux sociaux
Graphe aléatoire