Skalenfreie Netzwerke

Bei den empirischen Untersuchungen realer Netzwerke entdeckte man eine Vielzahl Systeme, deren Degree-Verteilungen einem Potenz-Gesetz gehorchen (vgl. Tab 1.1). Da für Potenzgesetze keine charakteristische Skalierung definert werden kann, werden diese Netzwerke skalenfrei genannt [5].

Die früheren Modelle konnten diese Verteilungform nicht erklären. Das Modell für Zufallsgraphen von Erdös und Renyi [9,23] beginnt mit einer festen Anzahl Knoten $N$ und verbindet jedes Paar von Knoten mit der Wahrscheinlichkeit $p$ miteinander. Das führt zu einer Poisson-Verteilung der Degrees. Auch das ``Small World'' Modell von Watts und Strogatz [10] beginnt mit einer festen Anzahl Knoten $N$ auf einem eindimensionalen Gitter. Jeder Knoten ist mit seinen nächsten und übernächsten Nachbarn verbunden. Dann wird jeder Link mit der Wahrscheinlichkeit $p$ an neue, zufällig ausgewählte Knoten umgelegt. Das Modell führt, in Abhängigkeit von dem Parameter $p$, zu Netzwerken mit Verteilungformen von einem Peak bei $<k>$ bis zu Poisson.

Benötigt werden neue Modelle für die Entstehung skalenfreier Netze.

Die grundlegenden Erkenntnisse, wie ein Netzwerk mit einer derartigen Verteilung entsteht, wurden zuerst von A.-L. Barabási und R. Albert [5] formuliert. S.N. Dorogovtsev et al. [7] zeigten, daß das Modell um eine anfängliche Attraktivität der Knoten erweitert werden muß. Krapivsky et al. [8] entwickelten aus diesen Erkenntnissen ihr Model und bestimmten weitgehend analytisch die gemeinsame Verteilung der Indegrees und Outdegrees eines Knotens. Im Folgenden werden die einzelnen Modelle genauer erläutert.