5.8 Grenzwertsätze in zufälligen Graphen

Inhalt:

 
Zufällige kombinatorische Graphen, in denen mögliche Kanten zwischen Knoten mit gewissen Wahrscheinlichkeiten auftreten, dienen dazu, komplexe Netzwerke zu modellieren und haben eine Vielzahl von Anwendungen, wie z. B. in der Informatik (Computernetzwerke). Das wohl einfachste Modell eines zufälligen Graphen wurde von Erds und Rényi um 1960 eingeführt. In diesem tritt jede mögliche Kante unabhängig von allen anderen mit fester Wahrscheinlichkeit p auf.

1999 konnte mit Hilfe von umfangreichen Statistiken gezeigt werden, dass das Modell von Erds und Rényi für die Beschreibung typischer realer Netzwerke ungeeignet ist, da es in der Verteilung der Grade der einzelnen Knoten ein fundamental anderes Verhalten zeigt. Seitdem wurde eine Vielzahl von zufälligen Graphmodellen entworfen, mit dem Ziel, typische Eigenschaften realer Netzwerke, wie z. B. power-law-Verteilung der Grade, hohe Clusterkoeffizienten oder small-world-Effekte wiederzugeben.