Modèle de Watts–Strogatz — Wikipédia

Graphe à 100 nœuds généré avec le 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].

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 :

Illustration du processus de reconnexion d'arête.
Graphe obtenu par le modèle de Watts–Strogatz avec , , , avec la bibliothèque NetworkX.

É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 :

  1. On part d'un graphe en anneau en treillis (Graphe de Cayley): chacun des nœud est connecté à voisins, 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é , en évitant de dupliquer des arêtes existantes et de relier un nœud à lui-même.

Propriétés

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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é

[modifier | modifier le code]

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

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

Notes et références

[modifier | modifier le code]
  1. a b et c (en) Duncan J. Watts et Steven H. Strogatz, « Collective dynamics of ‘small-world’ networks », Nature, vol. 393, no 6684,‎ , p. 440–442 (ISSN 1476-4687, DOI 10.1038/30918, lire en ligne, consulté le )
  2. (en) Paul Erdős et Alfréd Rényi, « On random graphs I », Publicationes Mathematicae, vol. 6,‎ , p. 290-297 (lire en ligne)
  3. a b et c (en) A. Barrat et M. Weigt, « On the properties of small-world network models », The European Physical Journal B - Condensed Matter and Complex Systems, vol. 13, no 3,‎ , p. 547–560 (ISSN 1434-6036, DOI 10.1007/s100510050067, lire en ligne, consulté le )
  4. a b et c (en) Réka Albert et Albert-László Barabási, « Statistical mechanics of complex networks », Reviews of Modern Physics, vol. 74, no 1,‎ , p. 47–97 (DOI 10.1103/RevModPhys.74.47, lire en ligne, consulté le )
  5. (en) Yongxiang Xia, Jin Fan et David Hill, « Cascading failure in Watts–Strogatz small-world networks », Physica A: Statistical Mechanics and its Applications, vol. 389, no 6,‎ , p. 1281–1285 (ISSN 0378-4371, DOI 10.1016/j.physa.2009.11.037, lire en ligne, consulté le )
  6. (en) M. E. J. Newman et D. J. Watts, « Renormalization group analysis of the small-world network model », Physics Letters A, vol. 263, no 4,‎ , p. 341–346 (ISSN 0375-9601, DOI 10.1016/S0375-9601(99)00757-4, lire en ligne, consulté le )