Ein Zufallsgraph ist ein Graph, dessen Kanten nicht nach einem festen Plan, sondern durch einen Zufallsprozess entstehen. Zufallsgraphen sind das wichtigste Werkzeug, um zu verstehen, welche Eigenschaften realer Netzwerke zwangsläufig auftreten — einfach weil es viele Knoten und Kanten gibt — und welche wirklich von der konkreten Struktur abhängen.
Das Erdős–Rényi-Modell
Das klassische Modell geht auf die ungarischen Mathematiker Paul Erdős und Alfréd Rényi zurück (1959). Es gibt zwei gleichwertige Varianten:
- G(n, p): Der Graph hat n Knoten. Jede der möglichen Kanten ist unabhängig von den anderen mit Wahrscheinlichkeit p vorhanden. Im Mittel entstehen also p · (n über 2) Kanten.
- G(n, m): Der Graph hat n Knoten und genau m zufällig gewählte Kanten. Für große n verhalten sich beide Modelle gleich, wenn m ≈ p · (n über 2) ist.
Für jede Kante entscheidet praktisch ein Münzwurf: Liefert die Münze „Kopf“, gibt es die Kante, sonst nicht. Der Graph ist damit das Ergebnis vieler unabhängiger Zufallsentscheidungen.
Das Schwellenphänomen
Der überraschendste Befund: Viele Eigenschaften treten in Zufallsgraphen schlagartig auf, sobald p eine bestimmte Schwelle überschreitet. Wächst p nur geringfügig, springt der Graph von „fast sicher nicht“ auf „fast sicher ja“:
- Bei p = 1/n zerfällt der Graph in viele kleine Zusammenhangskomponenten aus je etwa O(log n) Knoten.
- Bei p = c/n mit c < 1 bleiben alle Komponenten klein. Bei c = 1 passiert der Phasenübergang: Ab c > 1 entsteht eine Riesenkomponente, die einen festen Anteil aller Knoten enthält.
- Bei p = (ln n)/n wird der Graph mit hoher Wahrscheinlichkeit zusammenhängend.
- Etwas darüber liegt die Schwelle für einen Hamiltonkreis und einen Hamiltonpfad.
Solche Schwellenwerte machen Zufallsgraphen zu einem idealen Prüfstand: Ein Algorithmus, der auf zufälligen Eingaben scheitert, scheitert mit hoher Wahrscheinlichkeit an einer strukturellen Eigenschaft — nicht an einem Einzelfall.
Gradverteilung
Die Zahl der Nachbarn eines Knotens (sein Grad) ist binomialverteilt: Jeder der n − 1 anderen Knoten ist mit Wahrscheinlichkeit p verbunden. Ist n · p klein, nähert sich diese Verteilung einer Poisson-Verteilung an. Die meisten Knoten haben dann ähnliche Grade — ein Zufallsgraph ist „homogen“.
Genau daran erkennt man seine Grenze: Viele reale Netzwerke wie das World Wide Web oder soziale Netze sind stark inhomogen („Scale-free“: wenige Knoten mit riesigem Grad, viele mit kleinem). Sie werden besser durch Wachstumsmodelle wie Barabási–Albert (preferential attachment) oder das Small-World-Modell von Watts–Strogatz beschrieben.
Anwendungen
- Netzwerkanalyse: Als Nullmodell, gegen das man echte Netze testet — ist ein beobachtetes Muster Zufall oder Struktur?
- Algorithmen-Tests: Zufällig erzeugte Cliquen, Matchings und Pfade liefern harte Testinstanzen für neue Verfahren.
- Epidemiemodelle: Ansteckung über zufällige Kontaktgraphen modelliert die Ausbreitung in Populationen.
- Theorie: NP-vollständige Probleme werden auf Zufallsgraphen besonders gut verstanden, weil sich die schwierige Eingaberegion statistisch vermessen lässt.
Verwandte Grundlagen: Ungerichteter Graph, Knoten, Kante.