Das Modell von Krapivsky, Rodgers und Redner

Bereits bei dem Modell von Dorogovtsev et al. kündigte sich ein nächster Schritt der Modellierung an: ein Modell für gerichtete Netzwerke. Einige der größten untersuchten skalenfreien Netzwerke sind gerichteter Natur, wie z.B. das Netzwerk aus Zitierungen in wissenschaftlichen Veröffentlichungen oder das WWW. Die Topologie solcher Netzwerke läßt sich jedoch nicht nur mit einer Degree-Verteilung beschreiben, sondern die Unterscheidung nach Indegree-Verteilung $P_{in}$ und Outdegree-Verteilung $P_{out}$ gibt einen genaueren Einblick in deren Struktur. Diese Verteilungen sind für gerichtete Netzwerke bestimmt worden und eine Reihe dieser Netze zeigten jeweils ein Potenzgesetz mit unterschiedlichen Exponenten (vgl. Tab. 1.1).

Das Modell von Krapivsky, Rodgers und Redner [8] ermöglicht es, Netzwerke zu erzeugen, deren Indegree- und Outdegree-Verteilung jeweils skalenfrei sind, mit den Exponenten $\nu _{in}$ und $\nu _{out}$. Die Wachstumsdynamik läßt sich, je Zeitschritt, durch zwei mögliche Prozesse beschreiben:

(i)

Knoten-Wachstum: Mit der Wahrscheinlichkeit $p$ wird dem Netzwerk ein neuer Knoten hinzugefügt und mit einem älteren Knoten verbunden. Die Wahrscheinlichkeit eines bestehenden Knotens als Ziel gewählt zu werden, hängt von dessen Indegree ab.

(ii)

Link-Wachstum: Mit der Wahrscheinlichkeit $q=1-p$ wird eine Verbindung zwischen zwei bereits bestehenden Knoten geknüpft. Die Wahl des Urspungsknotens hängt von dessen Outdegree ab und die Wahl des Zielknotens von dessen Indegree.

Die Abbildung 2.3 illustriert die beiden Wachstumsprozesse.

Abbildung: Die Wachstumsprozesse im Krapivsky et al. Modell: (i) Hinzufügen eines neuen Knoten mit direktem Anknüpfen an einen bestehenden Knoten. (ii) Erzeugen einer Verbindung. Aus Krapivsky et al. [8]

Seien $N(t)$ die Anzahl der Knoten, $I(t)$ die gesamte Anzahl der Inlinks und $J(t)$ die gesamte Anzahl Outlinks in einem Netzwerk zum Zeitpunkt $t$. Entsprechend den beiden Wachstumsregeln des Modells entwickeln sich die Gesamtanzahlen:

$$(N,I,J)\to \begin{cases}(N+1,I+1,J+1) & \text{mit Wahrscheinlichkeit $p$}, (N,I+1,J+1) & \text{mit Wahrscheinlichkeit $q$}. \end{cases}$$ (2.14)

Mit der Wahrscheinlichkeit $p$ wird ein neuer Knoten hinzugefügt und mit einem gerichteten Link ans Netzwerk angebunden, folglich nehmen die Knotenanzahl und beide Gesamtkonnektivitäten jeweils um eins zu. Mit der Wahrscheinlichkeit $q$ wird nur ein neuer Link hinzugefügt, so daß $N$ konstant bleibt. Dementsprechend entwickeln sich die Werte mit der Zeit nach:

$$N(t)=pt, \qquad I(t)=J(t)=t,$$ (2.15)

daraus lassen sich unmittelbar der mittlere In- und Outdegree bestimmen,

$$<k_{\rm in}> \equiv I(t)/N(t)=\frac{1}{p}, \qquad <k_{\rm out}> \equiv J(t)/N(t)=\frac{1}{p}$$ (2.16)

Beide sind zeitunabhängig und gleich $1/p$. Um die gemeinsame Verteilung zu bestimmen müssen noch die Auswahlmechanismen spezifiziert werden.

• Die ``Attachment Rate'' $A(i,j)$ ist als die Wahrscheinlichkeit definert, daß ein neuer Knoten zu einem bestehenden Knoten mit Indegree $i$ und Outdegree $j$ verbunden wird,

• die ``Creation Rate'' $C(i_1,j_1;i_2,j_2)$ ist als die Wahrscheinlichkeit definiert, daß eine neue Verbindung zwischen einem Knoten mit Indegree $i_1$ und Outdegree $j_1$ und einem $(i_2,j_2)$-Knoten eingefügt wird.

Krapivsky, Leyvraz und Redner [32] zeigten, daß skalenfreie Verteilungen nur für lineare Raten zu erwarten sind. Die Raten werden analog zum Modell von Dorogovtsev zum Wachstum skalenfreier Netze gewählt.

