Small-World-Netzwerke

Watts und Strogatz [10] entdeckten in einer ganzen Reihe von realen Netzwerken eine besondere Eigenschaft. Obwohl die mittlere kürzeste Weglänge zwischen den Knoten klein und, wie bei Zufallsgraphen, in der Größenordnung des Logarithmus der Netzwerkgröße lag, besaßen diese Netzwerke einen deutlich größeren Clustering-Koeffizienten. Aufgrund dieser Beobachtung führten sie den Begriff der ``Small-World-Netzwerke'' ein, als Netzwerke mit kleiner kürzesten mittleren Weglänge und großem Clustering-Koeffizienten. Nach dieser Definition sind Zufallsgraphen keine ``Small-World-Netzwerke'', obwohl sie den ``Small-World-Effekt'' zeigen.

Nach folgendem einfachen Algorithmus werden Small-World-Netzwerke gemäß dem ``WS Modell'' erzeugt:

• Start: Begonnen wird mit einem ringförmigen Gitter aus $N$ Knoten. Jeder Knoten ist mit jedem seiner $K \geq 4$ nächsten Nachbarn verbunden ($K/2$ auf jeder Seite).
• Entwicklung: Jede Verbindung des Gitters wird mit der Wahrscheinlichkeit $p$ gelöscht und durch eine neue Verbindung zwischen zufällig ausgewählten Knoten ersetzt. Dabei sind Verbindungen von einem Knoten zu sich selbst und doppelte Verbindungen verboten.

Abbildung: Die Entwicklung nach dem WS-Modell. Das Modell interpoliert zwischen regulären Ringgittern und Zufallsgraphen bei konstanter Anzahl Knoten und Verbindungen. Ausgangspunkt sind $N=20$ Knoten, jeweils verbunden mit den 4 nächsten Nachbarn. Mit zunehmenden $p$ nähert sich das Netzwerk den Zufallsgraphen ($p=1$). Aus Watts und Strogatz [10].

Dieses Verfahren erzeugt etwa $pNK/2$ Verbindungen zwischen Knoten, welche vorher weit voneinander entfernt waren. Der einzige Parameter $p$ dieses Modells steuert den Übergang vom einem geordneten Zustand zu einer völlig zufälligen Konfiguration (Abb. 2.2). Für $p=0$ ist die Wahrscheinlichkeitsverteilung der Degrees $P(k) = \delta(k-<k>)$, wobei $<k>$ die mittlere Linkanzahl je Knoten ist. Für endliche $p$ wird die Verteilung breiter, bleibt aber um $<k>$ lokalisiert [24].