Der Zufallsgraph verständlich erklärt

Wer ein Netz aus Betrieben, Straßen oder Leitstellen betreibt, fragt sich: Hängt ein großer Teil davon zusammen, oder zerfällt es in Inseln? Ein einfaches Würfelmodell, der Zufallsgraph, zeigt: Ab einer bestimmten Zahl von Verbindungen je Betrieb ändert sich plötzlich, ob ein großer Teil des Netzes zusammenhängt. Diese Seite erklärt das zuerst ohne Formeln und danach für Fachleute mit Modell, Formeln und Messwerten.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Netz, in dem jede Verbindung vom Zufall abhängt

Stellen Sie sich einen Betriebsverbund vor: viele Betriebe, und für jedes mögliche Paar wird gewürfelt, ob es zwischen den beiden eine Verbindung gibt, etwa eine Lieferbeziehung. Bei Fachleuten heißen die Betriebe Knoten und die Verbindungen Kanten, das Ergebnis ein Zufallsgraph. Eingestellt wird nur eine Größe: der mittlere Grad, also wie viele Verbindungen ein Betrieb im Durchschnitt hat. Ein mittlerer Grad von zwei heißt: Jeder Betrieb hat im Durchschnitt zwei Geschäftspartner, manche mehr, manche weniger.

Das Modell ist mit Absicht einfach. Für jedes Paar gilt dieselbe Wahrscheinlichkeit, und sie ist so gewählt, dass im Durchschnitt der gewünschte mittlere Grad herauskommt. Es gibt keine Gruppen von Betrieben, die sich bevorzugt untereinander verbinden, und keine Betriebe mit besonders vielen Partnern. Gerade deshalb taugt es als Vergleichsmaßstab: Verhält sich ein echtes Netz anders, liegt das vermutlich nicht am Zufall allein.

Das Überraschende: Ein großes Netz entsteht plötzlich

Ist der mittlere Grad klein, besteht das Netz aus vielen kleinen Inseln: Gruppen von Betrieben, die untereinander verbunden, aber vom Rest abgeschnitten sind. Erhöht man den mittleren Grad langsam, passiert zunächst wenig. Dann, sobald er über eins steigt, kippt das Bild: Es entsteht eine große Gruppe, in der ein großer Teil aller Betriebe zusammenhängt, und die übrigen Inseln bleiben klein. Zusammenhängen heißt: Von jedem Betrieb der Gruppe führt über Zwischenstationen ein Weg zu jedem anderen.

Der Grund: Hat ein Betrieb im Durchschnitt mehr als einen Partner, führt jede Verbindung im Mittel zu mehr als einem weiteren Betrieb, und die Gruppe wächst weiter; sonst versiegt sie meist nach wenigen Schritten. Diese Grenze heißt Schwelle. Nach der Theorie im zweiten Teil dieser Seite liegen bei im Mittel anderthalb Partnern je Betrieb in sehr großen Netzen schon mehr als die Hälfte der Betriebe in der großen Gruppe. In einem Programm zum Ausprobieren, der Demo (Link am Ende dieses Teils), können Sie das Kippen selbst herbeiführen. In einem solchen Modellnetz bleibt ein Gerücht oder ein Ausfall entweder im Kleinen stecken oder erfasst einen großen Teil des Netzes; ob ein echtes Netz sich so verhält, lässt sich nur an diesem Netz selbst prüfen.

Was die Rechnung sagt und was ein kleines Netz zeigt

Die Theorie gilt für sehr große Netze mit sehr vielen Betrieben. Die Demo legt sie neben Netze mit einigen tausend Betrieben, die sie selbst auswürfelt. Weit von der Schwelle stimmen beide gut überein. Dicht an der Schwelle nicht: Ein Netz mit begrenzter Betriebszahl verwischt den Übergang, die große Gruppe ist dort kleiner, als die Rechnung sagt, und bei jedem neuen Auswürfeln etwas anders.

Wer also aus einem einzelnen kleinen Netz auf eine scharfe Schwelle schließt, sieht sie nur ungefähr. Die Demo zeigt deshalb auch Netze verschiedener Größe nebeneinander und ein Netz, das Verbindung für Verbindung wächst.

