Zufallsgraphen

Die Eigenschaften klassischer Zufallsgraphen können in den beiden folgenden Punkten zusammengefaßt werden:

• Die Gesamtanzahl von Knoten $N$ ist konstant.
• Die Wahrscheinlichkeit, daß zwei beliebige Knoten miteinander verbunden sind, enspricht $p$.

Aus dem Blickwinkel der Statistischen Physik stellen die klassischen ungerichteten Zufallsgraphen ein System im Gleichgewicht dar. In diesen ungerichteten Graphen aus $N$ Knoten gibt es $N(N-1)/2$ mögliche Verbindungen, so daß im Mittel $pN(N-1)/2$ Verbindungen darin existieren. Die Verteilung der Verbindungen auf die Knoten, der Knoten-Degree $k$, entspricht einer Binomialverteilung

$$P(k)=\binom{N-1}{k} p^k(1-p)^{N-1-k}$$ (2.5)

mit einem mittleren Degree $<k>=p(N-1)$. Für große $N$ entspricht die Gleichung (2.5) der Poissonverteilung

$$P(k)=\frac{{<k>}^k}{k!} e^{-<k>}.$$ (2.6)

Diese Verteilung um den Mittelwert des Degree und das starke Abfallen der Verteilungsfunktion zu hohen Degrees ist charakteristisch für Zufallsgraphen.