Loading AI tools
De Wikipédia, l'encyclopédie libre
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 :
É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 :
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.
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].
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].
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.