Zwei Fragen, zwei Grenzen: große Gruppe und ganzes Netz

Eine große Gruppe ist noch kein Netz aus einem Stück. Die Schwelle bei einem Partner im Durchschnitt beantwortet nur, ob es eine große Gruppe gibt. Ob wirklich jeder Betrieb dazugehört, ist eine zweite Frage mit einer höheren Grenze: Der mittlere Grad muss dafür mit der Zahl der Betriebe langsam wachsen. Knapp darunter bleiben einzelne Betriebe übrig, knapp darüber hängt in der Demo meist alles zusammen. Auch diesen Übergang können Sie dort beobachten.

Wie ernst ist das Modell zu nehmen?

Ein Zufallsnetz ist ein Vergleichsmaßstab, kein Abbild eines Straßen- oder Lieferantennetzes: Echte Netze haben Nachbarschaften und besonders gut vernetzte Betriebe, die dieses Modell nicht kennt.

Was Sie mitnehmen: Der mittlere Grad ist ein erster Anhaltspunkt, ob ein Netz zusammenhängt oder in Inseln zerfällt, aber nur, wenn die Verbindungen ungefähr gleichmäßig verteilt sind; ein einzelner Betrieb mit sehr vielen Partnern kann das Bild ändern. Woran Sie es im Betrieb merken: Bleibt ein Ausfall mal im Kleinen und erfasst mal fast alle, ohne dass sich die Verbindungen sichtbar geändert haben, ist das Netz empfindlich: Nahe der Schwelle kann schon eine Verbindung mehr oder weniger das Ergebnis ändern.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Modell: \(n\) Knoten, jede der \(\binom{n}{2}\) möglichen Kanten kommt unabhängig mit Wahrscheinlichkeit \(p = c/(n-1)\) vor; \(c\) ist der erwartete mittlere Grad. Die Demo zieht die Kantenmenge gleichverteilt aus allen Paaren (Zahl binomialverteilt) und zählt die Komponenten mit Union-Find.
• Theorie: Grenzwerte für \(n \to \infty\): die Schwelle der Riesenkomponente bei \(c = 1\), der Anteil \(S\) der Knoten darin, die mittlere Größe \(\chi\) der kleineren Komponenten und der Zusammenhang bei \(c = \ln n + x\).
• Vergleich: Die Messreihen sind Mediane über fünf feste Pläne (Zufalls-Seeds 100000 bis 100004), nie ein einzelner Zufalls-Seed; die Voreinstellungen der Demo sind Einzelläufe.

Die Formeln

Riesenkomponente. Für \(c \le 1\) ist \(S = 0\); für \(c > 1\) ist \(S\) die positive Lösung von

\[S = 1 - e^{-cS}.\]

Kleinere Komponenten. Mit der Lösung \(S\) gilt für die mittlere Größe der Komponente eines Knotens außerhalb der Riesenkomponente

\[\chi = \frac{1}{1 - c\,(1 - S)},\]

unterhalb der Schwelle also \(\chi = 1/(1-c)\); sie divergiert bei \(c \to 1\).

Zusammenhang. Bei mittlerem Grad \(c = \ln n + x\) ist das Netz mit Wahrscheinlichkeit

\[P(\text{zusammenhängend}) \to e^{-e^{-x}}\]

verbunden (Grenzwert für \(n \to \infty\)). Kritischer Punkt. Bei \(c = 1\) ist die größte Komponente von der Größenordnung \(n^{2/3}\), nicht ein fester Anteil von \(n\).

Befunde

Alle Zahlen stammen aus der README der Demo (jede steht in deren Tests, tests/test_claims.py). Messzahlen sind Mediane über fünf feste Pläne; bei den Messreihen steht die Größe \(n\) dabei. Die Zufallszahlen eines numpy-Generators sind nicht über Versionen stabil, die Tests prüfen deshalb Bänder.