$$A(i,j) = A_i=i+\lambda, \qquad C(i_1,j_1;i_2,j_2) = C(j_1,i_2)=(i_2+\lambda)(j_1+\mu).$$ (2.17)

Die Parameter $\lambda$ und $\mu$ müssen den Bedingungen $\lambda > 0$ und $\mu > -1$ genügen, damit die Raten für alle möglichen Werte des Indegree $i$ und des Outdegree $j$ positiv sind, $i \geq 0$ und $j \geq 1$. Diese Raten entsprechen einem ``Preferential Attachment'' bzw. ``Preferential Update'' von Verbindungen nach dem bekannten Mechanismus früherer Modelle, aus einer anfänglichen Attraktivität $\lambda$, $\mu$ und einer linearen Abhängigkeit vom In- bzw. Outdegree. Diese Form der Raten wird linear-bilineare Form genannt.

Mit dem Wachstum des Netzwerks entwickelt sich die gemeinsame Verteilung $R(i,j)$, definert als die relative Anzahl von Knoten mit Indegree $i$ und Outdegree $j$ im Netzwerk. Nach Krapivsky et al. kann die Form der Verteilung mit folgendem Differentialgleichungsansatz bestimmt werden.

$${d R(i,j)\over dt} = (p+q)\left[{(i-1+\lambda)R(i-1,j)-(i+\lambda)R(i,j)\over I+\lambda N}\right]$$ (2.18)

$$+ q\left[{(j-1+\mu)R(i,j-1) -(j+\mu)R(i,j)\over J+\mu N}\right] +p \delta_{i0}\delta_{j1}.$$

Der erste Summand beinhaltet die Änderung des Indegree der Zielknoten. Diese Änderung tritt sowohl beim Knoten-Wachstum, als auch beim Link-Wachstum auf (Wahrscheinlichkeit $p+q = 1$). Beide Prozesse erzeugen einen neuen Link, dessen Ziel via ``Preferential Attachment'' gewählt wird. Die Anzahl der Knoten mit Indegree $i$ nimmt um eins zu, wenn ein Knoten mit Indegree $i-1$ diesen Inlink erhält. Verringert sich um einen Knoten, wenn dieser Inlink einem Knoten zugefügt wird, dessen Indegree bereits $i$ ist. Der zweite Summand bestimmt die Änderungen im Outdegree der Quellknoten. Hier wirkt nur das Link-Wachstum (Wahrscheinlichkeit $q$), da nur dieser Prozeß eine Änderung im Outdegree bestehender Knoten bewirkt. Bei dem Hinzufügen eines Links wird der Quellknoten via ``Preferential Update'' gewählt. Der dritte Summand repräsentiert das Auftreten neuer Knoten, die nur einen Outlink und keinen Inlink besitzen (Wahrscheinlichkeit $p$).

Krapivsky et al. zeigten durch Betrachtungen der Lösungen des Gleichungssystems (2.18), daß sich $R(i,j)$ linear mit der Zeit entwickelt. Es kann daher $R(i,j)$ durch die stationäre Form $r(i,j)=R(i,j)/t$ substituiert werden. Mit $N=pt$, und $J=I=t$ und folgenden Ersetzungen

$$a=q {1+p\lambda\over 1+p\mu}\quad {\rm und}\quad b=1+(1+p)\lambda,$$

ergibt sich eine Rekursionsformel für $r(i,j)$

$$[i+a (j+\mu)+b]r(i,j) = (i-1+\lambda)r(i-1,j)$$

$$+ a (j-1+\mu)r(i,j-1)$$

$$+ p (1+p\lambda)\delta_{i0}\delta_{j1}.$$ (2.19)

Aus der gemeinsamen Verteilung $r(i,j)$ lassen sich die Indegree- und Outdegree-Verteilung durch die Summen $P_{in}(i)=\sum_j r(i,j)$ und $P_{out}(j)=\sum_i r(i,j)$ bestimmen. Krapivsky, Rodgers und Redner zeigten, daß sich aus (2.19) die Verteilungen

$$P_{in}(i) \sim i^{-\nu_{in}} \quad {\rm und} \quad$$ (2.20)

$$P_{out}(j) \sim j^{-\nu_{out}} \quad$$ (2.21)

ableiten lassen. Die Exponenten bestimmen sich aus den Parametern $\lambda,\mu,p$ des Modells nach

$$\nu_{in} = 2+p \lambda$$ (2.22)

$$\nu_{out}= 1+ \frac{1}{q}+\mu p \frac{1}{q}.$$ (2.23)

Dieses Modell ist in der Lage die gegenwärtig bestimmten Degreeverteilungen von realen, skalenfreien Netzwerken wiederzugeben. Darüber hinaus bietet es die Möglichkeit, Aussagen über die gemeinsame Verteilung $r(i,j)$ der Knoten eines Netzwerks in Abhängigkeit von deren Indegree und Outdegree zu treffen.