Skalenfreie Small-World-Netzwerke

Die Anwendung des Modells von Watts und Strogatz auf reale Netzwerke ist schwierig, da das Modell von regulären Graphen ausgeht. Viele reale Systeme beginnen ihre Entwicklung jedoch als Zufallsgraphen. Dies wirft die Frage auf, welche dynamischen Eigenschaften eines Netzwerks zu Small-World-Netzwerken führen. Eine mögliche Antwort auf diese Frage wurde von Ebel, Davidsen und Bornholdt [25] gegeben. Ausgehend von ungerichteten Zufallsgraphen mit einer konstanten Anzahl Knoten, entwickelt sich das Netzwerk nach folgenden Regeln:

• Transitives Verbinden: Für einen zufällig ausgewählten Knoten werden zwei seiner Nachbarn zufällig ausgewählt. Diese Nachbarn werden miteinander verbunden, sofern noch keine Verbindung existiert. Besitzt der ausgewählte Knoten weniger als zwei Nachbarn, dann wird der Knoten mit einem zufälligen Knoten des Netzwerks verbunden.
• Endliches Alter: Mit einer Wahrscheinlichkeit $p$ wird ein zufällig ausgewählter Knoten inklusive aller seiner Verbindungen aus dem Netzwerk entfernt und durch einen neuen Knoten ersetzt. Der neue Knoten wird mit einem zufällig ausgewählten Knoten des Netzwerks verbunden.

Für die Entwicklung des Netzwerks werden die beiden Schritte iteriert. In Begriffen eines Bekanntschaftsnetzwerks stellen die Knoten Personen dar und die Verbindungen Bekanntschaften von Personen. Die erste Regel stellt dann die Situation dar, daß zwei Personen A und C als Bekannte einer Person B eine höhere Chance haben, sich kennenzulernen. Die zweite Regel symbolisiert dann das Ausscheiden bzw. das Neuerscheinen von Personen in dem Netzwerk. Die Betrachtungen des Modells beziehen sich nur auf Werte für $p \ll 1$, wobei $p$ den einzigen Parameter des Modells darstellt.

Es wurde gezeigt, daß sich das System in einen stationären Zustand mit hohem Clustering-Koeffizienten und kurzer mittlerer Weglänge entwickelt. Es stellt somit ein Small-World-Netzwerk dar. In Abhängigkeit von dem Paramter $p$ kann das Modell exponentielle Degree-Verteilungen und Potenzgesetz-Verteilungen reproduzieren.