Frage	Befund
Welche Werte hat die Theorie?	Riesenkomponente bei c = 1,5: 58,3 %, bei c = 2: 79,7 %, bei c = 3: 94,0 %; mittlere Größe der kleineren Komponenten bei c = 0,5: 2,0.
Trägt die Theorie für n = 2 000?	Median über fünf Pläne: c = 1,4: 49,6 % (Theorie 51,1 %), c = 2: 79,0 % (79,7 %), c = 3: 93,6 % (94,0 %), c = 4: 98,0 %. Ab c = 1,4 weicht die Messung um höchstens 1,9 Prozentpunkte ab.
Wie verhält sie sich an der Schwelle?	Bei c = 1,0 liegt die Messung (n = 2 000, Median der festen Pläne) noch bei 6,9 % statt 0 (über 400 Pläne 6,3 %). Bei c = 1,1 ergeben die fünf festen Pläne 8,9 % statt der 17,6 % der Theorie, aber das ist ein Ergebnis dieser fünf Pläne; über 400 Pläne ist der Median 16,4 %, also nur etwa 1 bis 2 Prozentpunkte unter der Theorie.
Wie scharf ist der Übergang bei kleinem n?	Bei c = 0,8 hat die größte Komponente 4,3 % (n = 300), 1,2 % (n = 3 000) und 0,3 % (n = 30 000) der Knoten; bei c = 1,4 sind es 45,0 %, 50,5 % und 50,9 % gegen 51,1 % in der Theorie (Mediane der fünf festen Pläne; die Zahlen für kleine n sind aus fünf Plänen grob).
Wann ist das Netz zusammenhängend?	Bei c = ln n + x liegt der Anteil verbundener Netze für n = 100, 400 und 1 600 und x = −2 bis +2 in allen 15 Zellen höchstens 8 Prozentpunkte neben exp(−exp(−x)) (Zufallsfehler bis 4 bei 150 Zufalls-Seeds je Zelle); bei x = +1: 70,7 % (n = 1 600) gegen 69,2 %.
Was passiert am kritischen Punkt?	Bei c = 1 hat die größte Komponente im Median 64,5 (n = 500), 122,5 (n = 2 000), 317,5 (n = 8 000) und 721 Knoten (n = 32 000), geteilt durch n^(2/3) etwa 0,7 bis 1,0 (20 Pläne je Größe; die Spanne ist Stichprobenrauschen, mit 100 Plänen zwischen 0,78 und 0,89); ihr Anteil an n fällt von 12,9 % auf 2,3 %.

Grenzen

• Nur das einfachste Modell: Alle Paare sind gleich wahrscheinlich; Hubs, Gemeinschaften und Nachbarschaft kommen nicht vor. Ein Zufallsnetz ist als Modell eines Straßennetzes ungeeignet (Folgestück „Räumliche Netze“).
• Die Theorie gilt für \(n \to \infty\): Die Messungen liegen bei endlicher Größe darunter, vor allem dicht an der Schwelle. Die Messreihe ist mit fünf Plänen je Zelle klein.
• Zusammenhang ist schon bei \(n = 100\) gut getroffen: Eine Verschmierung wie bei der Riesenkomponente ist dort nicht zu erkennen; die Abweichungen liegen im Bereich des doppelten Zufallsfehlers.
• Der kritische Punkt streut stark: Zwischen Minimum und Maximum der größten Komponente liegt bei jeder Größe ein Faktor von 7 bis 9; das Verhältnis zu \(n^{2/3}\) ist deshalb nur eine Größenordnung, kein Gesetz mit scharfen Konstanten.
• Kein Wegelängen-Maß: Die Demo misst Komponentengrößen, nicht die Länge der Wege; das steht in der Linie „Graphen und Netzwerke“.

Quellen

• Erdős, P., Rényi, A. (1960): On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5.
• Bollobás, B. (2001): Random Graphs, 2. Auflage. Cambridge University Press.
• Quelltext, Pläne und Tests der Demo: github.com/sebastian-hanisch/zufallsgraph-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der README der Demo und aus dem Gedächtnis des Autors und sind nicht gegen die Originale geprüft.