Die unkorrelierte Verteilung

In einer ersten Näherung werden Korrelationen zwischen Indegree und Outdegree der Knoten vernachlässigt. Die gemeinsame Verteilung $r(i,j)$ kann daher aus den einzelnen Verteilungen $P_{in}$ und $P_{out}$ konstruiert werden

$$r_0(i,j) = P_{in}(i)P_{out}(j).$$ (4.2)

Mit $P_{in}(i)\sim i^{-\nu_{in}}$ und $P_{out}(j)\sim j^{-\nu_{out}}$ kann für $i\simeq j$ bereits abgeschätzt werden, daß $r_0(i,j) \sim i^{-\nu_{in}-\nu_{out}}=i^{-4.6}$ ist. Damit entspricht die Wahrscheinlichkeit einen Knoten bei $i=50$ zu finden, etwa $10^{-8}$. Bei einer Netzwerkgröße des Webcrawl von $N=1.8\cdot 10^7$ Knoten, werden einzelne Knoten im Mittel erst ab einer Wahrscheinlichkeit von $10^{-7}$ erwartet. Die Größe des belegten Wertebereiches der Verteilung $r_{crawl}(i,j)$ ist bereits ein erstes Indiz für eine Korrelation zwischen In- und Outdegree der Knoten.

Abbildung: Gemeinsame Verteilung des Webcrawls normiert mit der unkorrelierten Verteilung $r_{crawl}(i,j)/r_0(i,j)$. Die Färbung gibt die Abweichung der Wahrscheinlichkeiten für einen Knoten mit $i$ Inlinks und $j$ Outlinks an (lineare Farbskala).

Für diese Näherung werden die gemessenen Verteilungen $P_{in},P_{out}$ (vgl. Abb. 3.4, Abb. 3.5) verwendet, um den typischen, anfänglich exponentiellen Verlauf der Outdegree-Verteilung zu beachten. In Abbildung 4.2 ist die Verteilung des Webcrawls normiert mit der Näherung $r_{crawl}(i,j)/r_0(i,j)$ dargestellt. Unterschiede manifestieren sich daher als Abweichungen von Eins.

Besonders auffällig ist die deutlich hervortretende Diagonale. Die Ursachen hierfür werden in Abschnitt 4.5 diskutiert. An dieser Stelle interessiert zunächst, ob die Potenzgesetze korrekt wiedergegeben werden. Daher ist der Bereich der Verteilung außerhalb des Einflusses der Diagonalen interessant. Um diesen Bereich genauer darzustellen ist der Wertebereich für die Färbung auf $0-5$ eingeschränkt. Werte jenseits von 5 erhalten daher die Färbung von 5.

Abbildung: Diagonaler Schnitt durch die Abbildung 4.2 ausgehend von $i=0,j=15$, parallel zur hervortretenden Diagonale. Es ist ein deutlich abweichender Verlauf zwischen der unkorrelierten Verteilung und der Verteilung des Webcrawls zu sehen. Die angelegte Gerade entspricht einem Exponenten von $0.87$.

Mit zunehmenden $i,j$ erkennt man eine deutlich höhere Präsenz von Knoten im Webcrawl als in der Näherung (4.2). In Abbildung 4.3 ist ein diagonaler Schnitt durch die normierte Verteilung aus Abbildung 4.2 dargestellt, um den Verlauf klarer zu zeigen. Der Schnitt geht von $i=0,j=15$ mit einer Steigung von 1 aus, um einerseits möglichst außerhalb des Einflußes der Diagonalen zu bleiben, andererseits möglichst viele Datenpunkte zu erhalten. $n$ bezeichnet den Abstand von Ursprung des Schnittes. Damit Abweichungen von dem Potenzgesetz (4.2) deutlicher werden, sind die Daten doppeltlogarithmisch aufgetragen. Bei einer qualitativen Übereinstimmung des Verlaufs der gemessenen Verteilung und der Näherung wird in diesem Schnitt ein paralleler Verlauf zur X-Achse erwartet. Im Bereich bis $n=5$ ist der Verlauf relativ gut wiedergegeben. Zu höheren Degrees zeigt sich jedoch eine deutliche Abweichung. Die angelegte Gerade entspricht einem Exponenten von $0.87$. Weitere Schnitte parallel zur X-Achse und Y-Achse zeigen ähnliche Abweichungen.

Der Vergleich zeigt, daß die einzelnen Verteilungen der In- und Out-Degrees korreliert sind.