Das Modell von Barabási und Albert

Die Modelle von Erdös und Renyi [9] sowie von Watts und Strogatz [10] vernachlässigen zwei generische Eigenschaften von vielen realen Netzwerken. Erstens gehen beide von einer konstanten Knotenanzahl $N$ aus, obwohl die meisten Netzwerke durch kontinuierliches Hinzufügen neuer Knoten wachsen. Beispielsweise werden im Netzwerk der wissenschaftlichen Zitierungen ständig neue Publikationen mit neuen Referenzen hinzugefügt und das WWW wächst gegenwärtig durch das Hinzufügen von Seiten exponentiell mit der Zeit [26]. Zweitens nehmen die Modelle die Wahrscheinlichkeit, daß zwei Knoten miteinander verbunden sind, als zufällig und gleich wahrscheinlich an. Die Dynamik der meisten realen Netze zeigen jedoch einen Effekt, den man heute als ``Preferential Linking'' bezeichnet. So neigen zum Beispiel Autoren von wissenschaftlichen Publikationen dazu, eher bereits populäre Arbeiten zu zitieren, welche bereits einen hohen Degree besitzen. Ebenso tendieren Autoren von Seiten im WWW dazu, Links auf Seiten von breitem Interesse zu legen, wie Suchmaschinen, Zeitungen, Onlineportale, Onlineauktionshäuser, etc. Diese Beispiele legen die Vermutung nahe, daß Verbindungen nicht zufällig geknüpft werden, sondern Knoten mit einem bereits höheren Degree auch eine höhere Wahrscheinlichkeit haben, weitere Verbindungen von neuen Knoten zu bekommen.

Bei dem Modell von Barabási und Albert [5,27] (BA-Modell) wurde nicht versucht die Topologie eines Netzes direkt nachzubilden, sondern Regeln für das Wachstum formuliert: Zu einem Zeitpunkt $t=0$ wird mit einer kleinen Anzahl von Knoten $m_0$ begonnen. In jedem weiterem Zeitschritt $t$ wird ein neuer Knoten hinzugefügt und mit $m \leq m_0$ bereits bestehenden Knoten verbunden. Die Auswahl der Knoten findet dabei nicht zufällig statt, sondern in Abhängigkeit von dessen jeweiligem Degree $k$. Die Wahrscheinlichkeit $\Pi$, einen Link an einen Knoten $j$ zu binden, hängt linear von $k_j$ ab

$$\Pi(k_j) = \frac{k_j}{\sum_n{k_n}},$$ (2.7)

wobei $n$ über das gesamte Netzwerk summiert, den neuen Knoten ausgenommen. Aufgrund der Abhängigkeit zwischen der Wahrscheinlichkeit einen Link zu bekommen und der Anzahl Links, die ein Knoten schon hat, spricht man von ``Preferential Attachment''. Ein Knoten mit vielen Links hat eine größere Chance, weitere Links zu bekommen.

Die Wachstumsdynamik kann folgendermaßen zusammengefaßt werden:

• Start mit einer kleinen Anzahl Knoten $m_0$.

• Wachstum: In jedem Zeitschritt $t$ wird ein Knoten mit $m \leq m_0$ Verbindungen hinzugefügt, die den neuen Knoten mit $m$ anderen Knoten verbinden.

• Preferential Attachment: Die Wahrscheinlichkeit $\Pi$, daß ein bestimmter Knoten $j$ als Ziel ausgewählt wird, hängt von der Anzahl Links $k_j$ die er bereits auf sich vereinigt ab, via $\Pi(k_j) = \frac{k_j}{\sum_n{k_n}}$.

Dieser Algorithmus erzeugt nach $t$ Zeitschritten ein Netzwerk mit $N=t+m_0$ Knoten und $mt$ Verbindungen. Das Netzwerk entwickelt sich mit $t$ in einen stationären Zustand mit konstanter Degree-Verteilung nach einem Potenzgesetz

$$P(k) \sim k^{-\nu}$$ (2.8)

mit $\nu=3$ für großes $t$,$k$ [27].

Durch Untersuchung weiterer Modelle zeigten Barabási und Albert, daß die beiden Eigenschaften Wachstum und Preferential Attachment nötig sind, um diese skalenfreie Verteilungsform zu erklären. Ohne Preferential Attachment $\Pi(k)=konst.=1/(m_0+t-1)$ entspricht dieses Modell einem wachsenden Zufallsgraphen. Diese Graphen haben jedoch eine exponentielle Degree-Verteilung $P(k)\sim e^{-\beta k}$. In einem Modell ohne Wachstum, aber mit Preferential Attachment, nimmt $P(k)$ keinen stationären Zustand an, da die Knotenanzahl $N$ konstant bleibt, jedoch kontinuierlich neue Verbindungen geknüpft werden. Nach der Zeit $t=N(N-1)/2$ ist das Netzwerk vollständig verbunden.

Obwohl die lineare Form des ``Preferential Attachments'' (2.7) nur einen speziellen Fall darstellt, haben Untersuchungen an realen skalenfreien Netzen bisher nur diese Form gefunden [28,29,30]. Eriksen und Hörnquist [31] zeigten später, daß wachsende Netzwerke nur für die lineare Form des ``Preferential Attachments'' eine Verteilung $P(k)$ nach einem Potenzgesetz haben.

Die ersten Versuche mit dem BA-Modell führten Barabási und Albert numerisch durch. Später sind verschiedene analytische Lösungen vorgestellt worden. Barabási, Albert und Jeong [27] stellten einen Kontinuumsansatz vor, Dorogovtsev, Mendes, Samukhin [7] stellten einen Ansatz mit einer erzeugenden Funktion vor, und Krapivsky, Redner, Leyvraz einen Differentialgleichungsansatz [32]. Alle Ansätze bestätigen im Ergebnis die Verteilungsform (2.8) mit $\nu=3$.

Dieses einfache Modell legt den Grundstein für das Verständnis der generischen Mechanismen, die für die Wachstumsdynamik eines Netzes mit skalenfreier Potenzgesetz-Verteilung notwendig sind. Dennoch hat dieses Modell eine entscheidene Schwäche. Der Exponent der Degree-Verteilung ist konstant $\nu=3$. Viele reale Netze zeigen zwar ein skalenfreies Verhalten, aber die Exponenten variieren im Bereich von etwa $1$ bis $3$ (siehe Tab. 1.1).